문제 이해 단계 https://www.acmicpc.net/problem/9466 1~n번까지 사람이 있고 선택을 한다. (자기 자신도 선택 가능) 조가 이루어지는 경우는, 꼬리 잡기처럼 1 -> 2 -> 3 -> 1 이런 식으로 사이클을 이를 경우이다. 즉, 마지막에는 자기 자신으로 꼭 돌아와야 한다. 이러한 조건일 때, 짝을 이루지 못한 학생 수를 출력하는 문제이다. 문제 접근 단계 문제 이해 단계에서 말했듯이, 꼬리 잡기와 비슷한 패턴이다. 꼬리에 꼬리를 물어 추적을 하는 것이다. 이를 돌려 말하면 점점 깊이 들어간다고 할 수 있는데, 그래서 이 문제는 DFS로 푸는 것이 적절하다고 생각했다. 이 문제에서 짝이 이루어지는 경우는 사이클이 형성될 때이다. 처음 선택했던 사람의 번호를, 마지막 사람이 ..

문제 이해 단계 입력값으로 N이 입력된다. 선택할 수 있는 봉지는 3kg와 5kg이다. 이 봉지들을 이용하여 정확히 Nkg을 나눠 담을 때 가장 적은 봉지가 나오게 하는 문제이다. 문제 접근 단계 현재에서 가장 이득이 되는 선택을 하는 그리디로 풀 수도 있지만, 다이나믹 프로그래밍(DP)으로도 풀 수 있다. 왜냐하면, 작은 부분에서의 답이 큰 부분의 답이 되기 때문이다. N = 15 일 때를 가정해 보자. 15kg는 12 + 3 또는, 10 + 5에서 만들어진 숫자이다. 즉 12,10에서 만들어진 숫자인데, 12와 10은 (9,7), (7,5)에서 만들어진 숫자이다. 이런 식으로 작은 부분의 연산값이 큰 부분의 값이 된다. 이런 특징을 띄고 있기 때문에 DP로 풀 수 있다는 것이다. N에서 가장 적은 봉..

문제 이해 단계 2차원 격자가 주어지고, 각 정점의 연결 정보들이 주어진다. 시작 위치 S와 도착 위치가 E가 주어졌을 때 S에서 E로 가는 최단 거리를 구하고, 그 후 S에서 E로 갔을 때, 방문하지 않았던 정점만을 사용하여 다시 E에서 S로 최단거리로 돌아간다. 이때의 최단 거리의 합을 구하는 문제이다. 문제 접근 단계 해당 문제를 어떻게 푸는지에 대한 키워드는 1. 최단 경로의 거리를 구한다는 것 2. 산책을 할 수 있는 경로의 데이터만 주어진 다는 것이다. 1번의 키워드에서 경로를 탐색하여 최소 횟수를 찾는 DFS나 BFS를 사용해야 한다는 것을 알았다. DFS와 BFS 중 어떤 것으로 풀어야 효율적 일지 고민 중이었는데 2번 키워드에서 힌트를 얻었다. 산책을 할 수 있는 경로만 주어진다는 것은 ..

문제 이해 단계 https://www.acmicpc.net/problem/22948 문제는 앞서 풀었던 원 이동하기 1과 똑같다. 문제에 대한 자세한 설명은 원 이동하기 1에 대한 링크를 달아둘 테니 참고해 주길 바란다. https://howudong.tistory.com/33 [C++] 백준 22946 - 원 이동하기 1 문제 이해 단계 문제 좌표평면에 N개의 원이 존재한다. N개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 수는 howudong.tistory.com 이 문제에서 다른 점은 두 원을 지정해 준다는 점과 원 번호,x좌표,반지름이 입력으로 주어진다는 점이다. 그리고 출력으로 이동횟수와 더불어 이동한 원의 번호를..

