[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

• 최적화 이론의 한 기술
• 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘
• 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용한다.
• ex. 피보나치 수열에서 중복된 연산을 미리 배열을 만들어두고 값을 저장해두면(메모이제이션) 시간 복잡도 O(N)으로 개선 가능
• 상향식 접근법 : for으로 구현, 작은 문제를 모아 큰 문제 해결, 메모제이션 사용X
• 하향식 접근법 : 재귀함수 구현, 큰 문제를 해결하기 위해 작은 재귀 함수 호출, 메모제이션 사용
• 보통 동적 계획법은 상향식 접근법을 사용

 

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

---

DP 문제 - 1463번 1로 만들기

• 정수 N이 주어질 때, 세 개의 연산을 적절히 사용해서 1을 만드려고 한다. 연산 사용 횟수의 최소값 구하기 

1. 테이블 정의하기

• D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

2. 점화식 찾기

• D[12] = ?
• 3으로 나누거나 D[12] = D[4] + 1
• 2으로 나누거나 D[12] = D[6] + 1
• 1을 빼거나 D[12] = D[11] + 1
• D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)

3. 초기값 정의하기

• D[1] = 0

n = int(input()) # 정수 N
dp = [0]*(n+1) # dp에 계산된 값을 저장해두고
dp[1] = 0

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

print(dp[n])

---

DP 문제 - 9095번 1,2,3 더하기

• 정수 n이 주어질 때, n을 1,2,3의 합으로 나타내는 방법의 수 구하기

1. 테이블 정의하기

• D[i] = i를 1,2,3의 합으로 나타내는 방법의 수

2. 점화식 찾기

• D[4] = ?
• 1+1+1+1, 3+1, 2+1+1, 1+2+1 // (3을 1,2,3 합으로 나타내는 방법) + 1, D[3]
• 1+1+2, 2+2 // (2를 1,2,3 합으로 나타내는 방법) + 2, D[2]
• 1+3 // (1을 1,2,3 합으로 나타내는 방법) + 3, D[1]
• D[4] = D[1] + D[2] + D[3]

3. 초기값 정의하기

• D[1] = 1, D[2] = 2, D[3] = 4 방법의 개수 
• D[i] = D[i-1] + D[i-2] + D[i-3]

tc = int(input())

for _ in range(tc):
    n = int(input())
    if n == 1:
        print(1)
    elif n == 2:
        print(2)
    elif n == 3:
        print(4)
    else:   
        dp = [0] * (n + 1)
        dp[1], dp[2], dp[3] = 1, 2, 4
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        print(dp[n])

---

DP 문제 - 2579번 계단 오르기

• 각 계단에 쓰여 있는 점수가 주어질 때 게임에서 얻을 수 있는 총 점수의 최대값 구하기

1. 테이블 정의하기

• D[i][j] = 현재부터 j개의 계단을 연속해서 밟고 i번째 계단에서 얻을 수 있는 점수 합의 최대값 + i번째 계단은 반드시 밟아야 한다.
• (연속된 세 계단을 모두 밟아서는 안되는 제약조건) 

2. 점화식 찾기

• D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k] // 1개의 계단을 연속해서 밟고, k번째 계단까지 최대값 
  • 1개의 계단을 밟았다 = k-1번째는 밟지 않았다. = k-2번쨰는 무조건 밟았다.
  • S[k] : k번째 계단 점수
• D[k][2] = D[k-1][1] + S[k] // 2개의 연속된 계단을 밟고, k번째 계단까지 최대값
• j는 3개 연속이 불가능하기 때문에 3 이상일 수 없다.

3. 초기값 정의하기

• D[1][1] = S[1], D[1][2] = 0
• D[2][1] = S[2], D[2][2] = S[1] + S[2]

n = int(input()) # 계단의 개수
S = [0]*(n+1)
for i in range(1, n+1):
    S[i] = int(input())

if n == 1:
    print(S[1])
elif n == 2:
    print(S[1]+S[2])
