[이코테/C++] 6. 다이나믹 프로그래밍 / 동적 계획법 / Dynamic Programming

목차

출처
개념
vs 분할정복
예제문제

 

---

출처

(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

 

(이코테 2021 강의 몰아보기) 6. 다이나믹 프로그래밍

 

---

개념

• 보텀업(상향식) 방식

 

[필수 조건]

1. 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나누기 가능
• 작은 문제의 답을 모아서 큰 문제 해결 가능

2. 중복되는 부분 문제 (Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결 가능

 

[방법 : 메모이제이션 활용]

• DP 테이블 (결과 저장용 리스트) 생성

메모이제이션
- 캐싱(Caching)이라고도 불림
- 한 번 계산한 결과를 메모리 공간에 메모함
- 탑다운(하향식) 방식

---

VS 분할정복

공통점

• 최적 부분 구조일 때 사용 가능

차이점 : 부분 문제의 중복

• DP : 중복됨. 서로에게 영향 줌
• 분할 정복 : 동일 부분 문제가 반복적으로 계산 X

---

예제 문제

 

[백준]

피보나치 시리즈