프로그래밍 공부 노트

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 한 그래프에 대해 여러 경로를 물어보는 문제이므로 플로이드-워셜 방식으로 풀 수 있다. #include #define MAX_N 200 int main () { // map[i][j]: 도시 i에서 도시 j로 이동이 가능하다면 true, 아니라면 false bool map[MAX_N][MAX_N] = {{ 0, }}; // N: 도시의 수, M: 여행 계획의 경로 길이 // from, to: 각 ..

https://www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 기본적으로 문제 자체는 구슬 탈출 2와 같은 문제이다. 단 이 문제는 기울일 수 있는 최대 횟수가 정해져 있지 않으므로, 각 상태에 도달할 수 있는 최소 기울임 횟수를 따로 저장하여 중복되는 경우의 수를 최대한 쳐내야 한다. #include typedef unsigned int ui; #define MAX_N 10 #define INF 0xffff..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 구역의 개수는 최대 10개이다. 구역을 두 종류로 나누는 모든 경우의 수는 2 ^ 10 - 2 = 1022(개)이고, 각 지역구가 인접한 지역만으로 이루어져 있는지는 각 지역에 대해 인접한 지역을 탐색해 확인할 수 있으므로 이 때의 시간 복잡도는 10 ^ 2 = 100, 각 지역구의 인구수 차이는 선형 시간이 소모되므로, 지역구를 이루는 모든 경우의 수를 매우 빠른 시간 안에 계산할 수 있다. #include type..

https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 철저한 구현 문제이다. 각 플레이어가 보스가 있는 장소까지 1초에 한 칸씩 이동한 뒤 1초에 한 번씩 dps만큼의 데미지를 넣는 문제인데, 특별한 알고리즘이 사용되는 것이 아니므로 HP가 양수일 동안 루프하며 각 플레이어의 이동 및 데미지 계산을 진행하면 된다. #include #include #include using namespace std; t..

https://www.acmicpc.net/problem/6597 6597번: 트리 복구 창영이는 바이너리 트리를 매우 좋아한다. 그가 가장 좋아하는 게임은 바이너리 트리를 만들고, 노드에 알파벳 대문자를 하나씩 쓰는 것이다. 같은 알파벳을 여러 노드에 쓰지 않는다. 아래는 www.acmicpc.net 전위 순회에서 루트 노드는 맨 앞, 즉 0번째 인덱스에 존재하고, 중위 순회에서 왼쪽 서브 트리와 오른쪽 서브 트리는 루트 노드를 중심으로 나뉘어져 있다. 즉 전위 순회에서 얻은 루트 노드를 중위 순회에서 찾을 수 있다면 왼쪽 서브 트리와 오른쪽 서브 트리의 길이를 얻을 수 있고, 이를 이용하면 전위 순회에서 왼쪽 서브 트리와 오른쪽 서브 트리를 찾을 수 있다. 루트 노드와 왼쪽 서브 트리, 오른쪽 서브 ..

https://www.acmicpc.net/problem/10478 10478번: 단위 과학에서 단위는 어디에서나 존재한다. 물리에서 단위는 거리(미터, 키로미터 등), 무게(키로그램, 그램 등), 그리고 다른 많은 양을 측정하는데 사용한다. 컴퓨터 과학자들은 용량의 단위(키로 www.acmicpc.net 각 단위를 노드, 단위 간의 배율을 에지로 보면 이 문제는 가장 큰 단위, 즉 루트 노드에서 다른 노드로의 배율을 각각 출력하는 문제이다. 단 루트 노드가 존재하더라도 어떤 노드가 루트 노드인지 입력만 가지고는 알 수 없으므로, 플로이드-워셜을 이용해 모든 노드에서 모든 노드로의 배율을 계산한 뒤 가장 큰 배율을 가진 노드를 루트 노드로 간주한다. #include #include #include usi..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 칸과 칸 사이를 이동할 때 현재 칸보다 낮은 높이로만 이동하므로, 한 번 방문했던 칸을 다시 방문하려면 낮은 칸에서 높은 칸으로 이동해야 하므로 모순이 되어 같은 칸을 두 번 이상 방문할 수 없다. 또한 한 칸에 도달하려면 인접한 칸에서 현재 칸으로 이동해야 하므로, 현재 칸으로 이동하는 경우의 수는 인접한 칸 중 현재 칸보다 높이가 높은 칸으로 이동하는 경우의 수의 합과 같다. 즉 각 칸을 노..

알고리즘에서 그래프는 노드(정점)과 에지(정점을 연결하는 선)으로 이루어져 있는 일종의 도형을 의미한다. 알고리즘 문제 풀이에서 가장 많이 나오는 유형이며, 또 가장 기초적인 개념이기도 하다. 에지는 양방향일 수도 있고 단방향일 수도 있다. 예를 들어 위 그림에서는, 1번과 2번을 잇는 에지는 양쪽 방향으로 모두 이어져 있지만, 1번과 4번을 잇는 에지는 1번에서 4번으로 이어져 있지만 4번에서 1번으로는 이어져 있지 않다. 그래프가 주어지는 문제에서는 대부분 이 그래프를 탐색하기를 원하는데, 이 때 사용되는 방법이 바로 DFS와 BFS이다. DFS와 BFS는 그래프를 탐색하는 아주 기초적인 방법으로, 시작 노드를 하나 정한 뒤 이동 가능한 노드를 순차적으로 탐색하는 방법이다. 이 때 DFS는 스택을 사..

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 트리의 어느 한 노드를 칠한 경우 해당 노드의 모든 자식 노드 역시 칠해지므로, 색칠하는 횟수를 최소화하기 위해선 부모 노드를 먼저 칠한 뒤 트리를 탐색하며 색을 칠하면 된다. 즉 트리를 칠하는 최소 횟수를 구하려면, 각 노드의 색과 트리 구조를 입력받은 뒤 트리를 순회하면서 부모 노드와 색이 다른 자식 노드의 개수를 세면 된다. 이 때 1번 노드, 즉 루트 노드 역시 색이 칠해질 수 있..

https://www.acmicpc.net/problem/18232 18232번: 텔레포트 정거장 첫 번째 줄에 정수 N, M이 공백으로 구분되어 주어진다. (2 ≤ N ≤ 300,000, 0 ≤ M ≤ min(N×(N-1)/2, 300,000)) 두 번째 줄에 정수 S, E가 공백으로 구분되어 주어진다. (1 ≤ S, E ≤ N, S ≠ E) 그 다음 줄부터 M www.acmicpc.net 각 점을 노드로, 텔레포트 혹은 이웃한 점으로 이동하는 것을 에지로 본다면 이 문제는 bfs를 이용해 그래프를 탐색하는 문제로 볼 수 있다. #include #include #include using namespace std; #define MAX_N 300000 // visit[n]: 노드 n에 방문했다면 true..