프로그래밍 공부 노트

https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 설명의 편의를 위해 마름모 버튼을 caps lock, 별 버튼을 shift라고 부르자. 문자열을 인접한 대문자 혹은 소문자끼리 묶는다면 아래와 같다. i L ove INHA 위 상황에서, 두 번째 글자인 L을 입력하기 위해 caps lock을 누르게 되면, 다음 글자인 o를 입력하기 위해 다시 caps lock 혹은 shift를 눌러야 하므로 비효율적이다. 즉 길이가 1인 그룹을 입력하기 위해서는 ..

https://www.acmicpc.net/problem/2317 2317번: 결혼식 첫 줄에 N(1 ≤ N ≤ 10000)과 K(1 ≤ K ≤ N, K ≤ 1000)가 입력된다. N은 결혼식에 참가한 사람의 수이고 K는 결혼식에 참가한 사자가족의 수이다. 바로 이어서 (우선순위가 높은 사자부터) 사자가족의 www.acmicpc.net 결혼 축하 기차의 세 인접한 사람 혹은 사자의 키 H1, H2, H3에 대해, H1 H2 > H3이라면 세 키의 차이의 합은 H1 - H3의 절댓값과 같다. 따라서 사자의 키의 최솟값과 최댓값을 알고 있다면, 해당 범위 내에 있는 사람의 키는 결과값에 영향을 주지 못한다. 또, 사자의 키의 범위를 벗어나는 사람들을 키 순으로 정렬한 뒤 한 ..

https://www.acmicpc.net/problem/2024 2024번: 선분 덮기 각 테스트 케이스는 M(1 ≤ M ≤ 50,000) 과 "Li Ri"(|Li|, |Ri| ≤ 50,000, i ≤ 100,000)쌍으로 구성이 된다. 각각은 다른 행으로 분리되어 있다. 입력은 "0 0"으로 끝난다. 모든 입력은 정수이다. www.acmicpc.net 문제 설명만 보면 단순한 라인 스위핑 문제로 착각하기 쉽지만, 사실 이 문제는 일반적인 라인 스위핑처럼 모든 선을 사용하는 문제가 아니다. 예를 들어 두 선 [3, 5]와 [3, 8] 중 한 가지 선분을 사용할 경우 선 [3, 8]을 사용하는 것이 반드시 이득이다. A < P < B일 때, 구간 [0, A]에서 시작하는 선들을 이용해 구간 [0, B]를..

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/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net https://www.acmicpc.net/problem/1931 19..

https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net dfs를 이용해 가능한 경우를 모두 탐색할 수도 있고, 그리디 알고리즘을 이용해 답을 구할 수도 있다. dfs 어느 수에서 8을 없애는 가장 좋은 방법은 해당 수를 직전 수인 7 혹은 직후 수인 9로 만드는 것이다. 0부터 6까지로 만드는 경우는, 8을 7로 만드는 경우가 가능할 때 굳이 셀 필요가 없기 때문이다. 따라서 각 수를 노드로, 각 수에 존재하는 8을 7 혹은 9로 바꾸어 얻을 수 있는 모든 수와의 관계를 에지라고 ..

https://www.acmicpc.net/problem/24229 24229번: 모두싸인 출근길 취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있 www.acmicpc.net 각 판자의 시작점을 pair{ 시작점의 좌표, 1 }, 끝점을 pair{ 끝점의 좌표, -1 } 꼴로 배열에 저장해 정렬하고, 좌표가 같은 pair는 second를 모두 더해 압축한 꼴로 저장한다. 이렇게 하면 각 좌표에서 (시작점의 개수 - 끝점의 개수)를 오름차순으로 정렬된 꼴로 얻을 수 있으므로, 라인스위핑을 이용해 문제를 해결할 수 있다. 우선 문제의 조건을 보면 좌표 0에서 시작하..

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/17224 17224번: APC는 왜 서브태스크 대회가 되었을까? 2019년 올해도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다! 올해 새롭게 APC의 총감독을 맡게 된 준표는 대회 출제 과정 중 큰 고민에 빠졌다. APC에 참가하는 참가 www.acmicpc.net 문제를 역량별로 분류해 풀지 못하는 문제, 쉬운 문제만 풀 수 있는 문제, 어려운 문제도 풀 수 있는 문제로 나눠 그 개수를 센 뒤, 점수를 많이 받을 수 있는 문제부터 해결해 K개의 문제를 푼 뒤 얻은 총점을 출력한다. #include int min(int a, int b) { return a < b ? a : b; } in..