[이코테] 동적계획법 (Dynamic Programming) 개념 및 문제 풀이 정리

 

본 포스팅은 유투브에 온라인 배포되어 있는 나동빈 님의 이코테 강의를 수강하며 정리한 내용을 기록한 것입니다. 자세한 내용이 궁금하다면, 링크를 참고하시길 바랍니다.

 

포스팅 내 코드 블록은 깃허브에서 찾을 수 있음. 수정 필요

 

목차

 

개념 정리

동적계획법(Dynamic Programming)이란?

• 메모리를 활용하여 시간 효율성을 비약적으로 향상시키는 방법
• 두 가지 조건할 때 사용할 수 있음
• 이미 계산한 결과를 메모리에 저장하여, 다시 계산하지 않도록 함
• Top-down 방식과 Bottom-up 두 가지 접근 방식이 있는데, Bottom-up 방식을 지배적으로 사용하는 편

 

DP의 조건

1. 최적 부분 구조 (Optimal substructure): 큰 문제를 작은 문제로 쪼갤 수 있어야 함
2. 중복되는 부분 문제 (Overlapping subproblems): 쪼갠 작은 문제들 중 중복되는 문제가 있어야 함

 

Top-down 방식, Memoization(메모이제이션)

• 주로 재귀적인 구조로 문제 해결
• 큰 문제를 해결하기 위해 작은 하위 문제들로 나누어가며, 이미 계산한 하위 문제의 결과를 저장하고 재사용함.
• 일반적으로 메모이제이션을 위해 배열이나 해시맵을 사용. 배열명은 d, dp, cache 등으로 지정
• 탑다운 방식의 예시로는 피보나치 수열을 들 수 있음.

 

Bottom-up 방식

• 작은 하위 문제부터 시작하여 큰 문제까지 해결해나가는 방식
• 일반적으로 반복문을 사용하여 구현
• Bottom-up 방식의 예시로는 최장 공통 수열(Longest Common Subsequence)을 구하는 문제가 있음.

 

DP VS 분할 정복

• DP와 분할 정복은 모두 문제를 효율적으로 해결하는 알고리즘 설계 기법이나 차이가 있음
• DP는 큰 문제를 작은 하위 문제로 분할하고, 작은 하위 문제들의 중복 계산을 포함하고 있는 경우 주로 사용됨.
• 분할 정복은 문제를 더 작은 하위 문제로 분할하여 해결하는데, 하위 문제가 서로 독립적인 경우 사용됨. 병합 정렬, 퀵 정렬, 이진 검색 등이 대표적인 예시
• 요약하면, DP는 중복을 피하며 쪼개어 해결하고, 분할 정복은 쪼개어 해결하는 것 자체에 초점을 두는 풀이 방법. 하위 문제의 중복이 있으면 DP, 중복없이 독립적이면 분할 정복을 사용한다.

 

하향식의 대표적인 예) 피보나치 수열

• DP의 가장 대표적인 예
• 피보나치 수열 문제는 점화식(인접항 사이의 관계식)으로 나타낼 수 있

 

점화식 예

$$ a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1 $$

 

• 점화식으로 나타낼 수 있다면, 재귀함수로 바로 구현 가능함
• 단 기본적인 재귀 함수를 풀 경우, $2^N$의 시간복잡도를 가짐

 

기본 재귀 함수로 구현한 예)

# simple way
def _fibo(n):
    if n==1 or n==2:
        return 1
    else:
        result = fibo(n-1) + fibo(n-2)
        return result

 

- 피보나치 수열은 DP, 특히 재귀를 사용하는 Top-down 방식의 대표적인 예로, 재귀 함수로 풀되, 이미 계산한 값을 메모이제이션하는 방식으로 아래와 같이 풀 수 있음

- 이렇게 해결할 경우, O(N)의 시간복잡도를 가져 더 효율적이게 됨

 

Top-down 방식으로 푼 예)

d = [-1] * (n+1)

d[1] = 1 
d[2] = 1 

# top-down
def fibo(n):
    if d[n]!= -1: 
        return d[n]
    else:
        d[n] = fibo(n-1) + fibo(n-2)
        return d[n]

 

 

Bottom-up 방식으로 푼 예)

# bottom-up
def _fibo(n):
    d = [-1] * (n+1)
    d[1] = 1 
    d[2] = 1 

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

 

문제 풀이

 

개미병사 문제

---

요약

- 최소 한 칸 이상 떨어진 식량 창고를 털어야 할 때, 약탈가능한 최댓값 구하기

 

점화식

$$ a_n = max(a_{n-1}, a_{n-2}+a_n) $$

 

풀이 코드

# 이코테: 개미 전사 문제

n = int(input())
array = list(map(int, input().split()))
d = [0]*100

d[0] = array[0]
d[1] = array[1]

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

