다이나믹 프로그래밍

개념

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록
• 탑다운과 보텀업 방식 두 가지로 분류

조건

1. 최적 부분 구조

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 가능

2. 중복되는 부분 문제

동일한 작은 문제를 반복적으로 해결해야 함

예시

피보나치 수열

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

print(fibo(4))

이와 같이 피보나치 수열을 재귀적으로 풀면 불필요한 함수 호출이 많아진다. 이 경우 시간 복잡도가 O(2^n)이라는 복잡도가 나오게 된다. 그럼 어떻게 시간 복잡도를 줄 일 수 있을 까?

탑다운(메모이제이션)

한 번 계산한 결과를 메모리 공간에 메모. 캐싱이라고도 한다.

d = [0] * 100

def fibo(x):
	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))

시간 복잡도를 O(N)까지 줄일 수 있다.

보텀업(DP 테이블)

d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n + 1):
	d[i] = d[i-1] + d[i-2]

print(d[n])

문제 접근 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
• 먼저 그리디, 구현, 완전 탐색 등 아이디어로 풀 수 있는지 확인
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법 사용 가능
• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다

예제

1.

💡 아이디어

각 자리 수까지 가장 최대로 약탈할 수 있는 값을 저장한 리스트를 만든다. 그리고 바텀업 방식으로 문제를 해결한다.

n = int(input())
array = list(map(int, input().split()))

d = [0] * 100

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])

2.

💡 아이디어

이 문제도 바텀업 방식으로 해결해야한다. 1부터 X까지의 최소한의 연산 횟수를 담은 DP 테이블을 만들어서 문제를 해결한다.
이럴 경우에 만약 26이라면, -1 이후 인 d[25]와 나누기 2를 한 이후 인 d[13] 을 미리 구해놓으면 두 연산 중 어떤 것이 후에 더 효율적인 방안인지 알 수 있다.

x = int(input())

d = [0] * 30001

for i in range(2, x+1):
	d[i] = d[i-1] + 1
    
    if i % 2 == 0:
    	d[i] = min(d[i], d[i//2] + 1)
	if i % 3 == 0:
    	d[i] = min(d[i], d[i//3] + 1)
	if i % 5 == 0:
    	d[i] = min(d[i], d[i//5] + 1)

print(d[x])

3.

💡 아이디어

그림과 같이 먼저 리스트 값 초기화를 진행 해줍니다. 그리고 화폐마다 값들을 갱신해주면서 문제를 해결하면 됩니다.

N, M = map(int, input('입력 = ').split())
X = list()
for i in range(N):
    X.append(int(input()))

d = [10001] * (M + 1)

d[0] = 0
for i in range(N):
    for j in range(X[i], M+1):
        if d[j - X[i]] != 10001:
            d[j] = min(d[j], d[j - X[i]] + 1)

if d[M] == 10001:
    print(-1)
else:
    print(d[M])

4.

💡 아이디어

dp테이블인 d를 0으로 초기화 해주고, 2차원 공간의 문제이기 때문에 나는 방향벡터를 정의하였다.
그리고 첫 번째 열은 모두 arr와 같은 값이기 때문에 초기화를 해준다.

이중 for문을 통해서 각 열의 행마다 접근을 할 예정이다. 현재 위치에 우리가 정의한 3개의 방향을 더하여 범위 밖으로 나가지 않으면, 이동한(moved) 위치의 dp 테이블 값과 이동 전의 dp 테이블값 + 이동할(moved) 위치의 arr 값을 비교하여 둘 중 더 큰 것은 이동할(moved) 위치의 dp 테이블에 저장한다.

이렇게 하면 현재 위치에서 이동하는 3가지 위치의 값을 비교하여 값이 더 크다면 dp 테이블 값을 업데이트 한다.

row, column = map(int, input().split())
arr = list()
for i in range(row):
    arr.append(list(map(int, input().split())))

d = [[0] * column for _ in range(row)]

dRow = [-1, 0, 1]
dColumn = 1

for i in range(row):
    d[i][0] = arr[i][0]

for i in range(column):
    for j in range(row):

        for k in range(len(dRow)):
            movedRow, movedColumn = j + dRow[k], i + dColumn
            if movedRow < 0 or movedRow >= row or movedColumn < 0 or movedColumn >= column:
                continue
            d[movedRow][movedColumn] = max(d[movedRow][movedColumn], d[j][i] + arr[movedRow][movedColumn])

for i in range(len(d)):
    for j in range(len(d[i])):
        print(d[i][j], end=' ')
    print()

print(max(list(map(max, d))))

5.

💡 아이디어

이 문제는 LIS를 이용하여 쉽게 해결할 수 있다. 입력 받은 arr을 reverse하면 LIS문제와 같기 때문에 이를 활용한다.

n = int(input('입력 = '))
arr = list(map(int, input().split()))
arr.reverse()

d = [1] * (n + 1)

for i in range(1, n):
    for j in range(i):

        if arr[j] < arr[i]:
            d[i] = max(d[i], d[j]+1)

print(n - max(d))