알고리즘

[C++] 백준 12851번 숨바꼭질 2

그래프 탐색 문제. BFS 너비 우선탐색을 통해서 풀면 되는 문제다. 조건이 꽤 까다로운 문제다. 다른 그래프 탐색 문제들처럼 풀면 메모리 초과가 난다. 문제풀이 예전에 숨바꼭질1을 풀었었는데, 그 때는 그냥 가장 빠르게 목적지에 도달한 경우 몇 초인지만 알면 되는 문제였다. 이 문제는 가장 빠르게 목적지에 도달한 경우가 몇 초이고, 그 시간대로 가는 경우가 몇 가지가 존재하는지 출력하면 된다. 조건은 짜기 나름이므로, 코드 전문을 보고 틀린 이유만 정리하겠다. /* * 백준 12851번 숨바꼭질 2 * https://www.acmicpc.net/problem/12851 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include using namespace std; int s..

[C++] 백준 1068번 트리

그래프 탐색 문제. 그 중에서도 트리 & DFS문제이다. 트리의 기본 개념만 안다면 쉽게 풀 수 있다. 조건을 하나 잘못 생각해서 틀렸었다. 문제풀이 어려운 것 없이, 부모 - 자식, 자식 - 부모 관계를 모두 저장해둔다. 그리고 각각 다음에 사용한다. 부모 - 자식 관계 : 트리에서 깊이 우선 탐색을 통해 리프 노드가 몇 개인지 구할 때 사용한다. 자식 - 부모 관계 : 지울 노드의 부모 노드의 번호를 구하고 해당 부모 노드에서 부모 - 자식 관계에서 지울 노드를 찾은 후 지울 때 사용한다. 루트 노드가 예시 케이스에서는 -1이 모두 첫번째로 나오긴 했지만, 나중에 나오는 경우를 대비해서도 코드를 구현했다. /* * 백준 1068번 트리 * https://www.acmicpc.net/problem/10..

[C++] 백준 1965번 상자넣기

다이나믹 프로그래밍 문제. 어렵게 생각 안하고 풀었는데 틀렸습니다. 를 엄청많이 받고서야 풀었다. 그냥 완전탐색 비슷한 DP 느낌의 문제였다. 문제풀이 내가 푼 방식은 다음과 같다. 1번째 상자 ~ N번째 상자를 탐색한다. i번째 상자를 탐색하면서 자기 앞에 있는 상자들(1 ~ i) 중 가장 많이 담을 수 있는 상자를 골라서 + 1 해준 후 현재 상자가 최대 이만큼 담을 수 있다는 것을 기록해놓는다. 상자들 중 몇번째 상자가 가장 많이 기록할 수 있는지 출력한다. #include #include using namespace std; int boxCnt; int boxSize[1001]; int dp[1001]; int ans = 1; int main() { ios_base::sync_with_stdio(..

[C++] 백준 1890번 점프

다이나믹 프로그래밍 문제. 처음에 Bottom-Up 방식으로 시도했는데 틀렸다. Top-Down 방식으로 풀었을 때에도 방문처리를 안했어서 틀렸다. [C++] 백준 1520번 내리막 길 그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없 kimyunseok.tistory.com 위 문제와 거의 유사한 문제이다. 난이도는 왜이렇게 차이나는지는 모르겠지만, 위 문제를 풀 수 있다면 이 문제도 풀 수 있다. 문제풀이 다이나믹 프로그래밍의 TOP DOWN 방식과 DFS과 비슷한 로직을 혼용해서 풀었다. (1, 1)에서 시작해서 오른쪽, 아래쪽 방향으로 가면서 (r, c..

[C++] 백준 5014번 스타트링크

그래프 탐색 중 너비 우선 탐색으로 푸는 문제. [C++] 백준 1107번 리모컨 브루트 포스 완전탐색 문제. 이 문제는 두 번 풀게됐는데, 처음에 푼 완전탐색 코드에서 시간이 다른 사람들에 비해 너무 많이 나와서 백준 게시판을 참고해서 다시 풀게됐다. 정답 비율이 낮지 kimyunseok.tistory.com 위 리모컨 문제와 똑같은 문제였다. 예전에 푼 로직이 생각나서 바로 풀 수 있었다. 문제풀이 리모컨 문제와 아주 유사한 문제이다. BFS를 하게 되는데, 현재 층에서 위, 아래 층이 유효한 층이고 방문하지 않았다면 다음 층을 큐에 넣어주면서 계속 탐사하게 구현하면 된다. /* * 백준 5014번 스타트링크 * https://www.acmicpc.net/problem/5014 * 그래프 탐색 이론 ..

[C++] 백준 1167번 트리의 지름

[C++] 백준 1967번 트리의 지름 그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다 kimyunseok.tistory.com 위 문제와 거의 똑같은 문제. 차이점이라면, 루트 노드가 1이 아니다. 정점 번호가 작은 순서부터 입력되는 것이 아니라 랜덤으로 입력된다. -1이 나오기 전까지 노드를 연결시킨다. 정도가 되겠다. 3번 차이점은 사실 크게 중요하지는 않다. 위에 링크를 남긴 문제를 풀었다면 이 문제도 아마 크게 어렵지 않게 풀 수 있다. 문제풀이 자세한 풀이는 생략하겠다. (위 비슷한 문제와 거의 똑같은 방식으로 풀었다.) 우선, 루트 노드가 무엇인..

[C++] 백준 1967번 트리의 지름

그래프 탐색 문제. 처음에 그냥 정점마다 DFS를 모두 돌려서 제출했는데 맞췄다. (시간 복잡도를 계산해도 가능할 것 같았다.) 그런데 문제가 의도하는 바가 이것도 아닌 것 같고, 제출 내역에 다른 사람들 시간을 보니 다시 풀어야 겠다고 생각해서 다시 풀어서 제대로 맞출 수 있었다. DFS를 자유자재로 변형할 수 있으면 쉽게 맞출 수 있는 문제였다고 생각한다. 문제풀이 우선 처음 이 문제를 풀었을 때, 정점의 개수가 최대 10,000개인 것을 확인했고 간선의 개수가 최대 9,999개인 것을 확인했다. 각 정점마다 DFS를 한 번 하는데 소요되는 시간은 모든 정점을 방문했을 때, O(N)의 시간이 소요된다. 그러면 모든 정점에서 DFS를 한다면 총 소요되는 시간은 O(N^2)이다. N은 최대 10,000이..

[C++] 백준 1520번 내리막 길

그래프 탐색 + 다이나믹 프로그래밍 문제 사실 이 문제를 본 건 엄청 오래 전이였는데, 그 당시엔 못 풀었었다. (검색도 했었는데, 그냥 이렇게 푸는거구나. 만 알고 넘어감. 바로 풀면 의미가 없으므로!) 이번에 학교에서 주최한 프로그래밍 대회에서 비슷한 문제를 봤었는데, 이 문제에 대한 기억이 떠올라서 검색해서 비슷한 문제를 맞춘 후에 다시 풀어봤다. 그래프 탐색 이론과 DP (Top-Down)방식을 사용하는 문제가 있다니 신기했다. 문제풀이 결국, (1, 1)에서 (M, N)까지 몇 개의 길이 있는지를 구하는 문제다. 나는 지금까지 DP는 Bottom-Up 위주로 많이 풀었었는데 이 문제는 지금 (1, 1)에서 알 수 있는 경우의 수가 없다. 그런데 (M, N)에서 (M, N)으로 가는 경우의 수는 ..

[C++]백준 1806번 부분합

투 포인터 문제. 바로 이전에 풀었던 2230번 수 고르기 문제와 비슷한 유형의 문제이다. 정렬하지 않고 푸는 투 포인터 문제이다. 문제풀이 연속된 수들의 합 중에서 길이가 가장 짧은 것을 구하면 된다. 나같은 경우에는, front, tail(lo, hi)를 둘 다 0으로 초기화 시켜놓고 front부터 tail까지에 속하는 모든 원소의 합을 통해서 조건을 만들었다. 반복문은 front > numCnt >> minSum; int input; for (int i = 1; i > input; numVec.push_back(input); } int front = 0; int tail = 0; int curSum = numVec[0]; while (front = minSum) { ans = min(ans, tai..

[C++] 백준 2230번 수 고르기

투 포인터 문제. 투 포인터 문제를 오랜만에 풀었는데 틀렸다. 틀린 이유 위주로 정리하겠다. 문제 풀이 수열의 길이는 최대 100,000이다. 만일 한 index마다 끝까지 탐사하게 될 경우 시간 복잡도가 100,000 x 100,000이 되므로 10,000,000,000번의 연산을 하게된다. 이는 시간 초과가 발생할 것이다. 따라서 다른 방법을 생각했는데, 투 포인터 방법이 생각났다. 투 포인터는 한 줄의 배열이 있을 때 두 개의 포인터를 두어서, 포인터를 front, tail (혹은 lo, hi)로 두어서 포인터만 이동시키면서 푸는 방식이다. 이 문제는 최소의 차이를 구해야 하므로 정렬 시킨 후 투 포인터로 탐색해서 풀면 된다. 주의할 점은 고르는 두 수가 같은 수일수도 있다. A[i]를 두 번 고르..