[python/자료구조] 동적 계획법(Dynamic Programming)

 

동적 프로그래밍이란?

---

하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어 정답을 찾은 뒤, 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정을 말한다.

 

 

메모이제이션이란?

---

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이며 동적 계획법의 핵심이 되는 기술이다.

 

 

---

 

Example

---

  
  # 피보나치 수열(Bottom up)
  def fib(n):
    fiblist = [ 1, 1 ]
    for i in range(2, n+1):
       fiblist.append(fiblist[i-2] + fiblist[i-1]
    return fiblist[-1]  # 마지막 값 반환


  # 피보나치 수열(Top down)
  def fib(n):
    if n==0 or n == 1 :
       return 1
    else :  
       res = fib(n-1) + fib(n-2)
       memo[n] = res   # 메모이제이션
       return res
        

 

 

Q .  다음 data 리스트에서 이웃하지 않는 숫자들의 합 중 최댓값을 구하라

      data = [ 3, 4, 5, 6, 1, 2, 5 ]

A . 

  
  def solution(data):
      # 값이 1개인 경우 그대로 반환
      if len(data) == 1:
         return data[0]
      # 값이 1개, 2개인 경우 추가
      result = [ data[0], max(data[0], data[1]) ]
      # 리스트 값이 3개 이상일때
      for i in range(2, len(data) ):
          result.append( max( result[i-1], result[i-2] + data[i] ) )
      return result[-1]

  data = [ 3, 4, 5, 6, 1, 2, 5 ]
  print(solution(data)) # 정답 15