[알고리즘] 동적 계획법(Dynamic Programming), 피보나치

 

 

---

동적 계획법(Dynamic Programming)

한번 계산한 것은 적어두고, 다시 계산하지 말고 재사용하자!

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.

이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

르탄이는 매일 회사로 출근을 합니다.
그래서 출근하는 방법을 어떻게해야 가장 효율적인지를 알고 싶습니다.

집 - 봉천역 - 삼성역 - 코엑스 까지 걸어가는 길인데,
각각의 목적지까지 이동하는 방법은 지하철, 버스, 따릉이, 공유 킥보드가 있습니다.
그래서 다음과 같이 매일 실험해봤습니다.

1일 : 지하철(15분) - 지하철(20분) - 지하철(3분)
2일 : 지하철(15분) - 지하철(20분) - 버스(5분)
3일 : 지하철(15분) - 지하철(20분) - 따릉이(4분)
4일 : 지하철(15분) - 지하철(20분) - 공유 킥보드(6분)
5일 : 지하철(15분) - 버스(10분) - 지하철(3분)
6일 : 지하철(15분) - 버스(10분) - 버스(5분) ........

그런데, 꼭 이렇게 모든 경우의 수를 다 해봐야 할까요?
각 구간마다 수단이 얼마나 걸리는지만 알면 되지 않을까요?
또한, 이미 실험했던 시간은 다시 시도하지 않고 기록해두면 되지 않을까요?
이런 문제를 해결하기 위해서 동적 계획법(Dynamic Programming)이 탄생했습니다!

 

동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘입니다!

 

즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 됩니다.

F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼,

문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있습니다!

 

이처럼 문제를 반복해서 해결해 나가는 모습이 재귀 알고리즘과 닮아있습니다!

그러나 다른 점은, 그 결과를 기록하고 이용한다는 점입니다!

 

여기서 용어정리 간단하게 해드리겠습니다!

 

결과를 기록하는 것을 메모이제이션(Memoization) 이라고 하고,

문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping Subproblem)라고 합니다!

 

아까 예시에서 설명 드렸던 부분에서 각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것을 겹치는 부분 문제,

이미 실험했던 내용은 기록해두고 쓰면 된다는 것을 메모이제이션 이라고 생각하시면 됩니다!

 

즉, 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데,

이 때 사용하는 방법은 메모이제이션을 이용하는구나! 라고 생각하시면 됩니다.

---

피보나치 수열

# 피보나치 수열

fibo(n) = fibo(n-1) + fibo(n-2)

[1, 1, 2, 3, 5, 8, ..]

 

그냥 계산 (재귀적 방법)

def fibo(n):
    if n in [1, 2]:
        return 1
    return fibo(n-1) + fibo(n-2)


assert fibo(10) == 55
assert fibo(100) == 354224848179261915075 # 안끝난다.

이렇게 실행되므로, 연산을 많이 해야하여 실행시간이 매우 길어짐! ex. f(3)을 여러번 반복해서 구해야함.

 

DP

# 메모이제이션
# n번째의 값이 뭔지 기록하는 메모장을 만듦
memo = {1: 1, 2: 1}


def fibo(n):
    # 메모에 n이 저장되어 있다면 계산하지 말고 적힌 값을 반환
    if n in memo:
        return memo[n]
    # 없다면 메모에 새로 저장
    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]


assert fibo(10) == 55
assert fibo(100) == 354224848179261915075

 

---

정수 삼각형

https://www.acmicpc.net/problem/1932

 

testcase_triangle.txt

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

test_triangle.py

import sys

with open('testcase_triangle.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    INF = int(1e9)

    N = int(input())
    
    tri = []
    for _ in range(N):
        tri.append(list(map(int, input().split())))

    # tri 와 똑같은 구조의 memo를 만들고 모든 값을 무한대로 채워놈.
    memo = [[INF] * (i + 1) for i in range(N)]
    # memo[r][c] = r, c에 다다랐을 때 달성할 수 있는 최댓값
    memo[0][0] = tri[0][0]


    # r, c에서의 최댓값을 구하는 함수
    def dp(r, c):
        # r, c 가 있어야 하는 범위가 아니라면 최댓값은 0
        if not (0 <= r < N and 0 <= c < len(tri[r])):
            return 0
       
        # 무한대가 아니라면 이미 적혀있는 것이므로 적힌 값 리턴
        if memo[r][c] != INF:
            return memo[r][c]
        
        # 메모장에 적혀있지 않았다면 구해서 적어준다.
        # 최댓값 = 기존에 내가 가지고 있는 값 + (올 수 있는 값의 후보 둘 중 최댓값)
        memo[r][c] = tri[r][c] + max(dp(r - 1, c - 1), dp(r - 1, c))
        return memo[r][c]


    # 아래에서 위로 올라가는 구조 (제일 아랫줄만 돔)
    for col in range(N):
        dp(N - 1, col)

    print(max(memo[N - 1]))

 

# 부분 반복 구조

(r-1, c-1), (r-1, c-1), (r-1, c+1)
(r, c-1)  , (r, c)    , (r, c+1)

M(r, c) = tri[r][c] + max(M(r-1, c-1), M(r-1, c))

 

memo

각 위치별로 최댓값이 구해진다!

➡️ 내가 원하는 값은? 마지막 배열([24, 30, 27, 26, 24]) 중에 최댓값 ➡️ max(memo[N-1]) 

---

퇴사

https://www.acmicpc.net/problem/14501

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.
5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다.
2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

 

 

testcase_leave.txt

4
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6
10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

 

test_leave.py

import sys

with open('testcase_leave.txt') as f:
    sys.stdin = f
    input = sys.stdin.readline

    T = int(input())
    for _ in range(T):
        N = int(input())
        table = []
        for _ in range(N):
            t, p = map(int, input().split())
            table.append((t, p))

        max_val = 0 # 내가 벌 수 있는 최대의 돈
        
        # idx번 날에 일을 한다면, pay: 여태까지 번 돈
        def dp(idx, pay):
            global max_val
            
            # 원하는 범위가 날짜를 벗어날 때 
            if idx >= N:
                if pay > max_val:
                    max_val = pay
                return

            #
            t, p = table[idx]
            
            # 두가지 경우에 대해 재귀적 탐색
            for i in range(2):
                # 근무를 한다면
                if i == 1:
                    # 날짜가 정해진 범위를 벗어나면 안함
                    if idx + t > N:
                        return
                    # 상담이 끝난 날짜부터 일할 건지 검사
                    dp(idx + t, pay + p)
                # 근무를 안한다면
                else:
                    # 다음날 기준으로 벌 수 있는 최댓값 검사
                    dp(idx + 1, pay)
        dp(0, 0)
        print(max_val)

dp(n번째 날, 여태까지 번 돈)
	-> 근무를 한다면, dp (n+t, 여태까지 번돈 + n번째 날에 번 돈)
	-> 근무를 안한다면 dp(n+1, 여태까지 번 돈)

 

---

 

드디어 알고리즘& 자료구조 강의 완강! 🥳

알고리즘 하나 하나 곱씹으며 이해하느라 생각보다 오래걸렸다.

그래도 목표 기간 내로 완강한 나 자신 칭찬해👏🏻

남은 기간  문제 풀면서, 복습하고 CS 강의도 ㄱㅂㅈㄱ!!