동적 계획법 (Dynamic Programming)

• 약간의 추가적인 메모리 공간의 활용으로 연산 속도를 비약적으로 증가시킬 수 있는 알고리즘

✅ 다이나믹 프로그래밍이란?

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

• 위 두 조건을 만족하는 상황에서 효율적으로 해결 가능한 알고리즘

  다이나믹의 의미는? 단순히 멋져보여 붙여진 이름이라고 한다. 메모리 동적 할당에서의 '다이나믹' 의미와는 연관성이 없다!

✅ 다이나믹 프로그래밍 vs 분할정복(Divide and Conquer)

• if) 작은 문제의 중복이 일어나는가?
  • 중복 ⭕️ : 다이나믹 프로그래밍
    • 작은 문제들이 반복(중복)되는 상황, 즉 큰 문제에서도 답이 바뀌지 않는 특징
    • 작은 문제의 풀이를 이용해 큰 문제를 해결할 수 있다는 특징
  • 중복 ❌ : 분할정복
    • 큰 문제의 해결이 어려울 경우 단순히 문제를 작게 나누어 해결하는 특징
    • 작은 부분 문제의 답이 항상 같다는 보장은 없다는 특징

✅ 다이나믹 프로그래밍에서 사용되는 방식

1. 탑다운(Top Down) 방식 - 메모이제이션

• 대부분 재귀 함수를 사용해 구현하는 경우
• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
• 메모이제이션 : 이전에 계산된 결과를 일시적으로 기록해놓는 개념
  • 탑다운 방식에서 메모이제이션을 활용

2. 보텀업(Bottom Up) 방식 - 다이나믹 프로그래밍의 전형적인 형태

• 단순 반복문을 이용해 소스코드를 작성하는 경우
• 작은 문제부터 차근차근 답을 도출하는 방식
• DP Table : 보텀업 방식에서 사용되는 결과 저장용 리스트

✅ 메모이제이션 vs 다이나믹 프로그래밍

• 메모이제이션

  • 이전에 계산된 결과를 일시적으로 기록해놓는 개념
  • 탑다운 방식에 국한되어 사용되는 표현
  • 한 번 계산된 결과를 어딘가에 담아놓기만 하고, DP를 위해 사용하지 않을 수도 있음
  • 수열 : 배열 or 리스트로 표현할 수 있음
    • 메모이제이션 : 때에 따라 다른 자료형(ex. dict ...)을 이용할 수도 있음

• ex) 피보나치 수열
  

• 작은 문제들이 반복되고 그 작은 문제들의 결과 값이 항상 같으므로 이전에 계산된 작은 문제를 저장할 때 memoization 사용

다이나믹 프로그래밍과 메모이제이션은 별도의 개념이므로 혼용해 사용하지 말자!

✅ 다이나믹 프로그래밍은 어떤 상황에서 어떻게 사용하는가?

1. 완전 탐색 알고리즘으로 접근하였을 때 시간이 오래 걸리는 경우
   → 해결하고자 하는 부분 문제들의 중복 여부를 확인
   → 먼저 단순 재귀함수로 비효율적 프로그램을 작성해볼 것 (Top Down)
   → 작은 문제에서 구한 답이 큰 문제에서 사용될 수 있는 경우, 메모이제이션 기법을 적용해 수정해볼 것

2. 탑다운보다 보텀업 방식 권장

   • 시스템 상 재귀함수의 스택 크기가 한정되어 있을 수 있음
     • ex) 오천번째 이상의 피보나치 수 계산 시 recursiondepth(재귀함수 깊이) 오류가 발생할 수 있음
       • 위의 경우 sys 라이브러리 - setrecursionlimit() 함수 호출을 통해 재귀 제한 완화

✅ 다이나믹 프로그래밍 예제 - 피보나치 수열

• f(n) 함수에서 n이 커질수록 수행 시간이 기하급수적으로 늘어남 → sol. 메모이제이션 사용
• 시간 복잡도 : O(2N)

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

• 메모이제이션을 사용해 재귀적으로 코드를 표현 - Top-Down DP
• 시간 복잡도 : O(N)

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 d 초기화
d = [0] * 100
# 피보나치 수열을 재귀함수로 구현 - 탑다운 방식의 DP
def fibo(x):
    # 종료 조건(1 또는 2일 때 1을 반환
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 문제의 경우, 메모이제이션 리스트 d에 값이 있는 경우 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제의 경우, 점화식에 따라 메모이제이션 & 계산 값 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

• DP 테이블을 사용해 반복적으로 코드를 표현 - Bottom-Up DP

# 한 번 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수 : 1
d[1] = 1
d[2] = 1
n = 99
# 반복문으로 피보나치 수열 구현 - 보텀업 DP
for in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

📌 자료 출처

이것이 취업을 위한 코딩테스트다 with 파이썬