알고리즘 정리 <다이나믹 프로그래밍>

다이나믹 프로그래밍

 

다이나믹 프로그래밍이란 다양한 알고리즘 문제를 푸는 상황에서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이다.

 

쉽게 말로 표현하자면 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다.

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다.

 

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

1   1   2   3   5   8   13   21   34   55   89

이를 점화식으로 나타낼 수 있는데 an+2 = an+1 + an과 같이 표현할 수 있고 프로그래밍으로 표현하면 다음과 같다.

 

[소스 코드]

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

  return fibo(x-1) + fibo(x-2)


print(fibo(4))

이 소스코드의 문제점은 fibo(n)의 함수에 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다.

예를들어 fibo(6)를 수행하면 동일한 함수들이 반복적으로 호출되는걸 확인할 수 있다.

따라서 이렇게 재귀함수를 통해 간단하게 피보나치 수열의 점화식을 프로그래밍 할 수 있지만 단순히 매번 계산하도록하면 문제를 효율적으로 해결할 수 없게된다.

 

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

하지만 다이나믹 프로그래밍을 항상 사용할 수 있는 것은 아니고 다음 조건을 만족할 때 사용할 수 있다.

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

피보나치 수열은 해당 조건을 만족하기 때문에 메모이제이션(mermoization)기법을 사용해 해결할 수 있다.

메모이제이션이란 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

메모이제이션은 값을 저장하는 방법이므로 캐싱(cashing)이라고도 한다.

 

그렇다면 메모이제이션 기법을 사용해 어떻게 다이나믹 프로그래밍을 구현해야할까.

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

 

[소스 코드]

# 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

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))