다이나믹 프로그래밍

다이나믹 프로그래밍

중복되는 연산을 줄이자

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

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 더 풀어 문제를 효율적으로 해결하는 알고리즘 기법

• 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법

• 두 가지 방식 1. 탑다운(메모지에이션, 재귀) 2. 보텀업(DP테이블, 반복문)

• 사용 조건

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

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

• 한 번 구한 정보를 리스트에 저장하고 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정보를 그대로 리스트에서 가지고 온다.

• 캐싱 caching 이라고도 한다.

  
  

  ex) 피보나치 수열

• 피보나치 수열: 단순 재귀 소스코드

  # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    def fibo(x):
    	if x==1 or x==2:
        	return 1
        return fibo(x-1)+fibo(x-2)
  
    print(fibo(4))

  
  

• 피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드

  # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
  d = [0]*100
  
  # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
  def fibo(x):
  	# 종료 조건(1 혹은 2일때 1을 반환)
      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))

  
  

• 피보나치 수열: 보텀업 다이나믹 프로그래밍 소스코드

  # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
  d = [0]*100
  
  # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
  d[1] = 1
  d[2] = 1
  n = 99
  
  # 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
  for i in range(3, n+1):
  	d[i] = d[i-1]+d[i-2]
      
  print(d[n])