ch8.py

#최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제
#따라서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성

#어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법
#대표적인 것이 다이나믹 프로그래밍 기법(동적 계획법)
#탑다운과 보텀업 2가지 방식이 있음

#프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중'이라는 의미
#자료구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법
#But 다이나믹 프로그래밍에서의 다이나믹은 다른 의미를 가짐

#다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열
#피보나치 수열은 1부터 시작해서 마지막 항과 이전 항 2항의 합을 그 다음 항의 값으로 하는 수열
#보통 점화식으로 표현 x_(n+2) = x_(n+1) + x_n

#위 점화식을 재귀함수로 표현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    return fibo(x-1) + fibo(x-2)

print(fibo(4))

array = []
for i in range(1, 5):
    array.append(fibo(i))

print(array)

#여기서 이렇게 재귀식으로 표현할 경우 x 값이 커지면 커질수록 연산 시간이 기하급수적으로 늘어나는 문제가 발생
#따라서 재귀 함수를 사용해 만들 수는 있지만 단순 계산은 효율적이지 못함

#다이나믹 프로그래밍은 다음 조건을 만족할 때 사용
#1. 큰문제를 작은 문제로 나눌 수 있음
#2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

#위 문제를 메모이제이션 기법을 사용해서 해결
#메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나로 한 번 구한 결과를 메모리 공간에 메모하고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법
#이 때 값을 메모(저장)하는 방식으로 캐싱 이라고도 함

#구현 방법은 한 번 구한 정보를 리스트에 저장
#음 이전에 방문한 곳을 마킹하는 그런 아이디어랑 비슷한듯?

d=[0] * 100

def fibo(x):
    if x == 1 or x == 2:
        d[x-1] == 1
        return 1
    
    if d[x-1] != 0:
        return d[x-1]

    d[x-1] = fibo(x-1) + fibo(x-2)
    return d[x-1]

array = []
for i in range(1, 100):
    array.append(fibo(i))

print(array)

#정리하자면 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 효율성을 증대
#퀵 정렬의 알고리즘과 비슷하나 차이는 다이나믹 프로그래밍에서는 문제들이 서로 영향을 미치고 있다는 점(점화식으로 표현되는 거 자체가 어느 규칙을 가지고 끊임없이 이어지는 것을 의미)
#재귀 함수를 사용하면 오버헤드가 발생할 수는 있음(무언가 반복 중에 발생하는 문제로 보임)
#따라서 재귀문 보다는 반복문을 이용하는 것이 더 좋음(실제로 반복문으로 구현한 다이내믹 프로그래밍 성능이 더 좋음)