거창한 시작

www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 알고리즘 종류 트리 다이나믹 프로그래밍 사고 과정 앞서 풀어본 이 문제와 이 문제를 통해 아주 쉽게 풀 수 있었습니다. 독립집합 문제입니다. 독립집합이 되기 위해서는 A마을이 선택되면 연결된 다른 마을들은 선택되면 안됩니다. 반대로, A마을이 선택되지 않으면 연결된 다른 마을들은 선택되거나 선택되지 않아야 됩니다. 이러한 문제를 독립집합이라고 하는 것 같습니다. 따라서 DP로 풀면 될 것 같습니..

www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 알고리즘 종류 트리 다이나믹 프로그래밍 사고 과정 이 문제는 제가 바로 이전에 풀어보았던 문제와 유사했습니다. 독립집합이 되기 위해서는 A가 선택되면 연결된 다른 노드들은 선택되면 안됩니다. 반대로, A가 선택되지 않으면 연결된 다른 노드들은 선택되거나 선택되지 않아야 됩니다. 이러한 문제를 독립집합이라고 하는 것 같습니다. 따라서 제가 배운 DP로 풀면 될 것 같습니다. 조건은..

www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 알고리즘 종류 트리 다이나믹 프로그래밍 (DP) 사고 과정 우선순위 큐를 이용해서 시도를 해봤지만, 해결할 수 없었습니다. 이 분의 블로그를 통해서 도움을 얻을 수 있었습니다. 그러나 어떻게 DP를 사용할 생각을 떠올렸는지는 알 수가 없었습니다. 이후에 다시 보고 해결해 보겠습니다. 이 문제를 보고 왜 DP로 풀어야 하는지 알 수 있었습니다. 트리의 독립집합 문제 유형으로 DP로 풀 수 있었습니다. 문제에..

www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 알고리즘 종류 - 트리 사고 과정 - 노드에 맞춰 열의 번호가 매겨진 것을 보면 중위 순회임을 알 수 있다. 따라서 중위 순회를 하면서 각 층의 최소값과 최댓값을 구해주면 된다. - Root는 항상 1이 아니다. 예제에서 Root가 1로 제시되었지만, 어디에도 Root가 1부터 순서대로 입력된다는 말은 없다. 따라서 Root 노드를 찾아야 한다. 1. 입력으로 부모노드, 자식노드1, 자식노드2..

www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 이 문제에서 중요한 조건은 재방문 처리이다. 특히 아래와 같은 상황이다. 시작점 S에서 빨간색 선으로 이동하고, 초록색선으로 이동한다. 이 때 초록색 화살표 끝의 X에서는 어떻게 재방문을 처리해야 할까? - 일단, X를 구별할 수 없으니 번호를 붙여주기로 했다. - 이제 비교해볼 상황이 있다. 1. 0을 방문했고 다시 0으로 오는 경우 2. 0을 방문했고 ..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 - 위상정렬 사고 과정 - 순서가 있는 일을 순서대로 나열하는 문제이므로 위상정렬으로 풀 수 있다. - 가능하면 쉬운 문제부터 풀어야 하므로 우선순위 큐를 이용해서 작은 번호 문제를 먼저 오게 할 수 있다. - 문제의 예시로 과정을 설명해 보겠다. * 3번 보다 1번을 먼저 풀고, 4번 보다 2번을 먼저 풀어야 합니다. * 초기에 진입차수가 0인 번호..

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 알고리즘 종류 - 우선순위 큐 사고 과정 - 카드의 합이 작은 것부터 합치면 된다. * 10 20 40의 카드를 합칠 때에 큰 카드부터 합치기 시작하면 큰 카드의 숫자를 중복해서 합치게 된다. 예시) (20 + 40) + (60 + 10) = 150이 나온다. 여기서 60은 40과 20의 합이다. 따라서 작은 수부터 더하면 된다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13..

www.acmicpc.net/problem/1400 1400번: 화물차 입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 2 www.acmicpc.net 알고리즘 종류 - 구현 - BFS 사고 과정 - 이동 조건 * 차량은 이동하거나 제자리에 머물기 가능 * 교차로에 진입할 때, 이동가능한 방향일 때만 이동 가능 - 신호등 * 남북 또는 서동 방향으로 주기적으로 신호등이 변함 - 위 조건을 보고 생각한 내용 * Queue의 사이즈로 while문을 돌려서 시간을 더해가자 * Queue에는 위치 y, x만 넣자 * 신호등을 만났을 때 처리할 배열은 state..

www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 알고리즘 종류 - MST - Prim 사고 과정 - 모든 노드를 최소 비용으로 연결하는 MST 문제이다. 그런데 간선 기준이 아닌 노드 기준으로 탐색되고 있다. 따라서 Prim 알고리즘을 사용한다. 구현(C++) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include ..

www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 알고리즘 종류 - 다익스트라 사고 과정 1. 검문을 하지 않을 때, 최단경로를 구한다. 1-1. 최단 경로를 저장한다. 저장하는 방법은 parents 배열을 이용해서 부모 노드를 기록한다. 2. 최단 경로에 있는 노드를 막고, 다익스트라를 수행한다. 2-1. 구해진 최단 경로 비용이 무한대이면, -1 출력 2-2. 구해진 최단 경로 비용 - 검문하지 않은 최단 경로 비용 출력 구현(C++) 1 2 3 4 5 6 7 8..