동적 계획법의 원리와 구현 방식
- 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 작은 문제들이 반복돼 나타나고 사용되며, 이 작은 문제들의 결괏값은 항상 같아야 한다.
- 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모제이션(memoization) 기법이라고 한다.
- 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.
1. 동적 계획법으로 풀 수 있는지 확인하기
2. 점화식 세우기
3. 메모제이션 원리 이해하기
4. 톱-다운 구현 방식 이해하기
- 위에서부터 문제를 파악해 내려오는 방식
- 주로 재귀함수 형태로 구현
- 코드의 가독성이 좋고 이해하기 편함
5. 바텀-업 구현 방식 이해하기
- 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식
- 주로 반복문의 형태로 구현
톱-다운 VS 바텀-업
- 바텀-업이 좀 더 안전함
- 톱-다운 방식은 재귀 깊이 깊어지면 런타임 에러 발생 가능
나의 생각
동적계획법 문제를 풀다 보면 바텀-업 방식으로 구현할 일이 많은 것 같다.
점화식을 세우는 것이 중요한 것 같다.
점화식을 잘 세우는 친구에게 점화식을 잘 세우는 방법을 물어봤었는데, 처음에는 하나 하나 숫자를 쓰면서 규칙을 찾아보라고 조언해줬다.
출처
Do it 알고리즘 코딩 테스트 파이썬 편
