[알고리즘 공부] 동적계획법(Dynamic Programming)

[ 컨셉 ]

1. 문제에 대한 접근 방식을 일컫는다

2. 큰 문제를 작은 문제로 나누어 해결해 나가는 것

Q. 분할정복 기법 또한 부분 문제로 나눠 해결하는 과정인데 무엇이 다르지?

• 부분 문제의 중복이 핵심.
• 부분 문제의 중복이 많이 일어나는 문제의 경우, 분할 정복은 해결에 어려움이 있을 수 있다.

 

[ 동적계획법의 종류 ]

1. 하향식 방법 (Top-down)

• 재귀함수를 통해 하위 문제들을 해결해 나가는 방식
• 많은 중복이 발생하는 경우, 재귀적인 풀이는 효율성에 문제가 발생할 수 있다.
• "Memoization"을 통해 해결 된 하위 문제들을 캐싱(Caching)하여 중복을 해결하여 오버헤드를 줄일 수 있음.

 

2. 상향식 방법 (Bottom-up)

• 가장 하위의 문제부터 시작하여 순차적으로 해결해 나가는 방식
• 중복을 피할 수 있으며, 재귀(Recursion)에 의한 오버헤드가 없는 것이 장점이다.

 

3. 예시

• 피보나치 수열(Fibonacci Number) 계산
• 조합(Combination) 문제 해결 등

[ 출처 ]

• Introduction To Algorithms