거창한 시작

www.acmicpc.net/problem/14464 14464번: 소가 길을 건너간 이유 4 첫 줄에 C와 N이 주어진다. 다음 C줄에는 T1…TC가 주어지고, 그 다음 N줄에는 Aj와 Bj(Aj ≤ Bj)가 주어진다. A, B, T는 모두 최대 1,000,000,000인 음이 아닌 정수이고, 같을 수도 있다. www.acmicpc.net 알고리즘 종류 우선순위 큐 정렬 사고 과정 1. 닭의 시간을 오름차순으로 정렬하여 저장합니다. 2. 소의 끝나는 시간을 기준으로 오름차순 정렬합니다. 저는 우선순위 큐를 이용해서 저장했습니다. 3. 소를 하나씩 꺼내서 Ai ~ Bi에 속하는 닭이 있는지 확인합니다. 닭을 확인했으면, 체크합니다. 구현(C++) 12345678910111213141516171819202..

www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 알고리즘 종류 우선순위 큐 사고 과정 우선순위 큐 2개를 이용해서 해결했습니다. 현재 가진 연료로 갈 수 있는 거리까지 이동하고, 이 후에 나타난 주유소까지 도달하기 위한 연료를 지나친 주유소에서 가장 연료를 많이 주는 주유소를 선택하는 방법으로 해결했습니다. 1. 우선순위 큐(pq1)에 주유소 위치와 연료를 저장합니다. 주유소의 주유소의 위치를 기준으로 최소 힙을 만듭니다..

www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 알고리즘 종류 MST 사고 과정 1번 본사는 모든 지사와 연결되어 있기 때문에 제외합니다. 그러면 나머지 노드들을 가지고 MST를 진행하면 됩니다. 입력에서 이미 연결된 노드들이 주어지므로 union_find으로 두 노드의 부모 노드를 합쳐주는 것이 편합니다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 알고리즘 종류 구현 사고 과정 던전을 지나 N번 방에 몬스터를 쓰러트리고 아름다운 공주를 구하기 위한 최소 MaxHP를 구하는 문제이다. 간단하게 이분탐색을 이용해서 해결할 수 있다. 구현(C++) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..

www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 알고리즘 종류 다익스트라 사고 과정 늑대가 움직이는 것이 주목해야 할 부분입니다. '속력 = 거리 / 시간' 공식이 있습니다. 속력이 2배 빠르다는 것은 거리가 같을 때 시간이 1/2배 된다는 것이고, 속력이 1/2배 빠르다는 것은 거리가 같을 때 시간이 2배 된다는 것입니다. 따라서, 늑대가 빠르게 달릴 때는 거리 가중치에 1/2배를 해주고, 늑대가 느..

www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 알고리즘 종류 다익스트라 사고 과정 다익스트라는 한 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘입니다. 이 문제에서는 많은 맥도날드에서 모든 집으로 가는 최다거리와 많은 스타벅스에서 모든 집으로 가는 최단거리의 합을 구하는 문제이다. 많은 맥도날드와 많은 스타벅스를 어떻게 하나의 정점으로 처리할 수 있을까요? 비용이 없는 가상의 맥도날드 노드 한 ..

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..