프로그래밍 공부 노트

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

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

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

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/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 라인스위핑 기법을 사용한다. 이 때 입력이 정렬된 순서대로 주어지므로 입력을 정렬하지 않고, 각 선분의 시작점과 끝점을 기존 선분의 끝점의 최댓값과 비교해 입력받은 선분과 기존에 존재하던 선분이 겹치지 않는 부분의 길이만을 더한다. #include using namespace std; #define MIN_X -1000000000 int max(int a, int b) { return a > b ? a : b; } int main() { // 입출력..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다..

https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 두 비밀번호의 각 자리를 2중 for문으로 비교한다고 하자. A의 i번째 자리까지와 B의 j번째 자리까지의 가장 긴 부분 문자열을 str[i][j]라고 했을 때, A[i]가 B[j]라면 str[i][j]는 str[i - 1][j - 1]의 맨 뒤에 A[i]를 추가한 것과 같다. 만일 같지 않다면 이 때의 최장 공통 문자열은 A를 한 자리 줄이거나 B를 한 자리 줄였을 때의 최장 공통 부분 문..

https://www.acmicpc.net/problem/4370 4370번: 곱셈 게임 각 테스트 케이스에 대해서, 백준이가 이길 때는 "Baekjoon wins."를, 동혁이가 이길 때는 "Donghyuk wins."를 출력한다. www.acmicpc.net 백준과 동혁이 항상 최적의 플레이를 하므로, 둘이 사용하는 수는 항상 2와 9뿐이다. 또 여기서 최적의 플레이란, 이기는 사람은 항상 수를 크게 만들고 지는 사람은 항상 수를 최소로 만드는 것이므로, 백준과 동혁이 한 턴씩 번갈아 p에 수를 곱했을 때 나오는 수는 p * 18이고 시작하는 수는 반드시 1이므로 백준과 동혁이 k번씩 수를 곱했다면 나오는 수는 18 ^ k이다. 주어진 수 n이 백준이 이기는 경우라고 가정하면 백준은 반드시 9를 곱할..