프로그래밍 공부 노트

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..

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 각 칸에 상어가 있는지 여부를 입력받으며 각 상어의 좌표를 저장한 뒤, 상어가 없는 칸에 대해 상어와의 거리의 최솟값을 계산해 각 최솟값의 최댓값을 출력한다. #include #define INF 0x3f3f3f3f #define MAX_N 50 struct coord { int _y = 0, _x = 0; }; int abs(int n) { return n < 0 ?..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 집의 각 칸을 저장한 배열 map에 대해, map[i][j]에 파이프가 있다고 하자. 만일 map[i + 1][j]가 빈 칸인 경우 파이프를 세로로 움직일 수 있고, map[i][j + 1]이 빈 칸인 경우 파이프를 가로로 움직일 수 있으며, 위의 두 칸과 map[i + 1][j + 1] 세 칸이 모두 빈 칸인 경우 파이프를 대각선으로 움직일 수 있다. 그러므로 집의 각 ..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net bfs를 이용해 가능한 모든 경우를 탐색할 수도 있고, 그리디 알고리즘을 활용해 B를 A로 만드는 연산의 횟수를 구할 수도 있다. - bfs #include #include #define MAX 1e9 using namespace std; int main() { // step: A에서 B로 가기 위해 필요한 연산의 수 // len: 한 step에서 연산이 가능한 수의 개수 int A, B, step = 0, len = 1; // A에서 B로 가는 과정에 존재할 수 있는 수의 집합 queue q; // 문제의 조건을 입력받..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 각 칸에 도착했을 때 사다리 혹은 뱀에 의해 도달하는 칸을 배열 arrive에 저장한 뒤, 칸 i에서 주사위눈 j가 나온 경우 최종적으로 도착하는 좌표를 v[i][j]에 arrive를 이용해 저장한다. 이후 100번 칸에 도착할 때까지 bfs를 시행하면 주사위를 굴려야 하는 최소 횟수를 얻을 수 있으므로 이를 출력한다. #include #include..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1×1 크기의 공간을 노드로, 상하좌우로 인접한 칸 사이의 관계를 에지로 보면 이 문제는 상어의 좌표에서 먹을 수 있는 물고기의 좌표까지 bfs를 여러 번 실행하는 문제이다. 이 때 먹을 수 있는 물고기를 발견한 경우, bfs를 종료하지 않고 같은 거리에 있는 모든 좌표를 탐색해야 한다. #include #include #include using namespace std; #define M..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 각 지역을 노드, 지역 간의 도로와 그 거리를 에지와 그 가중치로 보면, 이 문제는 모든 노드에서 모든 노드로의 최소 비용을 찾는 문제이므로 플로이드-워셜 기법을 이용해 풀 수 있다. 모든 노드에서 모든 노드로의 경로를 찾은 뒤, 각 노드에서 다른 노드로 이동하는 비용이 m 이하라면 아이템을 획득하고, 획득한 아이템의 최댓값을 출력하면 정답이 된다. #include #define MAX_N 100 #d..