문제 이해 단계 https://www.acmicpc.net/problem/16973 NxM 크기의 격자판이 주어지고, 크기가 HxW인 직사각형이 주어진다. 이동할 수 있는 칸은 0, 이동할 수 있는 칸은 1로 되어 있다. 직사각형의 가장 왼쪽 위의 칸이 처음에 주어지고, 도착 좌표가 주어진다. 이때 이 직사각형의 왼쪽 위가 도착좌표까지 갈 때 최단거리를 구하는 것 문제 접근 단계 직사각형의 크기가 있다는 점만 제외하고는 벽과 격자판이 존재한다는 점과 특정 지점까지 이동하는 최단 거리를 구해야 한다는 점에서 대표적인 BFS 문제라는 점이라는 것을 알 수 있다. 중요한 것은 직사각형이기 때문에 체크해야 할 부분이 하나가 아니라 여러 개로 늘어났다. 직사각형 왼쪽 위 칸이 도착 지점으로 가야 하므로, 이 문제..

문제 이해 단계 https://www.acmicpc.net/problem/22946 좌표평면 안에 N개의 원이 존재한다. (1)N개의 원은 모두 겹치지 않는 상태거나, (2)한 원이 다른 원이 내부에 속하거나 (3)두 원이 만나지 않는 경우 로만 존재한다. 이때, 하나의 원 내부에서 다른 원의 내부로 이동하는데, 한 원당 딱 한 번만 방문 가능하다. 좌표평면도 하나의 거대한 원으로 취급하여 방문 가능하다. 이런 조건일 때 한 원에서 다른 원으로 이동할 때, 얻을 수 있는 최대 이동 수를 얻는 문제이다. 문제 접근 단계 한 원을 기준으로 다른 원을 비교한다고 생각했을 때, 두 가지 상태로 밖에 존재하지 않는다. 내부에 있거나 외부에 있거나 둘 중 하나의 경우이다. 위의 문제 조건에서 한 원당 한 번씩밖에 ..

문제 이해 단계 https://www.acmicpc.net/problem/1967 문제가 굉장히 복잡하게 쓰여있는데 사실 간단하다. 노드에서 노드로 가는 데에는 각각의 가중치가 존재한다. 이때, 한 트리의 리프(가장 아래에 있는 노드)에서 다른 리프로 가는 경로가 존재할 것이고, 당연히 각각의 가중치가 존재한다. 이때, 한 리프에서 다른 리프로 가는 경로에서 얻을 수 있는 가중치 합 중 가장 큰 가중치 합을 구하는 문제이다. 예시로 된 그림을 보면 더 이해가 간단히 될 것이다. 문제 접근 단계 리프 노드를 알아내기 위해서는 연결된 노드를 계속해서 타고 들어갔을 때, 마지막 노드는 연결된 노드가 없다. 즉, 해당 노드에서 여러 노드가 연결되어 있다면, 갈림길의 경우의 수를 타고 들어가는 합을 모두 구한 후..

문제 이해 단계 사람이 0부터 N-1까지 넘버링되어 있고, 친구 관계가 A - B - C - D - E 이런 식으로 "하나의 키가 다른 하나의 값이 되는 구조가 4개가 되는 구조가 있느냐" 를 따지는 문제이다. 이를 예시 2번에 나와있는 그림으로 그려보자면 이런 식이다. 여기서 가능한 구조는 (0-3-2-1-4), (4-1-0-3-2), (2-3-0-1-4) 등으로 재방문을 제외하고 방문하는 곳이 4곳 이상이면 된다. 이렇게 생각해 보면 문제 이해는 간단하게 끝난다. 문제 접근 단계 연결된 노드의 개수를 깊이라는 측면으로 가정한다. 또한 어떤 노드의 값이 다른 노드의 키가 되는 것을 보면 DFS로 푸는 것이 더 적절하다고 생각했다. 이 문제에서의 핵심은 어떤 노드에서 시작한 DFS 중, 단 하나라도 연결..