[개념] - 다이나믹 프로그래밍(DP)
📌 - 중복되는 연산을 줄이자
최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제가 있다.
컴퓨터 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다.
❗️- 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다.
메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법이 바로 다이나믹 프로그래밍이다.
👉 대표적인 예시 - 피보나치 수열
- n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
- 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
피보나치 수열을 재귀함수로 만들 수 있지만, 매번 반복 계산하도록 하면 문제를 효율적으로 해결할 수 없다.
👉 다음 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
다이나믹 프로그래밍은 메모이제이션을 사용해서 해결 할 수 있다.
📌 - 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모리 결과를 그대로 가져오는 기멉을 의미한다.
메모이제이션은 값을 저장하는 방법으로 캐싱이라고도 한다.
피보나치 수열을 메모이제이션을 이용해서 구현하면 다음과 같다.
# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
#이미 계산한 적이 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x-1) + fibo(x-2)
return d[x]
print(fibo(99))
재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법
- 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운방식
- 단순히 반복문을 이용하여 소스코드를 작성하는 경우 바텀업방식
바텀업 방식으로 푼 피보나치 수열
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 2
n = 99
# 피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
print(d[n])
문제를 푸는 첫 번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.
특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.