백준

길이 N이 주어졌을 때 가능한 계단수(앞 숫자와 연속되는 수)의 개수를 구하는 문제이다. 재귀함수를 이용해 코드를 작성해 보았다. da=c 에서 a는 길이, b는 계단수의 마지막 수, c는 b를 포함한 계단수의 개수를 의미한다. 길이가 n이고 마지막 수 x를

패인 런타임 에러: 백준에서 return 1; 코드는 프로그램이 비정상적으로 종료되었다고 판단된다고 한다. 출력 초과: 매 반복문이 돌아갈 때마다 judge를 false로 초기화해 줬어야 했는데 빼먹었다. 앞으로 실수하지 않도록 주의해야지

scanf로 string 자료형을 입력받고 난 후에 char 자료형을 입력받을 때는 상당히 주의해야 한다." %c" 형식으로 공백 한 칸을 꼭 띄워줘야 한다. 분명 잘 풀었는데 에러가 떠서 당황스러웠는데 공백을 쓰지 않은 탓이었다.

자료구조입문 과제로 스택을 구현했던 기억이 떠오르는 문제였다. 큐의 작동 원리를 이해하는 것이 핵심이다.

숫자가 7개이고 간격이 3이라고 가정하자.1 2 3 4 5 6 72 3 4 5 6 7 1 (1 pop, push)3 4 5 6 7 1 2 (2 pop, push)4 5 6 7 1 2 (3 pop!) --> 3 프린트

flag 변수를 이용해 레이저인지 괄호의 끝인지를 구분했다. 레이저로 절단할 때마다 sum에 스택 사이즈만큼을 더해주고, 괄호의 끝을 만나면 1을 더해주었다.

가장 핵심적인 코드는 아래 부분이다. 중첩 반복문을 이용해 에라토스테네스의 체를 만들 수 있다. 또는 아래와 같은 방식으로 에라토스테네스의 체를 만들 수 있다.

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다. N(짝수)=A(소수)+B(소수)\-> A=N-B 이 추측이 맞다면 N-B는 소수여야 한다. 따라서 N-B가 소수임을 확인하면 골드바흐의 추측이 사실인지 검증할 수 있다. 에라토스테네스의 체를 이용하여 간

팩토리얼의 경우 소인수분해를 했을 때 5가 2보다 훨씬 적기 때문에 수를 5로 나누었을 때 나누어지는 횟수를 변수 count에 차근차근 더해주면 답을 구할 수 있다.

과도한 반복문 사용으로 시간초과가 뜨는 코드이다. 구글링의 힘을 빌려 코드를 다시 짜 보았다. int 자료형을 long long 자료형으로 바꿔주고 구현 방식을 달리했다.

잘 풀었다고 생각했는데 틀려서 당황스러웠는데 이번에도 자료형 때문이었다. sum이 int 자료형이 커버 가능한 범위를 초과하는 경우가 있기 때문에 sum을 long long 자료형으로 설정해주면 오류가 나지 않는다. 문제를 푸는 데 핵심이 되는 아래 코드를

BOJ 바로가기

정답 소스코드를 보고 수정한 코드수정 전 코드최솟값을 구할 때 값을 일일이 비교하는 코드보다는 min을 초기화해두고 하나씩 덧붙이면서 비교해주는 방식이 훨씬 간편하다.

코드 맞게 잘 짰고 결과도 잘 나오는데 왜 안풀리나 싶었는데 숫자가 너무 커져서 long long 자료형의 범위조차도 넘어가 버릴 수 있기 때문이었다. 그래서 마지막에 썼던 cout<<go(n)%10007 코드를 삭제하고 매 반복마다 %10007

다음의 점화식이 핵심이다.

BOJ 바로가기문제를 잘못 이해해서 한참 잘못 풀었다가 나중에야 정확히 이해했다.수열 A = {10, 20, 10, 30, 20, 50}가 있을 때 가장 긴 증가하는 수열은 {10, 20, 30, 50}이다. 수열 A에서 만들 수 있는 증가하는 수열은 {10, 20},