else:
    dp = [[0 for col in range(3)] for row in range(n+1)]
    dp[1][1], dp[1][2] = S[1], 0
    dp[2][1], dp[2][2] = S[2], S[1]+S[2]
    # 계단 오르기 규칙
    # 1. 한 계단 또는 두 계단 오르기 가능
    # 2. 연속 세개 계단 불가능(시작점은 포함X)
    # 3. 마지막 계단 무조건 밟기

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

    print(max(dp[n][1], dp[n][2]))

---

DP 문제 - 1149번 RGB거리

• 집의 색상은 빨강, 초록, 파랑 중 하나의 색상
• 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어질 때, 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값 구하기

1. 테이블 정의하기

• D[i][0] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 빨강
• D[i][1] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 초록
• D[i][2] = i번째 집까지 칠할 때 비용의 최솟값, i번째 집은 파랑

2. 점화식 찾기

• D[k][0] = min(D[k-1][1], D[k-1][2]) + R[k] // 빨강으로 칠할 때 k-1 집은 초록 or 파랑 + R[k] 빨강 비용
• D[k][1] = min(D[k-1][0], D[k-1][2]) + G[k] // 초록으로 칠하면 빨강 or 파랑
• D[k][2] = min(D[k-1][0], D[k-1][1]) + B[k] // 파랑으로 칠하면 빨강 or 초록

3. 초기값 정하기

• D[1][0] = R[1]
• D[1][1] = G[1]
• D[1][2] = B[1]

n = int(input())  # 집 개수
R = [0] * (n + 1)
G = [0] * (n + 1)
B = [0] * (n + 1)
dp = [[0 for col in range(3)] for row in range(n + 1)]
for i in range(1, n + 1):
    color = list(input().split())
    R[i] = int(color[0])
    G[i] = int(color[1])
    B[i] = int(color[2])

if n == 1:
    print(min(R[1], G[1], B[1]))

else:
    # 초기값 설정
    dp[1][0] = R[1]
    dp[1][1] = G[1]
    dp[1][2] = B[1]
    # 집 색칠 규칙
    # 1. 1번의 집 색상은 2번의 집 색상과 같지 않아야 한다.
    # 2. N번 집의 색상은 N-1번의 집 색상과 같지 않아야 한다.
    # 3. 2(<= i <= N-1)번의 집 색상은 i-1번, i+1번 집의 색상과 같지 않아야 한다.

    for k in range(2, n + 1):
        dp[k][0] = min(dp[k - 1][1], dp[k - 1][2]) + R[k] # 이전색상 초록 or 파랑 + 현재 빨강
        dp[k][1] = min(dp[k - 1][0], dp[k - 1][2]) + G[k] # 이전색상 파랑 or 빨강 + 현재 초록
        dp[k][2] = min(dp[k - 1][0], dp[k - 1][1]) + B[k] # 이전색상 빨강 or 파랑 + 현재 파랑

print(min(dp[n][0], dp[n][1], dp[n][2]))

---

DP 문제 - 11726번 2xn 타일링

• 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하기

1. 테이블 정의하기

• D[i] = 2xi 크기의 직사각형을 채우는 방법의 수

2. 점화식 찾기

• D[i] = D[n-1] + D[n-2]
• 2 x 1 타일로 1개씩 채우면 남는 방법의 수 n-1
• 1 X 2 타일로 2개 채우면 남는 방법의 수 n-2

3. 초기값 정하기

• D[1] = 1
• D[2] = 2

n = int(input())
dp = [0]*1001

dp[1] = 1
dp[2] = 2

for i in range(3, 1001):
    dp[i] = (dp[i-1] + dp[i-2]) % 10007
print(dp[n])

 

DP 문제 - 11659번 구간 합 구하기 4

• dp[i] = arr[1] + arr[2] + arr[3] + .. + arr[i]
• dp[i] = dp[i-1] + arr[i]

import sys
n, m = map(int, sys.stdin.readline().split()) # 수의 개수, 합을 구해야하는 횟수
arr = list(map(int, sys.stdin.readline().split()))
dp = [0]*(n+1)
# D[i] = A[1] + A[2] + .. + A[i]
# D[i] = D[i-1] + A[i]
for i in range(1, n+1):
    dp[i] = dp[i-1] + arr[i-1]

for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    print(dp[j]-dp[i-1])