[알고리즘] 동적계획법(Dynamic Programming)이란?

* 한국외국어대학교 신찬수 교수님의 알고리즘 강의를 들으면서 정리한 내용입니다. 교수님의 강의와 유튜브, 강의 노트를 참고하여 정리했습니다. 

 

dp 알고리즘이란?

동적 계획법이란 복잡한 문제를 겹치는 부분 문제로 분할하여 
분할된 문제의 해답을 기록하고 더 큰 문제를 해결할 때 재사용하는 일종의 접근 방식이다. 

 

 

일반적인 재귀 함수 문제나 분할정복과 비슷한 면이 있지만,

한번 계산한 결과를 dp 테이블에 저장해놓고

다음번에 필요한 경우 dp테이블에서 참조하여

사용하기 때문에 반복되는 계산을 피할 수 있어 효율적임.

---

언제 dp알고리즘을 사용하는가?

1. 겹치는 부분문제로 나뉘어지고

2. 최적부분구조를 가지고 있을 때 : 부분문제에서 구한 최적 결과가 전체 문제에서도 최적 결과를 낼 수 있는 경우

 

=> 문제를 만났을 때 

1. 부분 문제로 쪼개지는가? -> 일반화시켜서 n번째 생각해보기
2. 겹치는 부분문제여서 앞의 값을 재사용할 수 있는가?
3. 쪼갠 부분 문제의 해답이 전체 문제의 해답에 유효한가?

 

---

 

어떻게 dp알고리즘을 사용하는가?

 

* 메모이제이션 (Memoization) 

-> 값을 기록하고, 그 기록한 값을 참조하는 것

-> 재귀함수 이용

-> 탑다운 방식

 

* 테이뷸레이션 (Tabulation)

-> dp table에 for문 이용하여 순서대로 채워나가는 방

-> for문 이용

-> 바텀업 방식

 

1. 해답의 구조를 파악해 어떻게 subproblem(부분문제)으로 나눌 지(최적 부분 구조 만족하도록) 결정한다. -> 일반화된 n번째에 대한 생각

2. 부문제의 해답을 어떻게 조합해 더 큰 문제의 해답을 만들 수 있는지 식을 마련한다. -> 점화식 표현

3. 점화식에 따라 해답을 계산하여 dp 테이블을 채워 나간다. Memoization & Tabulation

---

 

dp알고리즘 예시

• Fibbonacci 수 계산하기
• 계단 오르는 경우의수
• 도미노 타일링
• 최대합 계산하기
• zig-zag 수열
• LCS(최장공통부문자열)계산하기
• 편집거리 문제
• 괄호 만들기
• LIS(최장증가부수열)