[알고리즘] Dynamic Programming

 

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

피보나치 수 - 위키백과, 우리 모두의 백과사전

https://freedeveloper.tistory.com/276

[이것이 코딩 테스트다] 6. 다이나믹 프로그래밍