[TIL] 다이나믹 프로그래밍 Dynamic Programming, DP
다이나믹 프로그래밍 Dynamic Programming, DP
복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다, '기억하며 풀기'
1. 알고리즘 기법
문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획
2. 알고리즘 설계 기법
문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식
다이나믹 프로그래밍 사용 조건
Overlapping Subproblems 겹치는 부분 문제
DP 는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구하기 때문에
동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다
Optimal Substructure 최적 부분 구조
부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다
부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP 를 사용하게 된다
다이나믹 프로그래밍 문제 해결 방식과 코드 구현
참고) 피보나치 수열 Fibonacci Sequence
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2), (n >= 2)하향식 Top-Down, Memoization 방식
큰 부분에서 작은 부분으로 내려가는 것
n = 5 일 때, memo[n] 의 n 은 5부터 n-1 과 n-2 로 줄어들며 Top-Down 형식으로 답을 찾아낸다
# 피보나치 수열을 재귀 + 메모이제이션으로 정리
def fibonacci(n, memo):
if n in memo: # 이미 계산된 값이 있다면 그 값을 반환
return memo[n]
if n <= 1: # 기저 사례, n == 0 or n ==1
return n
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
if __name__ == '__main__':
n = int(input())
print(fibonacci(n, {}))큰 문제를 작은 하위 문제로 나누어 해결하는 방식
재귀 함수를 사용하여 문제를 작은 부분 문제들로 쪼개고, 중복 계산을 피하기 위해 이전에 계산한 값을 저장
Memoization - 캐싱을 통해 이전 계산 결과를 저장하여 중복 계산을 피하는 것을 의미
코드의 가속성은 높아지지만, 많은 스택 메모리를 사용할 수 있으며 처리 오버헤드가 존재할 수 있다
상향식 Bottom-Up, Tabulation 방식
작은 부분에서 더 해서 큰 부분으로 가는 것
n = 5 일 때, result[i] 의 i 는 2부터 n+1 까지 Bottom-Up 형식으로 답을 찾아낸다
# 피보나치 수열을 반복문 + 테이블으로 구현하기
def fibo_bottom_up(n):
if n <= 1: # 기저 사례, n == 0 or 1
return n
result = [0] * (n+1) # 결과 테이블
result[1] = 1 # 초기값 설정
for i in range(2, n+1):
result[i] = result[i-1] + result[i-2] # 이전 두 값 합산
return result[n] # n번째 피보나치 값 반환
if __name__ == '__main__':
n = int(input())
print(fibo_bottom_up(n))가장 작은 하위 문제들부터 시작하여 큰 문제를 해결하는 방식
반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장
코드의 가독성은 낮아질 수 있지만, 많은 반복문을 이용하기 때문에 스택 메모리를 사용하지 않아
메모리 절약 효과가 있으며, 처리 오버헤드가 없다, 입력 값이 큰 경우 Bottom-Up 방식이 더 효율적
+ 그리고 재귀 함수로 구현하는 방법까지 3개가 있다고 한다
이건 문제를 풀면서 다시 익혀 보려고 한다
다이나믹 프로그래밍 코드 구현
분할 정복 Divide and Conquer 과의 차이점
분할 정복과 동적 프로그래밍 모두 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같지만
분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다
예를 들어, 병합 정렬 Merge Sort 를 수행할 때 작은 하위 문제로 쪼개지지만 중복하여 하위 문제가 발생하지 않는다
분할된 부분 부분은 모두 독립적이고, 동일한 부분을 중복하지 않기 때문에 동적 프로그래밍에 적합하지 않다
피보나치의 경우에는 n 이 어떤 수이든, 그 하위 수를 구하는 부분은 중복해서 나타나기 때문에 동적 프로그래밍으로 해결이 가능하다
DP 에서 중요한 건
1) 점화식
2) 작은 문제의 값들을 재활용
3) 결과를 저장할 자료 구조
참고한 블로그
https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming