🛴 DP란?
큰 문제를 여러 작은 문제로 나누어 그 문제의 결과 값을 토대로 해결하고자 하는 알고리즘이다
❗ 분할 정복과의 차이점
분할 정복은 DP와 달리 하위 문제가 중복되지 않을 수도 있다는 차이점이 있다. DP는 계속해서 문제가 중복되는 것을 하술할 메모이제이션을 통해 제거하는 알고리즘이다.
🎞 메모이제이션(Memoization)
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
메모이제이션은 DP의 핵심이 되는 기술이다. 메모이제이션은 작은 문제의 값을 저장하고 이를 바탕으로 큰 문제를 해결해가며 다시 그 문제의 값을 저장, 해당 값을 바탕으로 더 상위에 있는 문제를 해결하는 식으로 활용된다.
📉탑다운(Top-Down)과 📈바텀업(Bottom-Up)
DP에는 크게 탑다운 방식과 바텀업 방식이 존재한다. 탑다운의 경우 가장 큰 문제로부터 출발하여 하위 문제들을 해결하는 방식이고, 바텀업 방식의 경우 가장 작은 문제들로부터 시작하여 전체 문제의 해답을 찾는 방식이다.
📄 코드 (Python)
피보나치 수열
1, 2항의 값은 1이고 그 다음 항부터는 직전 항과 그 전 항을 더한 값이 반복되는 수열
일반적인 피보나치 수열은 다음과 같이 구현한다(python).
def Fibonnacci(x):
if x == 1 or x == 0:
return 1
return Fibonnacci(x-1) + Fibonnacci(x-2)
위 코드(DP를 사용하지 않은 경우)로 Fibonnacci(6)을 구하려고 했을 때, 위에 보이는 트리처럼, 연산의 중복이 여러번 일어나는 것을 확인할 수 있다. 메모이제이션을 활용한다면 메모리 공간을 조금 더 활용하여 중복된 연산을 크게 줄일 수 있을 것이다.
다음은 바텀업 방식으로 피보나치 수열을 구현한 코드다.
N = int(input())
dp = [0]*(N+1)
dp[0],dp[1] = 1, 1
for i in range(2, N+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp)앞선 코드와 다르게dp라는 리스트에 연산 값을 저장하여 메모이제이션을 하면서 중복된 연산없이 피보나치 수열을 구할 수 있게 되었다.
🎯 [BOJ] 1135번 - 뉴스 전하기
