다이나믹 프로그래밍
개념
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록
- 탑다운과 보텀업 방식 두 가지로 분류
조건
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))