print(d[n-1])

 

1로 만들기

---

문제 요약

• 주어진 수를 1로 만드는 최소 연산 개수
• 어떤 문제에서는 큰 수로 나누는 게 무조건 유리하지만, 이 문제의 경우 큰 수로 나누는 것보다 작은 수로 나누는 것이 더 유리하기도 함

해결 방법

5, 3, 2로 나누거나 -1 을 한 값의 연산 최소 숫자 중 가장 작은 수를 가지는 연산+1이 현재의 연산 최소 개수이다.

 

풀이코드

# 이코테: 1로 만들기
n = int(input())
d = [0]*(n+1)

d[1] = 0 

for i in range(2, n+1):
    options = []
    if not i%5:
        options.append(d[i//5])
    if not i%3:
        options.append(d[i//3])
    if not i%2:
        options.append(d[i//2])
    options.append(d[i-1])

    d[i] += min(options) + 1 
    print(i, options)

print(d[-1])

 

효율적인 화폐 구성

---

문제 요약

• 주어진 화폐 종류를 최소로 사용하여 목표 금액을 만드는 문제

풀이 전략

• 모든 화폐 종류에 대해, 해당 화폐를 사용하기 전 금액에서의 최소 화폐 개수를 찾아 최솟값에 1을 더해 현재 금액의 최소 화폐 개수를 구함

 

풀이 코드

n, m = list(map(int, input().split()))
money = sorted([int(input()) for i in range(n)])
d = [0]*(m+1)

for i in range(1, m+1):
    options = []
    for m in money:
        if m>i:
            break
        elif d[i-m] >= 0:
            options.append(d[i-m]+1)

    print(i, options)
    if options:
        d[i] = min(options)
    else:
        d[i] = -1

print(d[-1])

 

금광

---

문제 요약

주어진 2차원 맵을 움직이며 캘 수 있는 최대의 금의 양을 반환

단 한 컬럼은 한 번만 지나갈 수 있고, 다음 컬럼은 이전 컬럼의 오른쪽 위, 오른쪽 동일위치, 오른쪽 아래 위치로만 움직일 수 있음

 

풀이 전략

컬럼별 -> 로우별로 움직이면서 3가지 방향에 대한 최댓값에 현재 값을 더해 맵을 갱신

갱신이 완료된 후, 마지막 컬럼의 최댓값을 반환할 값으로 한다

 

풀이 코드

def solution(n, m, maps):
    for im in range(1, m): 
        for in_ in range(n):
            options = [maps[in_][im-1]]
            if in_ > 1:
                options.append(maps[in_-1][im-1])
            if in_ < n-1:
                options.append(maps[in_+1][im-1])
            maps[in_][im] = maps[in_][im] + max(options)
    return max([row[-1] for row in maps])

if __name__ == '__main__':
    test_nums = int(input())

    test_data = []  
    for i in range(test_nums):
        n, m = list(map(int, input().split()))
        maps = list(map(int, input().split()))
        maps = [maps[i*m:(i+1)*m] for i in range(n)]
        test_data.append((n,m,maps))

    for td in test_data:
        print(solution(td[0], td[1], td[2]))

 

병사 배치하기

---

문제 요약

• 전체 병사의 전투력을 내림차순으로 배치하기 위해 열외해야 하는 병사의 최소 수
• 병사의 위치는 변경할 수 없고, 일부 병사를 열외하는 방식으로 구성해야 함

풀이 전략

• 가장 긴 증가하는 수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 DP
  • {4,2,5,8,4,11,15} 가 있을 때, LIS는 {4,5,8,11,15}임
  • LIS 알고리즘은, i에 대하여 i보다 작은 모든 j에 대하여 배열의 값이 j보다 i가 더 큰 경우(오름차순인 경우)에만 j에서의 최대 길이와 i에서의 최대 길이의 최댓값으로 i의 최대 길이를 갱신함 (오름차순이 아닌 경우에는 +1로 갱신이 불가능하기에 고려 대상에서 배제)
  • $$ 0<j<i일 때, d[i] = max(d[i], d[i-1]+1) if array[j] < array[i] $$
• LIS를 이 문제에 적용하려면, 우선 배치를 거꾸로 뒤집고, 위 점화식을 적용한 뒤에 전체 길이에서 최대 부분 시퀀스의 길이를 빼면 열외 병사의 수가 나오게 됨.

 

풀이 코드

# 이코테: 병사 배치하기
## 풀이 전략 - LIS 알고리즘

n = int(input())
soldiers = list(map(int, input().split()))[::-1]
d = [1]*n

for i in range(1, n): 
    options = []
    for j in range(i):
        if soldiers[i] > soldiers[j]:
            d[i] = max(d[i], d[j]+1)
    print(soldiers, d)

print(n-d[-1])