PS
1647 - 도시 분할 계획
이 문제에서는 어떤 그래프가 주어질 때, 그 그래프에서 정점을 두 그룹으로 나누면서 그룹 내 정점끼리 이동할 수 있는 경로를 유지하는 간선의 가중치의 합의 최소가 얼마인지 찾아야 한다.
1197 - 최소 스패닝 트리
이 문제는 그래프가 주어졌을 때, 그 그래프의 최소 신장 트리(MST)를 구하는 문제이다. 최소 신장 트리란, 어떤 그래프에 대해 가능한 모든 신장 트리 중에서, 간선의 가중치 합이 가장 작은 트리를 뜻한다. 신장 트리는 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다.
2252 - 줄 세우기
이 문제는 전형적인 위상 정렬 문제이다. 학생 수와 일부 학생들의 키 비교 결과가 각각 주어지면, 이를 바탕으로 학생들의 줄을 세울 수 있는 방법을 구해야 하는 문제이다.
1106 - 호텔
이 문제에서는 호텔의 고객을 C명 이상 늘리기 위해 필요한 최소 금액이 얼마인지 묻는다. 입력으로는 최소한 늘려야 하는 고객인 C와 홍보할 수 있는 도시의 수 N, 그리고 각 도시별 단위 홍보 비용과 홍보 효과(늘어나는 방문인원)이 주어진다.
1987 - 알파벳
이 문제는 보드의 크기와 알파벳이 적힌 보드가 주어졌을 때, 같은 알파벳을 두 번 이상 포함하지 않으면서 가장 멀리 갈 수 있는 경로를 찾는 문제이다.
15681 - 트리와 쿼리
이 문제는 가중치가 없는 트리(루트 포함)가 주어질 때, 정점 U를 루트로 하는 서브 트리(부분 트리)에 속한 정점의 수를 구하는 문제이다.
2467 - 용액
이 문제는 용액의 특성값이 오름차순으로 정렬되어 주어지면, 두 용액을 섞어 특성값이 0에 가장 가깝도록 할 수 있는 특정한 용액 두 개를 찾아야 하는 문제이다.
2166 - 다각형의 면적
이 문제는 다각형을 이루는 점의 좌표가 차례대로 주어졌을 때, 그 다각형의 넓이를 구하는 문제이다.
1967 - 트리의 지름
이 문제는 트리의 정점 수와 간선 정보가 주어지면, 그 트리의 지름을 출력하는 문제이다.
1504 - 특정한 최단 경로
이 문제는 1부터 N까지 이동할 때 u, v를 반드시 거치는 최단경로의 거리를 구하는 문제로 다익스트라를 사용하면 풀 수 있다.