동적 계획법(Dynamic Programming)이란?
메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이다. 또한 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이기도 하다.
DP의 핵심은 ‘메모제이션’(캐싱) 기법이다. 이미 계산된 결과(작은 문제)를 별도의 메모리에 저장해 다시 계산하지 않고 필요한 경우 사용하는 기법이다. 이 기법을 사용하면 시간복잡도가 훨씬 줄어들기에 수행 시간 효율이 비약적으로 향상된다.
- 처음 진행되는 연산은 기록한다.
- 이미 진행된 연산이라면 기록된 값을 호출한다.
- 시간과 자원 절약이 가능하다.
💡DP 사용 조건
- 최적 부분 구조(Optimal substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
- 부분 문제 반복(Overlapping subproblems)
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
💡DP 문제 해결 과정
- 주어진 문제가 DP 유형이 맞는지 확인 후, 최종적으로 풀어야 할 큰 문제를 확인한다.
- 큰 문제를 작은 문제로 분해하여 그 사이의 관계를
점화식의 형태로 나타낸다. - Memoization(Top-Down, 하향식) 방식 혹은 Tabulation(Bottom-up, 상향식) 방식을 통해 문제를 풀어나간다.
동적 계획법(DP) vs 분할 정복(Divide and Conquer)
동적 계획법의 경우 작은 문제가 큰 문제에 영향을 끼친다. 즉, 작은 문제가 종속적 특징을 가진다.
반면, 분할 정복은 작은 문제가 큰 문제에 영향을 끼치지 않는다. 즉, 각 문제들은 서로 독립적이다.
동적 계획법(DP) vs 탐욕법(Greedy)
탐욕법의 경우 현재의 상태에서 최적을 고르기 때문에, 문제에 따라 최적해를 보장하지 않는 경우도 있다.
하지만, 동적 계획법의 경우 모든 가능성을 고려하므로 어떤 문제든 항상 최적해를 보장한다.
🎈대표 문제 1
- SWEA 보급로, Bottom-up 방식
point > 출발점에서 도착점까지 가는데 드는 최소 비용 출력
for tc in range(1,int(input())+1):
N = int(input())
arr = [list(map(int, list(input()))) for _ in range(N)]
dist = [[21e8]*N for _ in range(N)] # 최소 비용을 저장할 배열
q = [(0,0)] # 출발점을 q에 append
dist[0][0] = arr[0][0] # 출발점 최소 비용 초기화
dy = [0,0,1,-1] # 움직일 수 있는 반경
dx = [1,-1,0,0]
while q:
y, x = q.pop(0)
for i in range(4):
ny, nx = dy[i]+y, dx[i]+x
if not(0<=ny<N and 0<=nx<N): continue
tmp = arr[ny][nx] + dist[y][x] # 기존 위치의 최소 비용 + 움직인 위치의 비용
if tmp < dist[ny][nx]: # 비교 후 더 작은 값으로 갱신
dist[ny][nx] = tmp
q.append((ny,nx))
print(f'#{tc} {dist[-1][-1]}')🎈대표 문제 2
- 최소 동전 개수를 사용하여 입력 받은 돈을 거슬러 주는 문제, Bottom-up 방식
point > 동전이 서로 배수 관계가 아님
coin = [1,7,10]
N = int(input()) # 입력 받은 돈
# 코인의 개수(y), 돈(x)을 기준으로 2차원 배열 생성
arr = [[0 for _ in range(N+1)] for _ in range(len(coin)+1)]
for i in range(1,len(coin)+1): # 사용할 코인의 idx
for j in range(1,N+1): # 확인하는 금액
value = coin[i-1]
if j//value == 0: # 몫이 없으면 위의 값 그대로
arr[i][j] = arr[i-1][j]
else: # 몫이 있고
if j % value == 0: # 나머지가 0이면
arr[i][j] = j//value
else: # 나머지가 0이 아니라면
arr[i][j] = min(arr[i-1][j], j//value + arr[i][j % value])
print(arr[len(coin)][N])🎈대표 문제 3
- Knapsack - 배낭 채우기 문제
가방의 용량이 정해져 있을 때, 배낭에 넣을 수 있는 물건들의 총가치가 최대일 때를 구하여라.
N, K = map(int, input().split()) # 총 물건의 개수, 가방의 용량(무게)
# 물건의 개수(y), 무게(x)를 기준으로 2차원 배열 생성
arr = [[0]*(K+1) for _ in range(N+1)]
for k in range(1,N+1): # 1~K번째 물건으로 i kg 을 만들 때 최대 가치
W, V = map(int, input().split()) # 물건의 무게, 물건의 가치
for i in range(1,K+1): # i kg
if i-W >= 0: # 넣을 수 있으면
Sum = V # 새로 확인해주는 물건의 가치 + 나머지 무게의 최대 가치
Sum += arr[k-1][i-W]
# Sum과 이 물건을 사용하지 않았을 때 최대 가치를 비교하여 최댓값을 선택
arr[k][i] = max(Sum, arr[k-1][i])
else: # 넣을 수 없으면 위의 값을 그대로
arr[k][i] = arr[k-1][i]
print(arr[N][K])추가 문제
연봉 200억의 소녀, 콩순이 개발자 성공 신화