다이나믹 프로그래밍

다이나믹 프로그래밍

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

 

- 대표적인 예: 피보나치 수열

피보나치 수열은 다음과 같은 형태의 수열이다.  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

 

점화식: 인접한 항들 사이의 관계식 

피보나치 수열의 점화식

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다.

𝑛번째 피보나치 수를 f(𝑛)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다

피보나치 함수 소스코드

# 피보나치 함수(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이 커질수록 수행 시간이 기하급수적으로 늘어난다는 문제가 발생한다. 

이 소스코드의 시간 복잡도는 O(2ᴺ)의 지수 시간이 소요된다.

다음과 같이 𝒇(2)가 중복되어 여러 번 호출되는 것을 확인할 수 있다. f(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다. 

 

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만 문제를 효율적으로 해결하지 못한다.

→ 다이나믹 프로그래밍을 사용하면 효율적으로 해결 가능

 

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

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

• 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족한다

 메모이제이션 (Memoization) 

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 구한 결과를 메모리 공간에 메모해두고 같은 문제를 다시 호출하면 메모한 결과를 가져옴
• 값을 저장하는 방식으로 캐싱(Caching) 이라고도 함
• 리스트로 구현 가능

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

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
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))

---

다이나믹 프로그래밍 VS 분할 정복

- 다이나믹 프로그래밍과 분할 정복은 모두 큰 문제를 작게 나누어 문제를 해결하는 알고리즘 기법

- 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복임

• 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
• 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

- 분할 정복의 대표적인 예시인 퀵 정렬

• 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않고, 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않음

- 다이나믹 프로그래밍

• 한 번 해결했던 문제를 다시금 해결함 ( 이미 해결된 부분 문제에 대한 답을 저장하고, 다시 해결할 필요가 없다고 반환)

 

메모이제이션 기법을 이용해 f(6)해법을 그려보면 피보나치 수를 호출할 때는 색칠된 노드만 방문함

다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)

 

탑다운 방식: 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 경우, 큰 문제를 해결하기 위해 작은 문제를 호출함

 

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

( 보텀업에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 함 )

 

 실전 문제  

1로 만들기

• 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다
  1. X가 5로 나누어 떨어지면, 5로 나눈다
  2. X가 3으로 나누어 떨어지면, 3으로 나눈다
  3. X가 2로 나누어 떨어지면, 2로 나눈다
  4. X에서 1을 뺀다
• 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 한다. 연산을 사용하는 횟수의
  최솟값을 출력하라. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다
  • 26 → 25 → 5 → 1

점화식 

 

답안 예시 

# 정수 X를 입력 받기
x = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

 

 

참조

[이것이 코딩 테스트다] 6. 다이나믹 프로그래밍

 

참고 서적

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