문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 solved.ac 난이도: Gold 3 종만북에 등장하는 변화하는 중간 값 문제와 동일한 문제. 해당 책에서의 트립 알고리즘을 사용하여 트리 내의 몇 번째 원소를 반환하는 코드를 짤 수도 있지만 우선순위 큐만으로 해결가능하다. 우선순위 큐는 부모 노드가 자식 노드보다 큰 값만 가지게 정렬(최대 힙의 경우)되어 있다. 반대로 최소 힙으로 구현된 우선순위 큐는 부모 노드가 ..

문제 https://www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 풀이 solved.ac 난이도: Platium 3 트리에서의 다이나믹 프로그래밍으로 분류되었지만 풀어보니 본인의 풀이에는 다이나믹이 사용될 부분은 없었다. 트리의 모든 경로를 하나 하나 계산하기에는 특정 노드에서 모든 노드 하나하나의 경로 수를 계산해보면 N(특정 노드)*(N-1)(선택한 노드 이외의 모든 노드)의 경로 수가 존재한다. 이..