프로그래밍 공부 노트

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/23349 23349번: 졸업 사진 첫째 줄에 학교가 공지할 것으로 예상되는 혼잡 (장소, 시간대) 쌍을 공백으로 구분하여 출력한다. 이때 시간대는 조건을 만족하는 가장 긴 시간대를 의미한다. www.acmicpc.net 각 촬영을 선분, 촬영의 시작 시간과 종료 시간을 시작점과 끝점으로 보면, 이 문제는 라인 스위핑을 이용해 선분이 가장 많이 겹치는 구간을 찾는 문제이다. 이 때 촬영 장소, 즉 선분의 종류가 문자열로 구분되므로, 라인 스위핑을 위해 각 점을 정렬할 때 선분의 종류를 최우선으로 두어 정렬하면 각 종류 별로 선분을 나누어 저장할 필요 없이 빠르게 라인 스위핑을 실행할 수 있다. #include #include #include #in..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 회의실을 최소로 사용하는 방법은 어느 시각에 동시에 진행되는 회의의 수의 최댓값과 같다. 따라서 라인스위핑을 이용해 동시에 진행되는 회의의 개수를 센 뒤, 이 때의 최댓값을 계산해 출력한다. #include #include using namespace std; typedef pair pii; #define _crd first #define _stat second #define MAX_N 100..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 점수는 곧 각 카드에 쓰인 수의 합이므로, 카드에 쓰인 수의 합을 최소화하려면 카드를 골라 더할 때 항상 그 값이 가장 작은 두 카드를 골라야 한다. 따라서 이 문제는 우선순위 큐를 이용해 모든 연산을 마친 뒤 각 성분의 합을 구하는 문제이다. #include #include using namespace std; typedef unsigned long long..

https://www.acmicpc.net/problem/23350 23350번: K 물류창고 K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 www.acmicpc.net 모든 컨테이너를 컨테이너의 큐 q1에 넣은 뒤, O(n ^ 2)의 시간에 걸쳐 다른 큐 q2에 우선순위의 오름차순으로 정렬되게 넣는다. 그 다음 q2의 모든 컨테이너를 컨테이너의 스택 s1에 넣는데, 이 때 우선순위가 같으면서 무게가 무거운 컨테이너를 스택에 넣을 경우 우선순위가 같으면서 더 가벼운 컨테이너를 컨테이너의 스택 s2에 임시로 넣은 뒤 q2의 컨테이너를 s1에 놓고, 다시 s2의 컨테이..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 이 문제의 입력은 비용이 같은 에지를 노드에 상관없이 한 줄씩 입력하는 형태인데, 이는 최소 스패닝 트리를 만드는 크루스칼 기법과 유사하므로 크루스칼 기법을 이용하면 이 문제를 해결할 수 있다. #include using namespace std; #define MAX_N 500000 // parent[i]: 노드 i의 부모 노드 int parent[MAX_N + 1]; void swap(i..

https://www.acmicpc.net/problem/17225 17225번: 세훈이의 선물가게 첫 줄에 상민이가 선물 하나를 포장하는 데 걸리는 시간 A, 지수가 선물 하나를 포장하는 데 걸리는 시간 B, 어제 세훈이 가게의 손님 수 N(1 ≤ N ≤ 1,000)이 주어진다. 이후 N개의 줄에 걸쳐 1번부 www.acmicpc.net 각 주문을 주문이 들어온 시간 t와 선물의 개수 m을 지닌 구조체로 저장한다고 하자. 입력으로 주어지는 주문들을 포장지 별로 분류하여 시간의 오름차순으로 저장한 뒤, 두 포장지의 주문이 들어온 순서대로 포장한다. 포장이 다 끝나고 난 뒤엔 포장한 주문의 t에 포장하는 시간을 더한 뒤 m을 1 빼고, m이 0이 되면 다음 주문에 대해 같은 작업을 수행하면 충분히 빠른 시..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net unordered_map을 이용해 도메인과 비밀번호를 연결해 저장한 뒤 각 쿼리마다 도메인의 비밀번호를 출력한다. #include #include #include using namespace std; int main() { //cin, cout 사용 시 필히 사용할 것 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NU..

https://www.acmicpc.net/problem/15500 15500번: 이상한 하노이 탑 첫 번째 줄에 원판을 옮긴 횟수 K (0 ≤ K ≤ 12345) 를 출력한다. 다음 K 개 줄에 걸쳐 A B (1 ≤ A, B ≤ 3) 를 출력하는데 A 번째 장대 맨위에 있는 원판 하나를 B 번째 장대 맨위로 옮긴다는 뜻이다. www.acmicpc.net 어느 기둥에 있는 원판 N을 3번 기둥에 옮기기 위해선, 원판 N 위에 있는 다른 원판을 모두 3번 기둥이 아닌 다른 기둥으로 치운 뒤 원판 N을 3번 기둥으로 옮겨야 한다. 이 과정을 가장 큰 원판부터 차례로 진행하면 이상한 하노이 탑 문제를 해결할 수 있다. #include #define MAX_N 123 #define MAX_K 12345 // s..