[백준11053] 가장 긴 증가하는 부분 수열 (C++)위 문제와 거의 비슷한 문제다. 다른 점이 있다면 수열의 모든 수를 출력해야 한다는 것. 어떻게 구현할지 고민하다가 이차원 배열을 만들어서 d[n]에 대응하는 수열을 저장해주는 방식으로

처음에 TOP-DOWN 방식으로 풀었는데 숫자가 너무 커서 그런지 스택 오버플로우가 발생하였다. 결국은 정답 소스코드를 참고하여 반복문을 이용한 방식으로 풀었다. 다음의 점화식이 핵심이다. d[n]=min(d[n], d[i-j*j]+1)

재귀함수를 이용한 TOP-DOWN 방식을 적용했을 땐 시간초과가 났다. 질문답변 글을 읽어보니, dp[3][100001]을 0으로 초기화했을 때 메모이제이션이 작동하지 않는 경우가 생기기 때문이라고 한다.

가장 긴 증가 부분 수열 / 가장 큰 증가 부분 수열 이런 타입 문제가 내겐 어렵게 느껴진다 ㅠd[i]=d[j]+a[i]d[j]는 d[i] 이전의 가장 큰 증가 부분 수열이다.

점화식을 어떻게 세워야 할지 고민하다가 n에서 가장 긴 증가하는 수열의 길이, 가장 긴 감소하는 수열의 길이 두 가지를 구해주면 답을 구할 수 있을 거란 생각이 들었다.

연속합 수열에서 수 하나를 제거할 수 있다는 조건 때문에 상당히 까다로웠던 문제다. 한참을 고민하고 코드를 짜보다가 제대로 작동하지 않아서 결국 정답 소스코드를 참고했다. 반례가 많은 문제여서 답안을 몇 번이나 제출하고 나서야 정답을 제출할 수 있겠다.

RGB 거리보다 조건이 한 개 더 추가되었다. 바로 첫번째 집과 마지막 집의 색이 같으면 안 된다는 것. 반복문을 이용해 첫번째 집의 색깔을 정해주고 시작한다. 그리고 세 개의 점화식을 통해 d[n][0], d[n][1], d[n][2]를 구해준다.

3월 9일에 수강하기 시작했던 알고리즘 강의가 3월 27일 오늘 끝났다. 약 2주 반 가량의 시간동안 강의를 들으며 공부한 셈이다. 중간중간 학원알바도 하고 친구들도 만나며 여유롭게 공부했다. 그러다보니 생각보다는 시간이 조금 더 걸렸다😂

문제를 푸는 데 번역 때문에 오해의 소지가 있었다.상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. ▷ 사탕의 색이 서로 다르지 않아도 인접한 두 칸을 골라 바꿀 수 있다.

브루트포스 문제이다. i = 0부터 1,000,000까지 채널을 올려가면서 원하는 채널 n에 다다르기 위해 버튼을 누르는 수의 최솟값을 구해준다. +와 - 버튼이 존재하기 때문에 절댓값 함수를 이용했고, 고장난 버튼인지 여부를 확인하기 위해 check함수를 만들었다.

날짜 계산 문제와 비슷하다. 두 문제 모두 브루트포스를 이용해 해결할 수 있지만, 카잉 달력 문제는 시간초과를 고려해서 조금 다른 방식으로 풀어야 한다. num을 x로 초기화하고 m을 계속해서 더해주는 방식으로 원하는 답이 나올 때까지 검사했다.

숫자가 이전에 나온 적 있는지 확인할 수 있도록 bool형 check 배열을 만들어두는 것이 핵심이다. 숫자를 배열에 넣을 때마다 check배열을 false로 만들어주고, 재귀함수를 돌린 후에는 다시 true로 바꾸어주어야 한다.

정답률이 낮은 문제이다. 그도 그럴 것이 고려해줘야 할 부분이 정말 많다. 대표적으로 틀리기 쉬운 부분은 다음과 같이 두 가지가 있다.

