문제 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 풀이 solved.ac 난이도: Platium 4 DP를 이용한 최소 공통 조상 알고리즘을 사용하여 해결하는 문제. 해당 문제는 LCA 2(11438)와 정점들의 거리(1761)에서 사용한 풀이에서 도로의 최소, 최대를 저장하는 계산만 추가하면 해결할 수 있다. x의 2^k(2의 k승) 번째 조상까지의 최소 도로를 min_road[x][k]라고 하자..

문제 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 트리에는 두 노드의 경로는 유일하다. 두 노드의 쌍을 받은 후 한 노드에서 다른 노드로 직접 이동하며 거리합을 구하는 것이 가장 간단한 해결 방법이겠지만, 어느 경로로 이동해야 다른 노드로 이동할 수 있는지 알 수 없다. 따라서 최소 공통 조상(LCA)을 구하여 각 노드에서의 LCA로의 거리의 합을 구하면 두 노드 사이의 거리를 알 ..

문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 이전 단계 문제인 LCA 와는 다르게 입력의 크기가 크고 제한 시간이 더 짧다. 따라서 최소 공통 조상 알고리즘을 최적화해야 한다. 최적화는 다이나믹 프로그래밍을 이용한 전처리를 통해 LCA를 찾는 시간 복잡도를 O(log Tree_heigth)으로 줄일 수 있다. 이를 위해 x의 2^k(2의 k승)번째 조상을 parent[x][k]..

문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 트리에 속한 두 노드의 최소 공통 조상(Lowest Common Ancestor)을 찾는 문제이다. 동일한 문제이지만 입력의 수가 더 많고 시간제한이 짧은 LCA 2와는 다르게 단순히 구현해도 시간안에 해결할 수 있다. 일단 LCA2를 푸는 기초가 되는 풀이를 살펴보자. 두 노드는 어느 곳에 위치하든 조상 노드로 한 칸씩 위로 올라가다 보면 ..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 트리의 높이를 구하는 것을 응용한 문제. 비슷한 문제를 미리 풀어서 쉽게 해결했다. [알고스팟] FORTRESS - 요새 (C++, 트리) 부모 노드에서 자식 노드로 가는 것은 가중치(cost)가 추가된다. 두 노드 사이의 경로의 비용합이 최대인 것이 트리의 지름이 된다. 지름이 되는 두 노드는 두가지 경우가 존재한다. 1. 루..

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 이진트리의 순회 순서를 공부하기 좋은 문제이다. 이진트리의 순회 순서에는 3가지가 존재한다. 3가지 순회의 이름은 루트 노드를 언제 방문하는지에 따라 지어졌다. 모든 순회는 항상 오른쪽 노드보다 왼쪽 노드를 먼저 방문한다. 1. 전위 순회(preorder traverse): 루트 -> 왼쪽 -> 오른쪽 2. 중위 순회(inorder traverse): 왼쪽 -> 루트 -> 오른쪽 ..

문제 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 solved.ac 난이도: Gold 1 스택을 활용해서 푸는 문제. 해당 문제가 까다로운 이유는 아래와 같다. 문제에서는 A와 B의 사이에 키가 큰 사람이 없다면 서로 볼 수 있다. 즉, 사이에 키가 같은 사람이 껴있어도 서로를 문제없이 볼 수 있다. 현실적으로 눈의 위치가 얼굴의 중간쯤(?)에 있기 때문에 중간에 키가 비슷한 사람이 있다면 앞의 사람을 볼 수 없..

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 solved.ac 난이도: Gold 5 큐를 이용하면 더 쉽게 구현할 수 있는 문제. 큐에 머리가 이동한 위치를 저장하고, 만약 이동한 곳에 사과가 없다면 큐의 앞에서 pop해준다. (꼬리가 줄어듬) 단, 머리가 움직인 곳에 꼬리가 있더라도 결국 꼬리는 다음 칸으로 이동해야하므로 게임 오버가 아님을 주의하자. 뱀의 이동방향의 경우 아래와 같이 mod연산으로 구현하였다. (오른쪽(0) 부터 시계..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 solved.ac 난이도: Gold 4 스택 자료구조로 해결 가능한 문제. 수열의 뒤에서부터 차례대로 진행하면 해결할 수 있다. 수열의 크기가 arr_size라 할 때 수열(arr)의 가장 마지막 수는 오큰수를 가질 수 없으므로 nge(arr_size-1)= -1을 저장하고 스택에 해당 수, arr[arr_size-1]를 넣고 시작하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..

문제 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 solved.ac 난이도: Silver 2 굳이 스택으로 풀지 않아도 되지만 스택으로 분류되어 있어 스택으로만 해결하려 하다 보니 코드가 복잡해진 것 같다. 일단 가장 높은 기둥(8번 기둥)의 왼쪽 부분만 생각해보자. 만약 기둥의 높이마다 지붕을 맞춘다면 5번 기둥에서 지붕이 낮아지고 8번 기둥에서 다시 높아진다면 오목한 부분이 생겨 비가 고이게 된다. 따라서 최장 기둥..