[이코테] Chap 8. 다이나믹 프로그래밍

Coding Test/이코테

[이코테] Chap 8. 다이나믹 프로그래밍

ʕ민지ʔ 2024. 9. 27. 21:28

이론

시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어렵다. 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문이다. 따라서 두 요소를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

하지만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다! 대표적으로 다이나믹 프로그래밍(Dynimic Programming) 기법이 여기 속한다.

~~프로그래밍에서 보통 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이지만, 다이나믹 프로그래밍에서의 '다이나믹'은 이 의미가 아니다.~~

예시 - 피보나치 수열

기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 보자. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다.

수열의 항이 이어지는 형태는 인접한 항들 사이의 관계식인 점화식을 사용해 간결하게 표현할 수 있다. 피보나치 수열의 점화식은 다음과 같다. (인접 3항간 점화식)

피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 나타낼 수 있다.

✓ n번째 피보나치 수 = (n- 1)번째 피보나치 수 + (n - 2)번째 피보나치 수

✓ 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

프로그래밍에서는 수열을 배열이나 리스트로 표현할 수 있다. 파이썬에서는 리스트 자료형, C/C++와 자바에서는 배열을 이용한다. 리스트와 배열 모두 '연속된 많은 데이터' 를 처리한다는 면에서 동일하다.

점화식에 따라 피보나치 수를 구하는 과정을 표현할 때엔, 다음과 같이 재귀 함수를 사용하면 된다.

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^N) 정도의 시간이 소요된다. N=30이면 약 10억 가량의 연산을 수행해야 한다는 의미다.

f(6)의 호출 과정을 보면, 함수가 반복적으로 호출되는 것을 알 수 있다. 이미 한 번 계산했지만 호출할 때마다 계속 계산하는 것이다. f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다. 예를 들어 f(100)을 계산하려면 약 1,000,000,000,000,000,000,000,000,000,000번이다. 재귀 함수를 사용하면 반복되는 계산이 많아져 효율적으로 문제를 해결할 수 없다. 이런 경우 다이나믹 프로그래밍을 사용한다. DP는 다음의 조건이 만족할 때 사용할 수 있다.

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

피보나치 수열은 이러한 조건을 만족하므로 DP를 구현해보자.

[1] 탑다운 방식(Top-Down)

메모이제이션(Memoization)은 DP를 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

실제로 메모이제이션을 구현하려면 한 번 구한 정보를 리스트에 저장하면 된다. DP를 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 답을 리스트에서 가져와 쓰는 것이다.

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

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
	if x == 1 or x == 2:
		return 1

	# 이미 계산한 적 있는 문제라면 그대로 반환
	if d[x] != 0:
		return d[x]
	
	# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
	d[x) = fibo(× - 1) + fibo(× - 2)
	return d[x]

print(fibo(99))

정리하면 DP는 큰 문제를 작게 나누고, 같은 문제면 1번씩만 풀어 문제를 효율적으로 해결하도록 하는 것이다.

분할 정복과의 차이

문제를 작게 나누는 방법은 퀵 정렬에서도 사용한다. 퀵 정렬은 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 하고, 이는 분할 정복(Dvide and Conquer)로 분류된다. 퀵 정렬에서 한 번 '기준 원소'가 자리를 변경해서 자리를 잡으면 기준 원소의 위치는 더 이상 바귀뀌 않고, 그 pivot 값을 다시 처리하지 않는다.

반면 DP는 한 번 해결했던 문제를 다시금 해결하는 부분이 있고, 이를 위해 이미 해결된 부분에 대한 답을 저장하고 그 값을 반환하는 것이다. 때문에 DP는 문제들이 서로 영향을 미친다.

f(6)을 호출할 때에는 위의 그림처럼 색칠된 노드만 방문한다. 점선으로 표시된 부분은 사실상 호출되지 않는다. 왜냐하면 호출하더라도 따로 계산하지 않고 리스트에서 값을 가져오거나 바로 1을 반환하기 때문이다.

시간 복잡도

DP를 적용한 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다. 왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는 데 사용되는 방식으로 이어지기 때문이다. 한 번 구한 결과는 다시 구해지지 않는다.

[2] 보텀업(Bottom-Up) 방식

이렇게 재귀 함수를 이용해 DP 코드를 작성하는 방법은 탑다운(Top-Down) 방식이라고 한다. 큰 문제를 해결하기 위해 작은 문제를 호출하기 때문이다. 그러나 이렇게 재귀 함수를 쓰면 메모리 적재 과정 때문에 오버헤드가 발생할 수 있으므로 대신 반복문을 사용하자. 일반적으로 반복문을 이용한 DP가 더 성능이 좋다. 반면 단순히 반복문을 이용해 코드를 작성하는 방법은 작은 문제부터 차근차근 답을 도출하여 보텀업(Botton-Up) 방식이라고 한다.

피보나치 수열 문제를 보텀업 방식으로 풀면 다음과 같다. 동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한다.

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

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

# 피보나치 항수(Fibonacci Function) 반복문으로 구현(보텀업 DP)
for 1 in range(3, n + 1):
	d[i] = d[i - 1] + d[i - 2]

print(d[n])

DP의 전형적인 형태는 보텀업 방식이고, 이때 사용하는 결과 저장용 리스트는 'DP 테이블'이라 한다. 메모이제이션은 탑다운 방식에서만 사용되는 표현이다.

메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념으로 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 DP를 위해 쓰지 않을 수도 있다. 즉, DP와는 별도의 개념이다.

또한 메모리제이션 방식 사용 시, 수열의 모든 경우가 아닌 일부의 작은 문제에 대한 해답만 필요한 때엔 리스트보다 사전(dict) 자료형을 사용하는 게 더 효과적일 수 있다.

코테에서 DP는 대체로 간단한 형태로 출제된다.

가장 먼저 문제가 DP 유형임을 파악하자. 문제를 완전 탐색 알고리즘으로 접근했는데 시간이 매우 오래 걸리는 경우, DP를 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인하자
일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법을 사용할 수도 있다.
가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하자. 시스템 상 재귀 함수의 스택 크기가 한정되어 있을 수 있다.

실전문제

실전 문제2. 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])

각각의 경우 중에서 최소의 수를 구한다.

실전 문제3. 개미 전사

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

1. i-1 번째 창고를 턴 경우

2. i-2까지의 최댓값과 현재 창고를 턴 경우

-> 둘 중 더 큰 값을 저장

실전 문제4. 바닥 공사

# 정수 N을 입력 받기
n = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

# 계산된 결과 출력
print(d[n])

실전 문제5. 효율적인 화폐 구성

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

현재글[이코테] Chap 8. 다이나믹 프로그래밍

꾸준히

Today :
Yesterday :

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

꾸준히