그래프 탐색 문제이다. 한 집이 존재하고 그 집의 상하좌우에 또 다른 집이 존재할 경우 집과 집 사이에 간선이 존재한다고 판단할 수 있다. BFS 또는 DFS를 통해 문제를 해결할 수 있다.

대표적인 BFS 문제이다. 출발점부터 목적지까지의 최단경로를 구해야 한다. 📌 ans 배열에 (x,y)까지의 최단거리를 저장해주었고, (x, y)에서 (nx, ny)로 넘어갈 때마다 ansnx에 ansx+1 값을 넣어주었다.

점점 BFS에 익숙해져 가는 것 같다! 최대한 다른 소스코드 참고 안하고싶어서 계속 혼자 코딩했는데 결국 풀어내서 기쁘다🥰 전체 토마토를 익히는 데 어느 정도의 시간이 걸리는지 구해내야 한다. 그동안의 BFS문제는 시작점이 하나였는데,

게임판에 사각형 사이클이 존재하면 Yes를, 존재하지 않으면 No를 반환해야 한다. 📍 DFS를 이용하여 풀 수 있다. 📍 현위치에서 상하좌우로 계속해서 나아가되 다시 본래의 위치로 돌아오면 flag에 true값을 할당해준다.

한 개의 순환선과 여러 개의 지선으로 이루어진 그래프가 주어진다. 해당 위치의 인덱스가 순환선인 경우에는 0, 지선일 경우에는 순환선까지의 거리를 출력해야 한다. BFS와 DFS를 이용하여 해결할 수 있다.

섬에서 다른 섬까지 다리를 하나 건설할 때, 다리의 길이의 최솟값을 구해야 한다. 📍 몇시간동안 이 문제만 붙잡고 있었다. 분명 로직은 완벽한데 자꾸 이상한 값이 나와서... 몇시간동안 디버깅한 결과 찾은 오류의 원인은 .. 큐를 비워주지 않아서 생겼던

수빈이가 n, 동생이 k의 위치에 있을 때 수빈이가 동생을 찾기 위해서 몇 번 이동해야 하는지 구해야 한다. 조심해야 할 부분 수빈이와 동생이 같은 위치에 있을 경우수빈이가 동생보다 오른쪽에 있을 경우 go3배열을 선언해 한 칸 앞으로 갈 경우

숨바꼭질 문제와 매우 유사하다. 차이점은 경로를 표시하는 출력을 추가해야 한다는 것뿐이다. 숨바꼭질 문제의 풀이는 다음 링크에서 확인할 수 있다. 📍 처음에는 배열 벡터를 선언해서 각 위치마다 이동경로를 표시해주었는데

기본적인 다익스트라 문제이다. 다만 정답률이 많이 낮은데, 주의해야 할 사항이 몇 가지 있기 때문이다ㅎㅎ,, 사용할 변수의 값이 int의 범위를 넘어갈 수 있다.pq.top().first 값이 t[curr] 값보다 크다면 continue를 진행해줘야 한다.

n명의 사람이 주어졌을 때 n/2명씩 스타트 팀, 링크 팀에 넣는다. 두 팀의 능력치가 최소가 되도록 팀을 구성하고, 능력치의 차이를 출력한다. 브루트포스, 백트래킹 문제이다. 어렵지 않게 풀릴 거라 생각했는데 생각보다 오래 걸렸다.

도시와 도시 간의 거리(시간) 정보가 담겨있는 그래프가 주어진다. 각 도시에서 다른 도시로 갈 수 있는 최소 시간을 구한 다음에, 친구들의 최대 왕복 시간이 최소가 되는 도시를 구해야 한다. 📍 플로이드-워셜 알고리즘을 이용해 2차원의 최소시간 배열을

각 집하장에서 최단시간으로 다른 집하장까지 이동할 때 첫 번째로 거쳐야 하는 집하장의 번호를 구해야 한다. 📍 플로이드-워셜 알고리즘으로 간단하게 풀 수 있다. 📍 답을 저장할 배열을 선언한 후, 삼중 반복문을 돌릴 때 다음 코드 한 줄을 추가하면 된다.

