다이나믹 프로그래밍(Dynamic Programming)

" 중복되는 연산을 줄이자 "

" 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 "

" 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지
해결하고자 하는 부분 문제들의 중복 여부를 확인해보자 "

- (해결하기 어려운 문제) = 깊게 다루는 분야로는 계산 복잡도 이론이 있다. => P-NP??? 공부 추천

- 3차원 리스트를 이용해야하는 복잡한 난이도 문제 = 9장 "최단 경로"

컴퓨터를 활용해도 해결하기 어려운 문제란 무엇인가???
- 최적의 해를 구하기에 시간이 매우 많이 필요하거나
- 메모리 공간이 매우 많이 필요한 문제 등 

컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이
많은 제약을 발생시킨다.

" 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다 "

(참고)
다이나믹 프로그래밍과 동적 할당의 다이나믹은 같은 의미일까???
- 프로그래밍에서 다이나믹(Dynamic)은 " 프로그램이 실행되는 도중에 " 라는 의미

동적 할당(Dynamic Allocation)
- 자료구조에서 동적 할당은 " 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당 "하는 기법
- 다아나믹 프로그래밍에서의 " 다이나믹 "은 이런 의미가 아니라는 점만 기억하기

<접근 방식>

" 왼쪽부터 차례대로(= 점화식), i - 1 "

1. 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용할 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어이다.

- 첫번째 코드에서 메모이제이션 기법을 적용해(두번째 코드) 소스코드를 수정하는 것도 좋은 방법임

 

2. But 가능하다면 위 방식보다는 보텀업 방식으로 구현하는 것을 권장한다.

- 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있다.

- 첫번째 코드(재귀적인 피보나치 수열)의 소스코드에서 5000번 이상의 큰 피보나치의 수를 구하도록 하면 " recursion depth 재귀 함수 깊이 " 와 관련된 오류가 발생할 수 있다.

# 재귀 제한 완화
import sys

sys.setrecursionlimit(10**6)

<사용 예시>

- 피보나치 수열( = 시간복잡도 O(2ⁿ) )

- 수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현

<점화식이란???>

- 인접한 항들 사이의 관계식을 의미하는데, 

https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D

점화식 - 위키백과, 우리 모두의 백과사전

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다.
수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다.

'''
* n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
* 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
'''

# 해당 코드 문제 발생
# n이 커질수록 수행 시간이 기하급수적으로 늘어남
# 점화식을 재귀 함수를 사용 == 비효율적

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(4))

	 f(4)
       /      \
    f(3)      f(2)
   /     \
f(2)     f(1)

prit(fiboncci(30)) # 2초 넘어감

파이썬의 경우 기본 자료형인 리스트 자료형이 연결 리스트(Linked List)의 기능을 포함하고 있는 점이
다른 프로그래밍 언어에서의 배열과 차이점이다. <Linked List>

n이 커질수록 수행 시간이 늘어남( 동일한 함수 반복적으로 호출함. = 이미 계산했지만 계속 호출할 때마다 계산)

 

<조건>

- 항상 다아니막 프로그래밍을 사용할 수는 없다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
대표적 예시 = 피보나치

<메모이제이션 Memoization 기법>

- 다이나믹 프로그래밍을 구현하는 방법 중 한 종류(= 퀵 정렬에서도 소개됨)

<정렬>
https://cord-ai.tistory.com/160

- 퀵 정렬 = 분할 정복(Divide and Conquer) 알고리즘으로 분류된다.
- 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹은 문제들이 서로 영향을 미친다는 것

- 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

- 메모이제이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다

- 99번째인데도 금방 점답을 도출함(= 단순 매번 계산하는 피보나치 코드는 30번째 수를 구할려면 2초 걸림) 

# Memoization
# 한 번 구한 정보를 리스트에 저장
# 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미
# 구한 답을 그대로 리스트에서 가져오면 된다.

# 한 번 계산된 결과를 "메모이제이션" 하기 위한 리스트 초기화
# 퀵 정렬에서도 소개됨
m = [0] * 100

def fibo(n):
    # 종료 조건
    if n == 1 or n == 2:
        return 1    
    
    # 이미 계산했던 것이라면 그대로 반환
    if m[n] != 0:
        return m[n]

    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    m[n] = fibo(n-1) + fibo(n-2)
    return m[n]
    
start = time.time()
print(fibo(99))
end = time.time()
print(end - start) # 0

사전(Dict) 자료형을 이용할 수도 있다.
- 사전 자료형은 수열처럼 연속적이지 않은 경우에 유용한데,
a의 n번째를 계산하고자 할 때 a0 ~ a n-1 모두(=합이)가 아닌 일부의 작은 문제에 대한 해답만 필요한 경우 

<퀵과 다이나믹>

- 퀵 정렬은 한 번 기준 원소 Pivot가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.

- 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징

" So, 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다. "

메모이제이션 방문 노드는 4개만 봄

점선 노드 = 처음 방식으로 호출했던 부분, 사실상 호출되지 않는것임
why???
- 호출하더라도 따로 계산하지 않고 리시트에서 값을 가져오거나 바로 1을 반환하기 때문에(= 코드 참조)

<메모이제이션에서 발생할 수 있는 문제>

- 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다.

= 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.

= 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋다.

<시간 복잡도 O(N)>

= f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는데 사용되는 방식으로

이어지기 때문

= 한번 구한 결과는 다시 구해지지 않는다.(= 계산 X)

최종적으로 다이나믹 프로그래밍을 적용했을 때 피보나치 수열 알고리즘, 시간 복잡도 O(N)

" 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, (메모이제이션)

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑 다운(Top-Down) 방식이라고 말한다. "

- '하향식'이라고도 한다.

- 메모제이션은 탑다운 방식에 국한되어 사용되는 표현

 

" 단순히 반복문을 이용하여 소스코드를 작성하는 경우,

작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up)이라고 말한다 "

- '상향식'이라고도 한다.

- 다이나믹 프로그래밍의 전형적인 형태

- Bottom Up 방식에서 사용되는 결과 저장용 리스트를 DP 테이블라고 부름

 

# Bottom Up 방식에서 사용되는 결과 저장용 리스트를 DP 테이블라고 부름
# DP테이블 초기화
m = [0] * 100

m[1] = 1
m[2] = 1
n = 99

# Bottom Up 다아니막 프로그래밍 
for i in range(3, n+1):
    m[i] = m[i-1] + m[i - 2]

print(m[n])