[4일차] DP

오늘은 내가 제일 싫어하는 유형인 DP에 대한 내용이었다. 나는 다른 유형에 비해서 유독 DP가 어려워한다. 구현 문제 같은 건 자질구레한 예외를 하나씩 처리해가는 게 짜증은 나도 맛은 있는데 반해서 DP는 아이디어를 떠올리지 못하면 손도 못 대겠다. 이름도 억지로 Dynamic Programming이라고 지은 것 너무 싫다. 처음에 들었을 때 도대체 이게 뭐지 싶은 이름이었다. 그래도 편식할 수는 없으니 공부는 해야지...

 

오늘 내용은 이미 학기 중에 들은 내용과 거의 비슷했지만 DP를 조금 스마트하게 처리하는 Brute-Force 방법으로도 생각할 수도 있다는 것을 듣고 신기했다. 사실 지금까지 DP를 BF랑 엮어서 생각해본 적이 없었다. 그런데 조금 생각해보니 맞는 말 같았다. 여러 알고리즘 기법이 있고 각각 동적 계획법이니 완전 탐색이니 분할 정복이니 하지만 결국은 다 주어진 문제를 푸는 방법이고 완전 동적 계획법과 분할 정복은 다르겠지만 그 둘의 경계는 조금 모호한가 하는 생각이 들었다. 

 

오늘 SWEA에서는 3문제를 풀었다. 그런데 2문제는 동적 계획법을 공부해봤다면 한 번쯤은 다 풀어봤을 법한 유명한 문제였다. 오랜만에 다시 풀려고 하니 기억이 잘 안 났다. 그래도 최대한 머릿속에서 끄집어내서 풀었다. 납득할 수 있을 만큼의 시간을 써서 풀어서 나도 이제 DP 내성이 생긴 건가 했지만 마지막 문제에서 그냥 처참히 도륙당했다. 결국엔 SWEA에서 정답자 코드를 볼 수 있도록 되어 있길래 그걸 참고했다. 코드를 보니 아이디어에 자질구레한 잡기술까지 포함해서 나 혼자서는 절대 못 풀었다. 보통 메모이제이션에 사용하는 배열을 2차원으로 사용하고 가끔 3차원까지는 봤는데, 이 문제는 무려 4차원이었다. 코드를 봐도 이게 지금 무슨 소리하는 거지...? 하고 꽤 헤맸다. DP는 진짜 많이 풀어보는 거밖에 답이 없다.

 

이 과정이 끝나고 역량테스트 B형에 응시할 수 있는걸로 알고 있는데... 아.... 나는 힘들지 않을까...? 일단 가는데까지는 가보자.