바킹독 DP 연습문제을 다 풀고 - 느낀점

 

바킹독 선생님은 CP를 위주로 공부했으면서도 강의 및 연습문제는 일반적인 취준생이 준비하는 코딩테스트 수준에 맞춰서 구성한다. 그래서 그런지, DP 문제집도 어려운 DP 대신 기본적인 DP 문제 위주로 구성되어 있다. 풀고나서 느낀점.

 

1. 쉬운 DP는 왠만하면 점화식을 피보나치 문제와 같은 방식으로 일차원 DP로 쉽게 구할 수 있다.

  피보나치 관련 문제는 물론이며, '이친수', '파도반 수열', '01타일'과 같은 문제는 현재 항과 이전 항들간의 관계만 생각하면 식이 금세 나온다.

 

2. 그러나 조금만 어려워지면 (골드5 이상) 유형이 다양해지며, 발상도 문제마다 다르다.

  나는 '자두나무', '타일 채우기'는 스스로 생각하여 풀었지만, '내리막길', '색상환'은 또 못 풀었다. 나는 소위 '양치기' 신봉자인데, dp도 (타고난 재능에서 한계에 도달한다면) 양치기로 모든 유형을 접하는 것이 중요해보인다.

 

3. 여러 가지 웰논 문제들

LIS(Longest Increasing Subsequence)

• 기본 풀이는 O(N^2)로, 각 항마다 이전 항들을 다 둘러보면서 자기 자신보다 작으면서 길이가 가장 긴 항의 값을 찾는다.
• 이를 응용하여, 기록하는 자기 자신보다 작으면서 길이가 가장 긴 항의 위치를 이진 탐색으로 찾으면 O(N^logN)으로 풀 수 있다(현재는 풀이 디테일 까먹음 ㅎㅎ).
• 백준에 '가장 긴 증가하는'으로 검색하면 엄청나게 많은 문제를 풀어볼 수 있다. 예전에 공부해서 다시 복습하고 싶다면, '가장 긴 감소하는 부분 수열'을 풀어보자.

LCS(Longest Common Subsequence)

풀이 발상이 기존의 '쉬운' dp랑 느낌이 달라서 따로 배워둘 필요가 있어보인다.

마찬가지로, 백준에 'LCS'로 검색하면 별 게 다 있으니(경로 추적, 문자열 3개 등...) 풀어보면 될 듯하다.

 

Knapsack

 

 

4. 구간 DP

'팰린드롬?'처럼 이차원 dp에서 dp[S][E]를 '주어진 object O의 S번째에서 E번째까지 어떤 연산을 한 결과'로 주어지는 문제들을 일컫는다.

바킹독 문제집에는 없지만, '행렬 곱셈 순서'가 이 분야에서 가장 유명한 문제가 아닐까 싶다.