프로그래밍 공부 노트

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/5847 5847번: Milk Scheduling Farmer John's N cows (1

https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 다익스트라를 살짝 변형한 문제이다. 여우에 대해 다익스트라 탐색을 실행하는 경우와 늑대에 대해 다익스트라 탐색을 실행하는 경우를 따로 생각해야 하는데, 늑대에 대해 다익스트라 탐색을 실행하는 경우 오솔길을 홀수 번 이용하는 경우와 짝수 번 이용하는 경우를 나누어서 계산해야 한다. #include #include #include using n..

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/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 한 건물이 최대 3개 건물에 영향을 미친다는 말은, 곧 한 건물은 최대 3개 건물의 필요 조건이라는 말이다. 즉 어떤 건물을 짓기 위해선 4개 종류 이상의 건물을 지어야 할 수도 있다. 모든 종류의 건물의 개수와, 해당 건물을 짓기 위해 더 지어야 하는 건물 종류의 수를 배열에 저장한다고 하자. 즉 건물이 건설되거나 파괴될 때마다 해당 건물 종류의 개수를 1씩 증감..

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

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 각 도시를 노드로, 버스를 에지 혹은 순간이동 혹은 타임머신으로 본다면, 가중치가 음인 에지가 존재하고 가중치가 음인 사이클이 존재하는지 찾는 문제이므로 벨만-포드 알고리즘을 이용해 해결할 수 있다. #include #include #include using namespace std; typedef pair edge; typedef lo..