[알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 1
코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.
Dynamic Programming의 조건
- 최적 부분 구조 (Optimal Substructure) 인가?
- 중복되는 부분 문제 (Overlapping Subproblems)가 있는가?
우리가 풀어야 하는 문제가 최적 부분 구조를 갖고있고, 중복되는 부분 문제들이 있을 수 있다. 이러한 비효율을 해결하기 위한 알고리즘 패러다임이 다이나믹 프로그래밍이다.
다이나믹 프로그래밍을 이해하기에 앞서 최적 부분 구조와 중복되는 부분문제에 대해서 먼저 살펴본다.
1. 최적 부분 구조
최적 부분 구조가 있다는건?
부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것이다
예시1. 피보나치 수 문제
부분문제인 와 의 최적의 답을 이용해서 기존문제인 의 최적의 답을 구했다. 따라서 피보나치 문제는 최적 부분 구조를 갖는다고 볼 수 있다.
예시2. 최단 경로 찾기
서울→부산으로 가는 최단 경로를 풀기 위해서는 서울→H, 서울→I, 서울→J로가는 최단 경로 문제의 답이 필요하다.
부분문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구했다. 따라서 이 문제도 최적 부분 구조를 갖는다.
2. 중복되는 부분문제
다시 한번 피보나치 문제를 보자. 의 문제를 풀기 위해서는 와 의 솔루션이 필요하다고 했다. 그리고 계속해서 부분문제를 나누다보면 아래와 같이 부분문제들이 존재한다.
그림 자세히 보면 중복되는 부분문제가 있다. , , 은 두번 계산된다. 이를 중복되는 부분 문제(Overlapping Subproblem)이라고 한다. 이번 장에서 다이나믹 프로그래밍을 통해 이를 해결할 것이다.
중복되지 않은 부분문제 (None-overlapping Subproblem)
문제를 부분문제로 나눈다고해서 항상 중복되는 부분문제가 존재하는것은 아니다. 합병 정렬(merge-sort)을 보자.
# 기존 문제
merge_sort([16, 11, 6, 13, 1, 4, 10, 7])
# 부분 문제
merge_sort([16, 11, 6, 13])
merge_sort([1, 4, 10, 7]
합병 정렬의 부분문제를 푸는 과정은 서로 독립적인걸 알 수 있다. (중복되지 않는다)
3. Dynamic Programming
앞서 최적 부분 구조와 중복되는 부분 문제에 대해 살펴보았다. 어떤 문제를 다이나믹 프로그래밍을 통해 개선할 수 있는는지 고민된다면 다음과 같이 생각하자.
최적 부분 구조가 있다. → 부분 문제들의 최적의 답을 이용해서 기존 문제를 풀 수 있다.(기존 문제를 부분 문제로 나눠서 풀 수 있다.) → 중복되는 부분문제들이 있을 수 있다.
이러한 중복되는 부분문제를 해결하는것이 Dynamic Programming이다.
Dynamic Programming: 한 번 계산한 결과를 버리지 않고 재활용하는 방식
Dynamic Programming 기법
- Memoization
- Tabulation
4. Memoization
Memoization은 중복되는 계산은 한번만 계산 후 메모하는 방법
피보나치 수에 적용하기
Memoization은 중복되는 계산은 한번만 계산 후 메모하는 방법
에 대한 부분문제들을 아래와 같이 그려볼 수 있다. 좌측 하단부터 계산을 수행해보겠다.
- 을 풀려면 , 를 풀어야 한다. base case이다. 각각의 답을 cache에 저장한다.
- 은 와 의 솔루션을 이용해서 풀 수 있다. 답을 cache에 저장한다.
- 는 과 의 솔루션을 이용해서 풀 수 있다. 과 의 답은 cache에서 가져온다. 과 의 답을 이용해 를 풀고 cache에 저장한다.
- 는 과 의 솔루션을 이용해서 풀 수 있다. 과 의 답은 cache에서 가져온다. 과 의 답을 이용해 를 풀고 cache에 저장한다.
- 는 과 의 솔루션을 이용해서 풀 수 있다. 과 의 답은 cache에서 가져온다. 과 의 답을 이용해 를 푼다.
우리는 각 부분문제를 한번씩만 풀었다. Memoization을 통해 중복되는 부분문제를 해결하였다.
5. Memoization을 이용해 피보나치 문제 풀이
문제
피보나치 수를 찾아주는 함수 fib_memo를 작성하라. Memoization방식으로 구현해야 한다.
def fib_memo(n, cache):
# 코드를 작성하세요.
def fib(n):
# n번째 피보나치 수를 담는 사전
fib_cache = {}
return fib_memo(n, fib_cache)
# 테스트
print(fib(10))
print(fib(50))
print(fib(100))
# 콘솔 출력
55
12586269025
354224848179261915075
풀이
4절의 피보나치에 적용하기 설명을 참고하자.
코드
def fib_memo(n, cache):
# base case
if n <= 2:
return 1
# 답이 cache에 있으면 가져온다.
if cache.get(n):
return cache.get(n)
# 답을 cache에 저장
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
def fib(n):
# n번째 피보나치 수를 담는 사전
fib_cache = {}
return fib_memo(n, fib_cache)
# 테스트
print(fib(10))
print(fib(50))
print(fib(100))
6. Tabulation
우리는 앞서 Memoization을 이용해서 답을 구해보았다. Memoization과 Tabulation의 가장 큰 차이는 어느 값을 먼저 구하는가? 의 접근 방식이다.
다음 그림을 확인해 보자. 피보나치수 을 구하기 위해 를 구해야 하고, 를 구하기 위해 를 구해야 했다. 이는 하향식 접근이라고 볼 수 있다.
Tabulation은 기본적으로 상향식 접근(bottom up)을 기반으로 한다.
다음 표를 보자.
1 | 1 |
2 | 1 |
3 | 2 |
4 | 3 |
5 | 5 |
6 | 8 |
부터 테이블을 채워나가고 있다. 이렇게 하면 반복되는 문제를 수행하지 않아도 된다. 표를 채워나가는 방식이라고 해서 Tabulation이라고 한다.
보통 Memoization은 재귀를 기반으로 하고 Tabulation은 반복문을 기반으로 한다.
7. Tabulation을 이용한 피보나치 수열 문제 풀이
문제
n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성하라. fib_tab은 tabulation방식으로 구현해야 한다.
def fib_tab(n):
# 코드를 작성하세요.
# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))
# 콘솔 출력
55
225851433717
1725375039079340637797070384
풀이
6장의 설명을 참고하자.
코드
def fib_tab(n):
# base case에 해당하는 항은 채워놓는다.
table = [0, 1, 1]
# n번째 피보나치 수까지 값을 채운다.
for i in range(3, n+1):
table.append(table[i-1] + table[i-2]) #
return table[n]
# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))
# 콘솔 출력
55
225851433717
1725375039079340637797070384
Author And Source
이 문제에 관하여([알고리즘 패러다임] 다이나믹 프로그래밍 (Dynamic Programming) - 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@joje/알고리즘-패러다임-다이나믹-프로그래밍-Dynamic-Programming-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)