211227 다이나믹 프로그래밍

• 다이나믹 프로그래밍
  • 피보나치 수열
    • 피보나치 수열 구하는 과정
    • 메모이제이션 (Memoization) 기법
  • 결론

다이나믹 프로그래밍

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

중복되는 연산 줄이기

프로그래밍에서 다이나믹 이란, '프로그램이 실행되는 도중에' 라는 의미이다. 자료구조에서 동적 할당(Dynamic Allocation) 은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다. 그러나 '다이나믹 프로그램' 에서는 이런 의미는 아니라는 것을 기억하자.

피보나치 수열

이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열

• $n$ 번째 피보나치 수 = $(n - 1)$ 번째 피보나치 수 + $(n - 2)$ 번째 피보나치 수
• 단, 1 번째 피보나치 수 = 1, 2 번째 피보나치 수 = 1

프로그래밍 에서는 이러한 수열을 배열 이나 리스트 로 표현할 수 있다.
수열 자체가 여러 개의 수가 규칙에 따라서 배열된 형태 를 의미하기 때문이다. 리스트나 배열 모두 '연속된 많은 데이터를 처리' 한다는 점은 동일하다.

피보나치 수열 구하는 과정

$n$ 번째 피보나치 수 를 $f(n)$ 이라고 표현할 때 4 번째 피보나치 수 $f(4)$ 를 구하려면 다음과 같이 함수 $f$ 를 반복해서 호출 할 것이다.
여기서 $f(2)$ 와 $f(1)$ 은 항상 1 이기 때문에 $f(1)$ 이나 $f(2)$ 를 만났을 때는 호출을 정지한다.

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

print(fibo(4))

그러나 피보나치 수열의 소스코드를 재귀 함수를 사용하여 작성하면, 동일한 함수가 반복적으로 호출될 수 있다. $f(n)$ 에서 $n$ 이 커지면 반복해서 호출하는 경우가 많아진다.

_{예를 들어 $f(100)$ 을 계산하려면, 연산 횟수는 약 1,000,000,000,000,000,000,000,000,000,000 번 이다.}

다시말해, 재귀 함수를 사용하여 매번 계산 하도록 하면 문제를 효율적으로 해결 할 수 없다. 이러한 문제는 다이나믹 프로그래밍 을 이용하면 효율적으로 해결할 수 있다. 다이나믹 프로그래밍은 항상 사용할 수는 없으며, 다음 조건을 만족할 때 사용할 수 있다.

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

메모이제이션 (Memoization) 기법

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

메모이제이션을 구현하는 방법은, 한 번 구한 정보를 리스트에 저장하여 구할 수 있다. 재귀적으로 다이나믹 프로그램을 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져오면 된다.

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

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
  print('f(' + str(x) + ')', end=' ')
  # 종료 조건(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(6))
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) 8

const d = Array(100).fill(0)

function fibo (x) {
  console.log(`f(${x})`)  // f(6), f(5), f(4), f(3), f(2), f(1), f(2), f(3), f(4)
  if (x === 1 || x === 2) return 1

  if (d[x] !== 0) return d[x]

  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]
}

console.log(fibo(6)) // 8

결론

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 한 번 해결 했던 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 된 것이니까 다시 해결할 필요가 없어 답만 반환하는 것이다.

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top Down) 방식 (하향식) 이라고 한다.
반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom Up) 방식 (상향식) 이라고 말한다.

다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이며, 사용되는 결과 저장용 리스트는 DP 테이블 이라고 부른다. _{(메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다)}

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 6

# 피보나치 함수 (Fibonacci Function) 반복문으로 구현 (바텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
  print('f(' + str(i) + ')', end=' ')
  d[i] = d[i - 1] + d[i - 2]

print(d[n])
# f(3) f(4) f(5) f(6) 8

다이나믹 프로그래밍을 이용하여 피보나치 수열 문제를 풀었던 방법을 잘 알아두면 다른 다이나믹 프로그래밍 문제에 접근하는 방법 또한 떠올릴 수 있을 것이다.

코딩테스트에서의 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제된다.

문제를 푸는 단계는,

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악한다.
2. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 결린다면, 다이나믹 프로그래밍을 적용할 수 있는지,
   해결하고자 하는 부분 문제들의 중복 여부를 확인한다.

가능하다면 탑다운 방식(재귀함수) 보다는 보텀업 방식으로 구현하는 것이 안정적이다. 재귀 함수의 스택 크기가 한정되어있을 수 있기 때문이다.