다이나믹 프로그래밍

< 다이나믹 프로그래밍 = 동적 계획법 >

1. 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법
2. 이미 계산된 결과는 별도의 메모리 영역에 저장
3. 탑다운과 보텀업 두 가지 방식으로 구성

< 다이나믹 프로그래밍 조건 >

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결

< 메모제이션 >

• 한 번 계산한 결과를 메모리 공간에 메모하는 기법 = 이전 계산 결과를 일시적으로 기록해 놓는 넓은 개념

1. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
2. 값을 기록해 놓는다는 점에서 캐싱이라고도 함

< 탑다운 vs 보텀업 >

• 탑다운 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고 함
• 다이나믹 프로그래밍의 전형적인 형태의 보텀업 방식 - 결과 저장용 리스트 = DP 테이블

< 다이나믹 프로그래밍 vs 분할 정복 >

• 다이나믹: 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
• 분할 정복: 동일한 부분 문제가 반복적으로 계산되지 않음

< 다이나믹 프로그래밍 문제 접근법 >

1. 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
2. 다른 풀이 방법이 떠오르지 않을 때 다이나믹 프로그래밍 고려
3. 재귀 함수로 비효율적인 완전 탐색 프로그램 작성(탑다운)
4. 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드 개선

• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음