DP가 무엇인지 DP 문제를 어떻게 해결하는지 공부한 뒤로 약 일주일 정도 백준에서 20개 정도의 DP 문제를 풀어보았다.
결론부터 말하자면 전보다는 확실히 늘었지만 아직 수많은 연습이 필요하다는 점을 뼈저리게 느낄 수 있었다.
1. DP 문제들의 공통점
아직은 쉬운 문제들(백준 난이도 기준 Silver 이하)만 풀어봐서 그런지는 모르겠지만 정말 기본 개념에 충실한 문제들이 대부분이다. (물론 이 중에도 해결하지 못하고 구글링한 문제들이 많음 ㅠ)
1.1 상태 및 관계의 중요성
문제의 상태를 정의하고, 이 상태간의 관계를 잘만 찾으면 정말 모르겠는 문제들도 몇 줄 안되는 코드로 해결되는 것을 볼 수 있다.
스스로 풀었을 때 관계를 찾고 적용하기 힘든 대부분의 문제들은 보통 여러 개의 예외 조건들이 존재하거나, 관계를 파악하기 힘든 문제들이 많았다.
문제를 풀다가 어? 이런 반례가 있네? 하면 반례들을 모두 해결하려기보다 깔끔하게 다른 해결 방법을 찾는 게 최선인 듯 싶다.
분명 이전에 풀었던 문제와 비슷한 해결 방식인데도 또 다른 예외가 존재하는 문제
백준 - 포도주 시식
1.2 규칙 찾기의 중요성
문제에서 규칙을 알려주는 경우 쉽게 풀 수 있지만 그렇지 않은 경우는 직접 머리를 굴려가며 규칙을 찾아야 한다.
수열만 잘 살펴보면 규칙이 잘 나오는 경우
백준 - 파도반 수열
: 수열과 그림만 잘 살펴보면 규칙이 보인다.
규칙을 찾기 힘들었던 문제
백준 - 퇴사
: 방향의 전환도 필요하고 dp 배열에서 규칙도 잘 찾아야 한다.
백준 - 가장 긴 증가하는 부분 수열
: 개인적으로 굉장히 좋은 문제라고 생각. 대소 관계를 생각하면서 진행해야 함.
또한 문제 내에서 최대 최소 경우의 수 키워드가 보이거나, 상태 간의 관계 가 어렴풋이 보인다면 DP로 풀면 될 것 같다.
2. 피드백
DP 카테고리로 분류된 문제들만 풀어서인지는 모르겠지만 왜 이 문제가 DP인지는 어느 정도 알아챌 수 있다.
이전 같으면 원시적으로(접근 방법 따위 무시하고 절차적으로) 접근하다가 결국 앓아 누웠을 문제들도 상태와 관계를 보려는 노력을 많이 하고 있다.
물론 아직 한참 멀었다. 문제를 이해하지 못하는 경우도 종종 있고, 방향에 얽매이거나, 관계를 찾지 못하는 경우도 자주 있다.
그래도 하다보면 내 실력은 점점 성장해 간다. 문제 풀이 시작 전만 해도 DP가 무엇인지, memoization tabulation이 뭔지도 모르던 나였다.
다시 가다듬고 내 것이 될 때까지 해보자!
