알고리즘 공부방

문제 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개 이상으로 선택될 수 있는가? 라는 결정 문제이다. 첫번째 위치를 선택해야 될까? 선택하지 않은 해가 있다고 가정하면, 그 해에서 첫번째 값을 빼고 앞의 위치를 선택해도 된다. 그렇다! 그리디가 해법이다...