알고리즘 공부방

문제 https://www.acmicpc.net/problem/1648 N*M 크기의 격자판을 2*1 모양의 타일로 채우는 경우의 수를 출력하는 문제이다. 풀이 일단 당연히 비트마스크 dp 문제이다. 더욱 자세한 풀이는 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648 을 참고하자. 이와 같이 각 칸에 번호를 붙이자. solve(pos, mask) = pos 번째 위치 전까지의 번호는 모두 채워져 있고, 비트마스크가 mask 일때 경우의 수를 의미한다. 비트마스크의 표현 범위는 만약 pos 가 15라면 15~20을 표현한다. 21번부터는 표현할 필요가 없음을 알 수 있다. 왜냐하면 21번을 포함하는 타일이 1~14중 하나를 동시에 포함할 수가..

문제 https://www.acmicpc.net/problem/1637 등차수열이 몇개 주어질 때, 그 수열에 나오는 수들 중 홀수번 등장하는 수를 찾는 문제였다. 풀이 이 문제는 종만북에 "캐나다 여행" 으로도 나오고, 2018년 여름학기 계절학교 문제에도 나온 문제이다. 언뜻 봐서는 파라마트릭 서치인지 알 수 없는 문제인데, 이제부터 딱히 어떻게 풀지 모르겠을 때 파라마트릭 서치를 사용하도록 하자. 문제는 간단한데, 홀수개 있는 정수를 어떻게 찾을까? 라는 문제에서, k라는 정수 이하의 정수의 개수를 세보자! 라는 문제로 바꿀 수 있다. 그럼 이걸로 어떻게 홀수개 있는 정수를 알아낼 수 있을까? 바로 누적합의 홀짝성을 이용하는 것이다. x가 홀수개 있는 수라고 하자. x미만의 모든 수에 대해서는 다 ..

문제 https://www.acmicpc.net/problem/3090 주어진 배열의 수들을 t번 감소시킬 수 있을 때 인접한 숫자의 차이의 최댓값을 최소화 하는 문제이다. 풀이 나한테는 많이 어려웠던 문제였다. 지금까지 코드포스에서도 한번쯤은 봤던 문제긴 한데, 파라마트릭 서치라는 생각을 전혀 하지 못했던 것 같다. 이 문제가 파라마트릭 서치라는 생각을 했어야 되는 이유 1. "최적화" 문제이다. 한번쯤은 생각해 봐야지? 2. "이때, 인접한 숫자의 차이의 최댓값을 최소로 하는 프로그램을 출력하시오." "최대값을 최소로", "최솟값을 최대로" 문제이다. 자 이제 파라마트릭 서치로 인접한 숫자 사이의 간격이 diff 이하여야 한다고 구했다고 하자. 과연 그런 해가 존재하는지 결정함수를 어떻게 짜야 할까?..

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

문제 https://www.acmicpc.net/problem/2437 주어진 무게의 추들 중에 몇개를 골라 만들 수 없는 최소의 무게를 구하는 문제이다. 풀이 언뜻 봐서는 dp 문제인듯 하지만, 실제로는 그리디 문제이다. 주어진 추들로 측정할 수 없는 최소 무게를 구하는 것이기 때문에 parametric search 로는 안된다. 핵심은 이를 파악하는 것이다. 정렬된 추의 무게 a1, a2, a3, ... 이 있을 때 S = a1+a2+...+ai-1 까지의 무게는 모두 만들 수 있다고 가정하자. 만약 S+1 보다 ai이 더 크다면 S+1은 어떤 방법으로도 만들 수 없다. 크지 않다면 S+ai까지 모든 무게를 만들 수 있다. 이를 귀납적으로 풀면 된다. 시간 복잡도 : $O(NlogN)$ #includ..