20250120 이것이 코딩 테스트다 챕터8(다이나믹 프로그래밍)

다이나믹 프로그래밍

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

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

재귀 함수로 비효율적인 프로그램(탑다운)을 작성한 뒤 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어.

가능하다면 재귀 함수 이용하는 탑다운 방식보다 버텀업 방식으로 구현하는 것을 권장. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문.

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제는 피보나치 수열. 피보나치 수열을 재귀 함수를 사용해 문제를 해결하려고 하면 이미 호출했던 함수를 또 호출하는 불필요한 호출을 하게 된다. 그렇게 되면 O(2^n)이라는 아주 안좋은 시간복잡도를 가지게 된다. 따라서 다이나믹 프로그래밍을 사용해 효율적으로 해결한다.

다이나믹 프로그래밍 사용 조건

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

탑다운 방식

큰 문제를 해결하기 위해 작은 문제를 호출한다.
재귀 함수를 이용해 다이나믹 프로그래밍 소스코드를 작성하는 방법 같은 것이 탑다운 방식.

메모이제이션이라고도 함.
하향식이라고도 함.

메모이제이션 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류.
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법.
값을 저장하는 방법이므로 캐싱이라고도 함.

구현

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

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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]

이 경우 시간복잡도는 O(N)

버텀업 방식

작은 문제부터 차근차근 답을 도출한다.
단순히 반복문을 이용해 소스코드를 작성하는 경우 버텀업 방식.

상향식이라고도 함.
다이나믹 프로그래밍의 전형적 형태.

구현

다이나믹 프로그래밍을 반복문으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 DP 테이블에서 가져오면 됨.

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

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

# 피보나치 함수 반복분으로 구현(버텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
  d[i] = d[i - 1] + d[i - 2]

cf. 재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있음.
재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 다이나믹 프로그래밍이 더 성능이 좋음.

cf. 다이나믹 프로그래밍과 메모이제이션은 다르다.
메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미함.
한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있음.

---