PS
1753 - 최단경로
전형적인 다익스트라 문제로 정점, 간선의 수와 시작 정점 그리고 간선이 입력으로 주어지며, 이를 입력받아 시작 정점에서 각 정점으로의 최단 거리를 구하는 문제이다.
1043 - 거짓말
이 문제는 여러 개의 파티가 있고 그 파티에 참여하는 여러 사람이 있을 때, 진실을 알고 있는 사람을 피하여 거짓말을 할 수 있는 파티의 개수가 몇 개인지 알아내는 문제이다.
17069 - 파이프 옮기기 2
파이프 옮기기 1과 문제는 같으나 제한시간이 0.5초이고 N이 $3 \le N \le 32$ 범위로 더 커졌다.
17070 - 파이프 옮기기 1
이 문제는 (1,1), (1,2)를 가로 방향으로 차지하고 있는 파이프의 한 쪽 끝을 정해진 방법만을 이용해 (N, N)까지 옮길 수 있는 경우의 수를 구하는 문제이다. 다만 공간에 벽이 있을 경우, 그 벽에 파이프가 닿지 않도록 해야 한다.
13549 - 숨바꼭질 3
이 문제는 두 숫자 N과 K가 주어지고, 이동 방법을 이용해 N을 K로 만드는데 드는 최소 비용(문제에서는 시간)이 얼마인지 구해야 하는 문제이다. 이동 방법에는 두 가지가 있다.
2096 - 내려가기
이 문제는 Nx3칸의 테이블에서 규칙을 따라 내려가면서 얻을 수 있는 최대 점수 및 최소 점수를 구해야 하는 문제이다. 규칙은 다음과 같다. 어떤 줄에서 다음 줄로 넘어갈 때 바로 아래의 수로 내려가거나, 또는 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다.
1916 - 최소비용 구하기
이 문제는 다익스트라 알고리즘을 사용하는 전형적인 문제이다. 다익스트라 알고리즘이란, 가중치가 있는 그래프에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이 문제에서 정점은 도시이고, 간선은 각 도시를 잇는 버스이며, 가중치는 버스 비용이다.
16953 - A → B
이 문제는 시작점 A에서 끝점 B로 가는 최소 연산 수를 구해야 하는 문제이다. 이때 2를 곱하는 연산과 1을 수의 가장 오른쪽에 추가하는 두 가지 연산이 가능하다.
11725 - 트리의 부모 찾기
이 문제는 트리를 입력받은 뒤 그래프 탐색 알고리즘을 이용해 노드 1부터 시작해 인접 노드를 순회하면서, 인접 노드의 부모 노드를 결정하면 되는 문제이다. BFS 또는 DFS를 사용하여 문제를 해결하면 된다.
11660 - 구간 합 구하기 5
이 문제는 2차원 누적 합을 잘 사용해야 하는 문제이다. 문제 내용을 살펴보면, $N \times N$ 크기의 2차원 표를 입력받아 $M$개의 2차원 구간합을 구하는 것이 목표이다. 그런데 만약 표를 입력받아 순회하며 합을 구하는 브루트포스 방식으로 단순히 구현하면 최악의 경우 100000 1024 1024번(1천억 번) 연산하므로 시간초과가 날 것이다...