16. 다이나믹 프로그래밍 : 문제 풀이 전략

컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다.

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

 

다만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.

이것이 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다.

 

피보나치 수열의 경우 쉽게 코드로 나타낼 수 있지만 

재귀적 방식

def fibo(x):
  if x == 1 or x ==2:
    return 1
  return fibo(x-1) + fibo(x-2)

print(fibo(4))

for문 방식

memory = [0] * 100

def fibo(x):
 
  if x == 1 or x ==2:
    return 1
  
  new_value = 1
  old_value = 1
  temp = 0

  for i in range(x) :
    temp = new_value + old_value
    old_value = new_value
    new_value = temp
    print(temp)
  
  return temp

시간 복잡도가 정확히는 세타 (1.618..**n)이지만 일반적으로 O(2**n)표기한다. 즉 n이 커지면 수행 시간이 기하급수적으로 늘어나기 때문에 100번째 fibo를 호출했을 경우에는 우리의 수명이 다해도 연산이 끝나지 않는다.

 

다이나믹 프로그래밍으로 이를 해결 할 수 있는데, 다이나믹 프로그래밍의 조건.

1. 큰 문제를 작은 문제로 나눌 수 있다. (예, fibo(n) = fibo(n-1)+fibo(n-2) )

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (예, fibo(n+1) = fibo(n) + fibo(n-1)  )

 

메모제이션 기법, DP 테이블 (중복되는 연산을 줄이자.)

 

탑다운 방식

memory = [0] * 100

def fibo(x):
  if x == 1 or x ==2:
    return 1

  if memory[x] != 0:
    return memory[x]
  
  memory[x] = fibo(x-1) + fibo (x-2)
  return memory[x]
print(fibo(99))

index를 신선하게 활용한다는 것에 있어서 계수배열과 비슷한 느낌이 든다.

저장이 된 경우는 그대로 값을 활용하고 저장이 안 되있는 경우는 저장하고 return 해주는 것이 인상적이다.

하지만 재귀를 사용할 경우에는 오버헤드를 발생시킬 수 있으므로 for문을 사용하는 것이 좋다.

일반적으로 반복문을 사용한 것이 성능이 더 좋다.

 

바텀업 방식

memory = [0] * 100

def fibo(x):
  memory[1] = 1
  memory[2] = 1

  for i in range(3, x+1):
    memory[i] = memory[i-1] + memory[i-2]
  return memory[x]

print(fibo(5))

와우 진짜 리스트를 이렇게 활용할 수도 있구나.. 하는 생각이 들 정도로 심플하면서도 아름답다.

 

메모제이션

 

때에 따라 dict를 이용할 수 있다. 수열처럼 연속적이지 않은 경우에 유용하다.

일부의 작은 문제에 대한 해답만 필요할 경우가 존재할 수도 있다. 이럴 땐 dict를 활용하자!

 

문제를 푸는 첫 단계는 바로 다이나믹 프로그래밍 유형임을 파악하는 것.

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

일단 재귀 함수로 비효율적인 프로그램을 작성한뒤 메모제이션을 적용

(재귀 함수 깊이 오류가 날경우 sys 라이브러리의 setrecursionlimit() 함수 호출)

가능하다면 보텀업 방식으로 구현하는 것을 추천한다. .