DP 공부

DP(Dynamic Programming, 동적 계획법)

• 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.
• 해당 글은 DP 문제를 만났을 때 접근하는 방법을 정리한 것 입니다.

접근 방법

1. 직접 손으로 풀어보면서 규칙성을 찾아냅니다.
2. dp 테이블을 1차원으로 할지 2차원으로 할지 선택하고 dp[i]가 무엇인지 정의합니다.
3. 초기값을 설정하고, 테이블을 체우는 반복처리를 진행합니다. (점화식을 정의해서 처리합니다.)

규칙성을 찾아내는 과정

• 문제의 종류에 따라 규칙성을 찾아내는 방법이 다르기 때문에 꾸준히 규칙성을 찾는 연습을 통해서 찾아내는 것이 중요합니다.

1. 문제를 보면서 경우를 어떤 형식으로 나눌지 생각합니다.
   • 백준 RGB거리문제에서 빨강을 선택한 경우, 초록을 선택한 경우, 파랑을 선택한 경우로 나눠서 접근했습니다.
   • 백준 계단 오르기문제에서 계단을 안 오른 경우, 한 번에 한 계단 오른 경우, 한 번에 두 계단 오른 경우로 나눠서 접근했습니다.
2. N=1일 때 어떻게 되는지 생각합니다.
   • N=1일 때는 초기값으로 아무런 제약이 없는 상태입니다.
   • 아무런 값을 넣어도 괜찮은 단계이고 이 단계를 통해서 다음 단계에 영향을 주기 때문에 주의 깊게 생각해야 하는 중요한 단계입니다.
3. 가능하면 자신의 규칙을 바탕으로 규칙을 찾아냅니다.
   • 규칙을 찾기 위해 아무런 규칙없이 풀면 경우에 따라 규칙성을 찾기 힘든 경우가 있습니다.
   • 자신의 규칙을 만들어서 규칙성을 찾아내면 범위를 줄여나갈 수 있습니다.
   • 핵심은 처음부터 규칙을 만드는 것이 아니라 적어도 N=3일까지 규칙없이 풀고, 그 다음 자신의 규칙을 붙여서 접근합니다.
   • 백준 2xn 타일링 2문제에서 N=3까지 규칙없이 풀고, 왼쪽 오른쪽에 타일을 붙이는 것이 아니라 오른쪽에 타일을 붙이는 규칙을 세워서 문제를 해결했습니다.

DP 테이블 정의

• 먼저 DP 테이블을 1차원이라고 정의해도 문제가 해결되지 않으면 2차원으로 정의합니다.

참조

• 동적계획법(Dynamic Programming)
• [백준문제집 DP 필수문제 #01] 2747. 피보나치 수 (백준, 파이썬)
• [백준문제집 DP 필수문제 #03] 11727. 2xn 타일링 2 (백준, 파이썬)
• [백준문제집 DP 필수문제 #04] 11057. 오르막 수 (백준, 파이썬)
• [백준문제집 DP 필수문제 #19] 1149. RGB거리 (백준, 파이썬)
• [백준문제집 DP 필수문제 #18] 2579. 계단 오르기 (백준, 파이썬)