Ch8.다이나믹 프로그래밍

1. 다이나믹 프로그래밍

중복되는 연산을 줄이자

🔖컴퓨터로도 해결하기 어려운 문제?

• 최적해를 구하기에 시간이 많이 필요한 문제(연산 속도 한계)
• 메모리 공간이 매우 많이 필요한 문제(메모리 공간 한계)
  => 효율적인 알고리즘을 작성해야 한다.

⭐다이나믹 프로그래밍(동적 계획법)

• 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가!

다이나믹의 의미
: 프로그램이 실행되는 도중에 (하지만 여기서의 다이나믹은 이 의미가 아님!)

🔖다이나믹 프로그래밍을 이용하는 대표적 예시

• 피보나치 수열
  • 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열.

  

  • 점화식으로 표현!
    • n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수

  <인접 3항간 점화식>
  => 프로그래밍에선 이러한 수열을 배열이나 리스트로 표현 가능.

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

  ➡️ 문제점:
  1. n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어남.(시간 복잠도: 2^N)
  2. 동일한 함수가 반복적으로 호출됨

다이나믹 프로그래밍을 이용할 수 있는 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션?

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법.
  
• 이전의 결과를 일시적으로 기록해 놓는 넓은 개념을 의미. => 캐싱이라고도 함.
  
  Tip. 때에 따라 dict가 이용될 수도 있음(수열처럼 연속적이지 않은 경우 유용)

⭐구현은 한번 구한 정보를 리스트에 저장!!

d = [0] * 100
# 메모이제이션은 탑다운 방식에 국한되어 이용되는 표현

def fibo(x):

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

print(fibo(99))

=> 재귀 함수를 이용하면 CS에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다(반복문을 이용하자!)
=> 시간복잡도는 O(N)

분할 정복 VS 다이나믹 프로그래밍

다이나믹 프로그래밍	분할 정복
문제들이 서로 영향을 미침	문제들이 서로 영향을 미치지 않음

탑다운 방식

• 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법(큰 문제를 해결하기 위해 작은 문제를 호출)

보텀업 방식

• 반복문

d = [0] * 100 # DP 테이블: 결과 저장용 리스트

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

문제를 푸는 단계

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악 => 특정한 문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인’
2. 일단 재귀적으로 작성(가능하면 반복문으로 작성)
3. 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 -> 코드 개선!(메모이제이션 활용)

recursion depth(재귀 함수 깊이) 오류
- sys 라이브러리의 setrecursionlimit() 함수를 호출하여 재귀 제한을 완화할 수 있음.