동적 계획법 (Dynamic Programming, DP)
date
Apr 18, 2024
slug
dynamic-programming
status
Published
tags
Algorithm
summary
type
Post
컴퓨터의 연산 속도는 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문에 이러한 자원들을 최대한으로 활용하는 효율적인 알고리즘을 작성해야 한다.
→ 이러한 방법을 다이나믹 프로그래밍이라고 한다.
→ 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
예를 들어 피보나치 수열을 재귀로 구현한 후
f(6) 을 호출한다고 했을 때 반복되는 연산 과정이 존재한다.
→ 아래 사진은 f(3)이 여러 번 나오고, f(3) 을 구하기 위해 f(2), f(1)도 계속 호출된다.
→ f(100) 을 호출한다면 어떻게 될까?
이때 반복되는 계산 결과를 저장하고 이를 재활용하는 방법인 메모이제이션을 사용한다면 효율적인 계산이 가능하다.
컴퓨터 계산 속도가 빨라지는 것과는 무관하게 알고리즘의 효율성이 왜 중요한 고려사항인지 피보나치 예시를 통해 명확히 알 수 있다. - 알고리즘 기초, p16
이렇게 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제에서 구한 정답을 큰 문제에서도 동일하여 활용할 수 있을 때 다이나믹 프로그래밍이 가능하다. - 분할 정복 (Divide and Conquer)
재귀를 사용하는 방법을 탑다운 방식(하향식)이라고 한다. 큰 문제를 해결하기 위해 작은 문제를 호출하기 때문이다.
그리고 반복문을 사용하여 작은 문제부터 답을 도출하는 방법을 바텀업 방식(상향식)이라고 한다.
계산 결과를 DP 테이블(저장용 리스트)에 저장하여 반복적인 계산을 하지 않는다.
책에서는 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이라고 한다.