[5일차] D&C

오늘 내용은 분할 정복에 관한 내용이었다. 강의는 분할 정복을 배우게 되면 거의 무조건 배우는 merge sort, quick sort, binary search에 관해 진행했다. 셋 다 처음 듣는 내용은 아니라 강의는 무난하게 들을 수 있었다. 근데 오늘 올려준 문제들은 쉽지 않았다. 이게 왜 분할 정복 인지도 모르겠다. 내가 다른 방법으로 풀려고 하려고 해서 그런가 도저히 어떻게 쪼개서 풀어야 하는지 감도 안 잡혔다. 

 

총 5개의 문제가 올라왔는데, 일단 3개의 문제만 풀었다. 나머지 두 개는 더 어려운 문제 같다. 내일은 주말이니 내일 풀어봐야지. 근데 3문제 다 순탄치 못하게 풀었다. 알고리즘 문제 유형 중에서 DP를 제일 못하는 줄 알았는데 분할 정복이 복병인가...? 문제를 좀 더 많이 풀어봐야지. 

 

오늘 연구실에서는 OpenCL한테 맞고 삼성 특강에서는 분할 정복한테 맞았다. 더욱 강해져야겠다.

 

추가)

어제 다 못 풀었던 두 문제를 마저 풀었다. 사실 혼자 힘으로 해낸 건 아니라서 정확히 말하면 풀었다고 할 수는 없고 남의 코드를 보고 공부한 거지... 첫 번째 문제는 O(nlogn)의 시간 복잡도를 가지는 정렬 방법을 수정해서 푸는 문제였다. 처음에 merge sort를 수정해서 풀었는데 답이 나오지 않았다. 그런데 수정하는 방법이 틀려서 답이 안 나오던 거였다. 되게 간단한 코드였지만 아마 나는 아이디어를 평생 떠올리지 못했을 것이다 하하.

 

그리고 두 번째 문제는 parametric search라는 방법을 사용하는 문제였다. 얘는 최적화 문제를 결정 문제로 바꿔서 푸는 기법이다. 처음엔 분할 정복 인척 하는 완전 탐색으로 풀었는데 당연히 시간 초과가 나왔다. 이렇게 푸는 게 아니라 이분 탐색과 parametric search를 섞어서 푸는 문제였다. 알고리즘의 답을 검증하는 단계가 다항 시간 안에 가능하면 NP라는 것을 배우면서 내가 알고리즘의 답을 검증하는 코드를 짤 일이 있을까 하며 방심했는데 당했다. 백준에서 이런 문제를 하나 더 풀어봐야겠다.