Dynamic Programming
Dynamic Programming에서 Dynamic programming은 딱히 의미 없는 용어이다. 그냥 Dynamic, 멋있어서 붙인 용어라고 한다. Dynamic programming은 Optimal Substructure(최적 부분 구조)와 Overlapping Subproblem(중복되는 부분 문제)를 만족할때 자주 사용한다고 한다.
Optimal Substructure는 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 결과를 도출하고 그 결과를 모아 큰 문제를 해결할 수 있는 문제를 의미한다. Overlapping Subproblem은 동일한 문제를 반복적으로 해결하는 문제이다.
Fibonacci Sequence
대부분 동적 프로그래밍 예제로서 피보나치 수열을 많이 사용한 것 같다. 피보나치 수열은 동적 프로그래밍으로 계산할 수 있다. 피보나치 수열은 첫번째 및 둘째 항이 1이고 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 의미한다.
피보나치 수열을 파이썬으로, 재귀호출 방식을 통해 구현할 수 있다.
def fibonacci(x):
if x == 1 or x == 2:
return 1
return fibonacci(x - 1) + fibonacci(x - 2)
print(fibonacci(5))
이런 피보나치수열을 다이나믹 프로그래밍으로 해결할 수 있다. 다이나믹 프로그래밍으로 문제를 풀어내기 위해서는 먼저 조건에 만족하는지 화긴을 해보아야 한다.
- 큰 문제를 작은 문제로 나눌 수 있는가? (최적 부분 구조)
- 동일한 작은 문제를 반복적으로 해결할 수 있는가? (중복 부분 문제)
피보나치 수열은 다이나민 프로그래밍 적용 조건에 만족한다.
Memoization
메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다. 이 방법은 한번 계산한 결과를 메모리 공간에 메모하는 기법이다. 즉 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오면서 값을 기록해 놓는 부분에 있어서 caching이라고 부르기도 한다.
TopDown/ BottomUp
다이나믹 프로그래밍의 전형적인 구현 방식은 BottomUp 방식이 일반적이다. 결과를 저장하는 리스트는 DP 테이블이라고 부른다. 즉 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.
아래 코드는 피보나치 수열을 바텀업 방식으로 구현한 소스코드이다.
# 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp_table = [0] * 100
# 첫번째 피보나치 수와 두번째 피보나치 수는 1
dp_table[1] = 1
dp_table[2] = 1
n = 5
# 피보나치 함수를 반복문으로 구현한다.
for i in range(3, n+1):
dp_table[i] = dp_table[i-1] + dp_table[i-2]
print(dp_table[n])
피보나치 수열을 탑다운 방식으로 구현한 소스코드이다.
# 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp_table = [0] * 100
def fibonacci(x):
if x == 1 or x == 2:
return 1
if dp_table[x] != 0:
return dp_table[x]
dp_table[x] = fibonacci(x - 1) + fibonacci(x - 2)
return dp_table[x]
print(fibonacci(5))
Reference
https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98
피보나치 수 - 위키백과, 우리 모두의 백과사전
피보나치 수를 이용한 사각형 채우기 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8
ko.wikipedia.org
https://freedeveloper.tistory.com/276
[이것이 코딩 테스트다] 6. 다이나믹 프로그래밍
www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 다이나믹 프로그래밍 다이나믹 프로그래밍은 동적 계획법이라고도 부른다 일반적인 프로그래밍 분야에서의 동적(Dynamic)..
freedeveloper.tistory.com
'ALGORITHM > Algorithm 설명' 카테고리의 다른 글
[알고리즘] 최단경로 알고리즘 (0) | 2022.03.12 |
---|---|
[알고리즘] Binary Search (0) | 2022.02.28 |
[알고리즘] BFS (Breadth First Search) (0) | 2022.02.04 |
[알고리즘] DFS (Depth First Search) (0) | 2022.02.03 |
[알고리즘] 완전탐색 (Exhaustive Search) (0) | 2022.01.25 |