양방향 통행이 가능한 도로와 일방향 통행만 가능한 도로가 있다. 한 건물에서 다른 건물이 도착하기까지 몇 개의 일방향 통행 도로를 거슬러 가야 하는지 구해야 한다.이것저것 해보느라 많이 헤맸는데 생각보다 답이 간단했던,,,문제다 ㅎㅎ 😂

모든 행성을 탐색할 수 있는 최소 시간을 구하는 문제이다. 📍 가중치가 같지 않고, 모든 위치에서의 최단경로를 구해야 하기 때문에 플로이드-워셜 알고리즘을 이용하였다. 📍 DFS와 백트래킹을 이용해 문제를 해결했다.

주어진 N개의 숫자 중 M개를 사전순 순열로 출력하는 문제이다. 근데 이제 숫자가 중복으로 주어져도 수열은 중복 없이 출력해야 하는... 지금까지 풀었던 N과 M 중 제일 어렵다. 중복된 수열을 출력하면 안되기 때문이다. 📍 set이라는 편리한 도구가 있어

이모티콘 문제와 상당히 유사하다고 느꼈다. 벽 부수고 이동하기 문제를 더 연습해보고 싶으신 분들은 이모티콘 문제를 풀어보면 좋을 것 같다! 단순 BFS에 조건이 하나 더 추가된 문제이다. 0(길)과 1(벽)이 적힌 지도가 입력으로 주어진다.

다익스트라 알고리즘 구현 연습에 좋은 문제인 것 같다. 단순 다익스트라 구현 + 약간의 아이디어가 추가된 문제이다. 최단경로를 구하되 문제에서 주어지는 두 점을 꼭 지나도록 해야 한다.

배열을 전부 탐색하는 방식으로 풀면 시간 초과가 뜨는 문제이다. 그래서 스택으로 필요 없는 부분은 쳐내고 탐색하게끔 풀어야 하는데, 스택을 떠올리기가 어려운 것 같다 😥 맨날 그래프만 풀어서 그런가... 자료구조 알고리즘도 열심히 풀어봐야겠다.

스택 문제 은근 어렵다... ㅋㅋㅋㅋㅋ 😂오큰수 문제와 탑 문제와 유사하다. 📍 현재 빌딩 (i)가 n이 될 때까지 반복문을 돌린다. 📍 만약 현재 빌딩이 이전 빌딩(스택에 쌓여있는 빌딩) 보다 크거나 같다면 이전 빌딩 입장에서 현재 빌딩 이후의 옥상을

비트마스크 명령어를 구현하는 문제이다.비트마스크 공부하기 싫어서 미뤄뒀었는데 오늘 공부해보니 의외로 재밌다!!!

스타트와 링크 문제와 유사하다. 스타트와 링크 문제 풀이는 다음 링크에서 볼 수 있다. 두 팀의 능력치 차이가 최솟값이 될 때의 답을 구하는 문제이다.비트마스크로 풀었다!

숨바꼭질에서 조금 심화된 문제이다. 이번에는 수빈이가 동생을 찾는 데 걸리는 최소 시간뿐만 아니라 최단 경로의 개수까지 알아내야 한다.진짜 손절하고 싶었던 문제... 왜냐면 나는 정말 맞다고 생각했는데 답이 자꾸 틀리다고 나왔다.

연구소에 바이러스가 유출되었다. 바이러스는 벽을 뚫고 퍼질 수 없다. 벽 3개를 세워서 안전구역의 개수를 가장 크게 만들어야 한다. 연구소의 바이러스 위치가 표시된 지도가 입력으로 주어진다.📍 벽을 세운다. 연구소의 크기가 크지 않으니 브루트포스

sign 배열의 정보가 주어진다. sign[a][b] = '+'는 a에서부터 b까지의 합이 양수임을 의미한다. 주어진 sign배열을 만족하는 수열을 찾아야 한다. 📍 브루트포스를 이용해 모든 경우의 수를 조사한다.

