동적 계획법 1 설명에서 배웠던 핵심 내용부터 짚고 넘어가자.
- DP 개념
DP ( 동적 계획법 ) 이란, 문제를 같은 인자를 가지는 작은 부분 문제들로 분할하고 그 부분 문제들을 합쳐 더 큰 문제를 해결해나가며 최종 정답을 구하는 알고리즘을 의미한다. 상하방 부분 문제 간의 관계식을 ==‘점화식'이라고 하며, 더 이상 분할할 수 없는 부분 문제를 '기저사례’라고 한다. 부분 문제들은 인자==를 기준으로 구분하며 같은 인자를 가진 부분 문제는 같은 문제이므로 답도 항상 같다. 만약 같은 인자에서 답이 달라질 수 있다면, 인자를 잘못 설정한 것이다. 또한 부분 문제가 중복되는 경우, 답을 미리 저장(캐싱)해뒀다가 사용하는 식으로 중복 계산을 회피할 수 있는데 이를 '메모이제이션 기법' 이라고 부른다.
- DP 풀이 방법
DP를 푸는 방법은 크게 두가지로 나뉜다. 가장 큰 부분 문제에서부터 시작해 작은 문제로 쪼개나간 뒤 다시 그 문제들을 합치는 식으로 해결하는 방식을 ==‘Top-Down' 풀이라고 한다. 처음부터 기저 사례에서 시작해 그 문제들을 합치는 식으로 해결하는 방식을 'Bottom-Up’== 풀이라고 한다. ‘Top-Down’ 방식은 재귀 호출 형식으로 구현하며, 코드가 직관적이라는 장점이 있다. ‘Bottom-Up’ 방식은 다중 포문 형식으로 구현하며, 실행 속도가 빠르다는 장점이 있다.
이번 단원에서는 좀 더 다양한 ‘인자’들의 예시를 접해보고 그에 따른 점화식을 구하는 연습을 해볼 것이다. 저번 단원의 문제들은 대부분 인자가 하나여서 점화식도 단조로웠으며, 문제에서 어떤 항목을 인자로 삼을지 친절하게 알려줬다. 이번 단원의 문제들은 인자 수가 대부분 2개 이상이고 문제의 분할 구조도 좀 더 복잡하며, 인자를 숨긴다! 직접 인자를 찾아 점화식을 구해보자.
문제 풀이
- 무엇을 인자로 잡아야 할까요? 이제 문제들이 대놓고 인자를 알려주지 않습니다. 스스로 찾아봅시다.
- 부분 문제의 분할 구조를 잘 생각해봅시다.
- 어디서 본 문제 같지 않나요?
- 방향이 증가한 탐색 문제
- 배낭 문제 바리에이션 1
- 취할 수 있는 동작을 잘 파악해봅시다.
- 배낭 문제 바리에이션 2
- 부분 문제간의 경계를 명확히 구분해봅시다.
- 배낭 문제 바리에이션 3
- 문제를 잘 읽고 직관력을 발휘해봅시다.