알고리즘 공부방

문제 https://oj.uz/problem/view/JOI19_naan 문제 보기 - Naan (JOI19_naan) :: oj.uz 문제 보기 - Naan (JOI19_naan) oj.uz 길이 L의 빵이 주어진다. 각 빵은 길이 1 단위로 서로 다른 맛의 소스가 칠해져 있다. 이때 N명의 사람들의 단위 길이의 소스별 행복도가 주어진다. 빵을 정확히 N개의 조각들로 나누어, 각 사람에게 하나씩 조각을 나누어 줄 때, 다음 조건을 만족해야 한다. (전체 빵을 모두 먹었을 때의 행복도)/N

문제 https://oj.uz/problem/view/JOI20_ho_t1 문제 보기 - Just Long Neckties (JOI20_ho_t1) :: oj.uz 문제 보기 - Just Long Neckties (JOI20_ho_t1) oj.uz 길이 $N+1$의 배열 A, 길이 $N$의 배열 B가 주어졌을 때 $1

문제 https://oj.uz/problem/view/IOI19_shoes 문제 보기 - Arranging Shoes (IOI19_shoes) :: oj.uz 문제 보기 - Arranging Shoes (IOI19_shoes) oj.uz 왼쪽 신발과 오른쪽 신발이 여러 개 있고, 각 신발마다 크기가 같은 신발끼리만 짝을 맞출 수 있다. 처음에는 신발들이 막 아무렇게나 섞여 있을 때, 이 신발들을 짝이 맞는 신발들끼리 붙어 있으며, 같은 짝에서는 왼쪽 신발, 오른쪽 신발 순서대로 배열해야 한다. 사용할 수 있는 연산은 인접한 두 신발을 swap하는 연산일 때, 연산의 최소 횟수를 구한다. ($N

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

문제 https://www.acmicpc.net/problem/2343 주어진 수들을 m개로 쪼갤 때 각 CD의 수들의 합의 최댓값을 최소화 시키는 문제이다. 풀이 문제는 매우 간단한 파라마트릭 서치 문제이다. 결정함수에서는 각 CD의 용량이 time 일때 m개 이하로 배정할수 있는지 여부를 반환하면 된다. 당연히 결정함수는 넣을 수 있는것은 최대한 쑤셔 넣는 그리디이다. 이 문제가 나한테 어려웠던 이유는 바로!!!!!! 구현이다. 그리디 부분에서 몇개 값을 건너뛴다거나, 무한루프를 돈다거나 하는 문제가 발생해 한동안 애먹었었는데, 바로 time

문제 https://www.acmicpc.net/problem/2110 주어진 점들중 c개를 골랐을 때 가장 멀리 떨어질 수 있도록 하는 거리를 구하는 문제이다. 풀이 종만북에는 "DARPA" 라는 이름으로 실려 있는 문제이다. 문제가 "최적화 문제" 이니까, 한번쯤은 패러매트릭 서치를 생각해야 정상이다.(!!) 출력해야 하는 답은 "몇 m 떨어지게 설치하는 것이 최대인가?" 이니, 이것을 이분탐색의 인자로 놓고 구현한다. 이제 결정 문제를 풀어보도록 하자. 최소 d m 떨어져 있도록 선택했을 때, c개 이상으로 선택될 수 있는가? 라는 결정 문제이다. 첫번째 위치를 선택해야 될까? 선택하지 않은 해가 있다고 가정하면, 그 해에서 첫번째 값을 빼고 앞의 위치를 선택해도 된다. 그렇다! 그리디가 해법이다...

문제 https://www.acmicpc.net/problem/8980 택배의 목록과 트럭의 용량이 정해져 있을 때 배달할 수 있는 택배의 최댓값을 구하는 문제이다. 풀이 회의실 문제와 비슷하다. 제일 일찍 도착하는 택배 부터 우선순위로 배정해야 한다. 문제를 살짝 변형시켜 s부터 e까지 가는 택배 n개가 있으면 s부터 e까지 가는 택배 1개의 선분이 n개 있는 것으로 생각하자. 이제 회의실에서 동시에 C개의 회의를 할 수 있는 회의실 문제로 바뀌었다. 마찬가지로 가장 먼저 끝나는 택배 S, 최적해 M1, M2, M3, ...가 있다고 하면 M1을 항상 S로 바꿔도 최적해 이므로 성립한다. 따라서 무조건 먼저 끝나는 택배를 우선순위로 선택해야 하며, 원래 문제와 똑같아 진다. 자명하다. *Tip : 내 ..

문제 https://www.acmicpc.net/problem/1449 이 문제 자체보다 다음의 변형된 문제에 주목하자. 회의실 배정 문제처럼 N개의 구간들이 주어질 때 이 구간들을 최소한으로 선택해 그 합집합이 전체 구간을 모두 덮을 수 있도록 해야 한다. 풀이 가장 왼쪽 점을 지나는 구간들 중 가장 오른쪽으로 멀리 뻗어 나가는 구간을 선택한다. 그리디 알고리즘이 아닌 다른 최적해의 구간 M1, M2, ... 이 있다고 가정하자. 이때 가장 왼쪽 점을 포함하는 구간들 중 제일 오른쪽으로 멀리 뻗어 나가는 구간은 S라 하자. M1과 S는 모두 제일 왼쪽 점을 포함하지만, S는 더 멀리 나가니, M1을 S로 바꿔도 최적해가 된다. 자명하다. 시간 복잡도 : $O(N)$ #include using names..