프로그래밍 공부 노트

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/21820 21820번: Acowdemia I If Bessie cites her third paper, then the citation counts become $(1,100,3,3)$. As mentioned above, the $h$-index for these counts is $3$. www.acmicpc.net 구조만 놓고 보면 이분 탐색 문제이지만, 탐색 범위가 10^6으로 작은 편이므로, 선형 탐색으로도 답을 충분히 찾을 수 있다. c[i] = 참조된 횟수가 i 이하인 논문의 개수인 배열 c가 있다고 하자. 이 배열을 탐색하여 c[h] >= c인 h의 최댓값을 찾게 된다면, 이 h가 곧 h-인덱스가 된다. 이후 참조된 횟수가 h인 논..

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

https://www.acmicpc.net/problem/23358 23358번: Quack Strikes Back (Easy) Two years ago the IPSC contestants had a hard time to understand a piece of code written in PostScript. Last year wasn't any better as we introduced a queue-based programming language. If you didn't participate last year (and even if you did :), this pract www.acmicpc.net 굳이 따지자면 큐를 쓰는 문제이긴 하지만, 알고리즘 문제라기 보단 CS 문제에 가깝다. 큐와 레..

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/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제에서 필요한 건 지구에 부딪히는 별똥별의 개수의 최솟값, 즉 트램펄린으로 튕겨내는 별똥별의 개수의 최댓값이므로 트램펄린의 정밀한 위치는 신경쓸 필요 없다. 주어진 별똥별 중 별똥별 A와 별똥별 B(이 때 A와 B는 같을 수도, 다를 수도 있다), 그리고 트램펄린의 왼쪽 꼭지점 P에 대해, A의 x좌표와 P의 x좌표가 ..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 특별한 알고리즘을 사용하지 않는 구현 문제이다. 주사위를 객체로 만든 뒤 주사위의 회전을 메소드로 구현하면 쉽게 풀 수 있다. #include #define MAX_N 20 // N: 지도의 세로 크기, M: 지도의 가로 크기 int N, M; // 좌표 class coord { public: // (x, y): (가로, 세로) i..

https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 모든 캐릭터의 레벨을 정렬한 뒤, 레벨이 가장 낮은 캐릭터부터 다음 캐릭터와 레벨이 같게끔 차례로 레벨을 올려주면 된다. #include #include using namespace std; #define MAX_N 1000000 int main() { // 입출력 속도 향상 ios::sync_with_stdio(false..