[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

1. 다이나믹 프로그래밍 개요

• 다이나믹 프로그래밍의 2가지 방식
  • 탑다운
    • 재귀 함수를 이용
    • 큰 문제를 해결하기 위해 작은 문제를 호출
  • 바텀업
    • 반복문을 이용
    • 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결
• 메모이제이션 기법을 주로 사용하여 구현

 

2. 다이나믹 프로그래밍

• 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결
  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구현한 정답은 그것을 포함하는 큰 문제에서도 동일하다
• 메모이제이션
  • = 캐싱
  • 다이나믹 프로그래밍을 구현하는 방법 중 하나
  • 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 방법
  • 리스트에 값을 구현
• 다이나믹 프로그래밍 사용 조건
  1. 최적 부분 구조 (Optimal Substructure)
     • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결
  2. 중복되는 부분 문제 (Overlapping Subproblem)
     • 동일한 작은 문제를 반복적으로 해결해야 함

 

2.1. 피보나치

      

      

      

    
    

      <code />
    
### 피보나치 수열 소스 코드 (재귀적)

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

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 프로그래밍)
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]

 

2.2. 다이나믹 프로그래밍 vs 퀵 정렬

• 퀵 정렬
  • 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬
  • 분할 정복 알고리즘 중 하나
• 다이나믹 프로그래밍
  • 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결
  • 다이나믹 프로그래밍은 문제들이 서로에게 영향을 끼친다는 점이 다름

 

3. 탑 다운(Top-Down) vs 바텀 업(Bottom-Up)

• 탑다운(Top-Down)
  • 메모이제이션, 하향식
  • 큰 문제를 해결하기 위해 작은 문제를 호출
• 바텀업 (Bottom-Up)
  • 상향식
  • 다이나믹 프로그래밍의 전형적인 형태
  • 작은 문제부터 차근차근 답을 도출
  • DP 테이블: 바텀업 방식에서 사용되는 결과 저장용 리스트

 

4. 팁

• 다이나믹 프로그래밍의 유형임을 파악하는 것이 우선
  • 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
    • 완전 탐색 알고리즘으로 접근할 때 시간이 너무 오래걸리는 경우
      • 다이나믹 프로그래밍 적용 고려
      • 해결하고자 하는 부분 문제들의 중복 여부 확인
  • 재귀 함수로 구현 후 작은 문제에서 구한 답이 큰 문제에서도 사용되는지 확인
    • 메모이제이션이 사용 가능하다면 코드 개선
  • 보텀업 방식으로 구현하기

 

5. 문제

5.1. 정수 삼각형

1932번: 정수 삼각형

      

      

      

    
    

      <code />
    
import sys
input = sys.stdin.readline

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            left = 0
        else:
            left = triangle[i-1][j-1]

        if j == i:
            right = 0
        else:
            right = triangle[i-1][j]
        triangle[i][j] += max(left, right)

print(max(triangle[n-1]))

 

5.2. 퇴사

14501번: 퇴사

      

      

      

    
    

      <code />
    
import sys
input = sys.stdin.readline

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (n+1)
answer = 0

for i in range(n - 1, -1, -1):
    if table[i][0] + i <= n:
        dp[i] = max(table[i][1] + dp[table[i][0] + i], answer)
        answer = dp[i]
    else:
        dp[i] = answer

print(answer)

 

5.3. 병사 배치하기

18353번: 병사 배치하기

      

      

      

    
    

      <code />
    
import sys
input = sys.stdin.readline

n = int(input())
fights = list(map(int, input().split()))
fights.reverse()

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if fights[i] > fights[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

 

5.4. 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

      

      

      

    
    

      <code />
    
import sys

N = int(sys.stdin.readline())
A = list(map(int, input().split()))
dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

5.5. 계단 오르기

2579번: 계단 오르기

      

      

      

    
    

      <code />
    
import sys
input = sys.stdin.readline

n = int(input())
stairs = [0] * 301
for i in range(1, n+1):
    stairs[i] = int(input())
dp = [0] * 301

dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

if n >= 4:
    for i in range(4, n+1):
        dp[i] = max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i])

print(dp[n])

 

5.6. 징검다리 건너기

22869번: 징검다리 건너기 (small)

      

      

      

    
    

      <code />
    
import sys
input = sys.stdin.readline
INF = int(1e9)

n, k = map(int, input().split())
nums = list(map(int, input().split()))

dp = [INF] * n
dp[0] = 0

for i in range(n-1):
    if dp[i] > k:
        continue
    for j in range(i+1, n):
        dp[j] = min(dp[j], (j-i)*(1 + abs(nums[j]-nums[i])))

if dp[-1] <= k:
    print("YES")
else:
    print("NO")

길이를 구할 때는 INF도 적극적으로 활용