도시 간의 최단거리 배열이 주어진다. 이 배열을 보고 도로의 최소 개수를 알아내야 한다. 📍 플로이드-워셜 알고리즘을 조금 변형해서 풀 수 있다. 도시 A에서 도시 B로 갈 때, 도시 C를 경유해서 갈 수 있는 경우 A에서 C로 가는 도시는 필요 없다.

5/9 ~ 6/4 42서울 라피신이 끝난 지 대략 한 달이 지났다. 피신 이후 친구들을 간간이 만나며 집에 있는 시간에는 알고리즘 공부를 했다. 실버에 머물러 있던 백준 티어가 골드2로 올랐고, 나름대로의 자신감도 조금 생겼다.

주어지는 조건에 맞에 소문난 칠공주를 구성해야 한다. 공주들의 자리는 서로 인접해야 하고, 이다솜파가 4명 이상으로 구성되어야 한다. 처음엔 DFS로 풀었는데, 이렇게 풀면 틀린다. 칠공주의 자리가 십자가 모양으로 되어있는 경우는

처음엔 우선순위 큐를 쓰지 않고 그냥 큐로만 풀었다. 그러니까 예제 출력은 맞게 나오는데 런타임 에러가 났다.. 다른 분들의 소스코드를 참고하니 우선순위 큐를 이용해서 푸셨길래 나도 그렇게 푸니까 맞았다. 수정 전 소스코드는 대충 이러했다. 🥶

읽을 수 있는 단어의 개수가 최대가 되게끔 k개의 알파벳을 골라서 배워야 한다. 가능한 모든 조합을 탐색해야 한다.비트마스크를 이용해 모든 조합을 체크할 수 있다. 📍 a, c, i, n, t 이 다섯 글자는 꼭 배워야 한다.

N개의 숫자 중 M개의 숫자를 뽑아 비내림차순의 수열을 만들어야 한다. 단, 수열이 중복되면 안 된다.검색해보니 비트마스크 풀이는 잘 없길래 내가 써보기로 했다. 📍 비트마스크를 이용해 공집합이 아닌 모든 부분집합을 탐색한다.

문자열의 형태로 배열을 입력받은 후 R(reverse)연산 또는 D(delete) 연산을 진행해준 결과를 출력해야 한다.고려해야 할 점은 두 가지이다.

min과 max 사이 제곱수로 나누어떨어지지 않는 수의 개수를 구하는 문제이다. 📍 N을 설정하는 것이 중요하다. 📍 예를 들어 min = 30, max = 45 라고 가정하자.

📍 0이 있는 곳에 BFS를 돌려서 0 뭉텅이마다 라벨링을 해줬다. 동시에 뭉텅이를 구성하는 0이 몇 개인지도 벡터에 담아주었다. 📍 이후 1의 상하좌우에 0이 있다면 뭉텅이의 개수를 ansi에 더해주었다.

알파벳을 숫자로 치환해서 두 단어의 값을 더했을 때의 최댓값을 구하는 문제이다. 그리디 알고리즘을 이용해 풀 수 있다. 각 단어에서 알파벳의 가중치(자릿수)는 다음과 같다.

N x M 행렬에서 K개의 숫자를 뽑아 합의 최대가 되도록 만드는 문제이다.이상한 착각과 시간초과 때문에 꽤나 고생했던 문제이다. 🥶 처음에는 DFS를 돌릴 때 시간 절약을 위해 i는 x부터, j는 y부터 돌렸다.

계산식에 괄호를 적절히 넣어서 계산 결과가 최솟값이 되도록 만들어야 한다.

스도쿠 판을 채우는 백트래킹 문제이다. 📍 bool형 배열 세 개를 만드는 것이 중요하다. row[A][B] = true는 A번째 행에 B라는 숫자가 존재함을 뜻한다. col[A][B] = true는 A번째 열에 B라는 숫자가 존재함을 뜻한다.