[432] 7주차 동적 계획법, 누적합

동적 계획법(Dynamic Programming)은 우리말로 "기억하며 풀기"로 번역되기도 한다.

1. 동적 계획법(동적 프로그래밍, Dynamic Programming; DP)

가. 개요

동적 계획법은 복잡한 큰 문제를 간단한 작은 문제 여러 개로 나누어 푸는 아이디어를 말합니다.

분할 정복과 차이는 간단한 작은 문제가 반복되어 나타나므로 답을 저장해놓고 재사용하는 데 있습니다.

분할 정복은 작은 문제가 모두 다르다.(ex. 퀵정렬, 병합정렬)

반복되는 작은 문제의 답을 기록해놓고 연산 없이 빠르게 재사용

동적 계획법은 구체적인 알고리즘이 아닌, 알고리즘을 설계하기 위한 접근 방법을 지칭하는 용어입니다.(ex. 분할 정복, 그리디, 백트래킹 등)

나. 동적 계획법을 사용하기 위한 조건

1) 최적 부분 구조(Optimal Substructure)

큰 문제를 작은 여러 문제(부분 문제)로 나누어 풀기 위해서는 작은 문제의 답을 통해 큰 문제의 답을 찾을 수 있어야 합니다.

예를 들어 위와 같은 지도에서 서울에서 부산까지 가는 최단 경로를 찾는 문제가 있습니다.

브루트포스로 모든 경우(서울-대구 3가지, 대구-부산 3가지, 총 9가지)를 따져보는 방법도 있습니다.

하지만 문제를 서울에서 대구까지, 대구에서 부산까지의 부분 문제로 나누어 풀고 더하는 방법이 더 효율적입니다.

이와 같이 부분 문제의 답을 통해 큰 문제의 답을 찾을 수 있는 구조를 최적 부분 구조라고 합니다.

최적 부분 구조를 가지고 있다면 우리는 분할 정복과 동적 계획법을 고민해볼 수 있습니다.

2) 겹치는 부분 문제(Overlapping Subproblems)

큰 문제를 부분 문제로 나누었을 때, 같은 부분 문제가 반복되는 경우가 있습니다.

이런 경우에 분할 정복 보다 동적 계획법이 더 효율적입니다.

예를 들어 피보나치 수열을 구하는 경우, 이전의 값이 여러 번 재사용되는 것을 알 수 있습니다.

이럴 때 매번 다시 연산을 하는 것보다, 부분 문제의 답을 기록해놓고 이후에는 기록된 값을 다시 사용하는 것이 효율적입니다.

다. 동적 계획법으로 풀 수 있는 문제들

1) 피보나치 수열

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

문제에서는 n번째 항만 구하면 되지만, 사실 n번째 항을 구할 때 이전 항들이 계속 필요합니다.

따라서 미리 테이블을 만들어놓고 n까지의 피보나치 수열을 완성합니다.

n = 8
fib = [0] * (n+1)
fib[1] = 1
for i in range(2, n+1):
    fib[i] = fib[i-2] + fib[i-1]
print(fib)
# [0, 1, 1, 2, 3, 5, 8, 13, 21]

이후 n번째 항을 출력하면 됩니다.

2) 2xn 타일링

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

2xn의 직사각형 안에 2x1의 타일을 붙이는 경우의 수를 찾는 문제입니다.

규칙을 찾아 바로 구할 수 있으면 좋겠지만, 대부분의 문제들은 처음 봤을 때 규칙이 떠오르지 않습니다.

그럴 때는 일정 범위까지는 직접 구해보는 게 좋습니다. 왜냐하면 직접 구하다보면 규칙이 보이기도 하기 때문입니다.

n이 1이면, 가능한 경우는 한 가지밖에 없습니다.

n이 2이면, 가능한 경우는 두 가지입니다.

n이 3이면, 가능한 경우는 세 가지입니다.

n이 4이면, 가능한 경우는 다섯 가지입니다.

 

위의 경우를 아래와 같이 나누어 보면 규칙이 보입니다.

바로 이전 단계의 모든 경우에 세로 한 칸짜리를 붙이는 경우와 두 단계 전의 모든 경우에 가로 두 칸짜리를 붙이는 경우의 합으로 나타낼 수 있습니다.

점화식으로 나타내면,

\(a_{i} = a_{i-1} + a_{i-2}\) (단, \(a_{0} = 0, a_{1} = 1\))

으로 나타낼 수 있고, 위에서 본 피보나치 수열과 같다는 사실을 알 수 있습니다.

3) 포도주 시식

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

연속으로 세 잔을 마실 수 없다는 조건이 있어서 당황스러운 문제입니다.

앞에서와 같이 이전 단계의 답을 가지고 다음 단계의 답을 구할 수 있는지 보겠습니다.

이전 단계의 답이 구해져 있다고 가정해보면, 이전 단계의 답이 마지막으로 와인을 마셨는지, 안 마셨는지 알 수 없습니다.

따라서, 이번 단계에서의 최대값은 위 그림과 같은 세 가지 조건 중 하나일 것입니다.

따라서 점화식으로 나타내면,

\(a_{i} = max(a_{i-1}, \:a_{i-2} + 포도주_{i}, \:a_{i-3} + 포도주_{i-1} + 포도주_{i} )\)

(단, \(a_{0} = 0, \:a_{1} = 포도주_{1}, \:a_{2} = 포도주_{1}+포도주_{2} \))

으로 나타낼 수 있고, 이 점화식을 가지고 테이블을 n까지 채워나가면 답을 구할 수 있습니다.

wine = [0] + [6, 10, 13, 9, 8, 1]
memo = [0, wine[1], wine[1]+wine[2]] + [0, 0, 0, 0]
for i in range(3, 7):
    case1 = memo[i-1]
    case2 = memo[i-2] + wine[i]
    case3 = memo[i-3] + wine[i-1] + wine[i]
    memo[i] = max(case1, case2, case3)
print(memo)
# [0, 6, 16, 23, 28, 33, 33]

4) RGB 거리

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

각각의 집을 세 가지 색깔로 칠하는 비용이 주어질 때, 이웃한 집끼리는 다른 색으로 칠하는 경우에 비용을 최소화 하는 문제입니다.

가장 먼저 브루트포스를 생각해보아도 이웃한 집끼리는 다른 색으로 칠해야하므로 적어도 2에 집의 개수 제곱(\(2^{(집의 개수)}\))만큼을 살펴보아야 하므로 집이 30개만 넘어가도 경우의 수가 10억이 넘기 때문에 브루트포스는 불가능합니다.

 

따라서 이전 단계의 답을 가지고 다음 단계의 답을 구할 수 있는지 살펴봅시다.

첫 번째 집과 두 번째 집을 칠하는 경우를 살펴보면 위와 같이 3번의 비교를 통해 더 적은 비용을 기록할 수 있습니다.

이렇게 갱신된 비용은 두 번째 집을 해당 색으로 칠했을 때 첫 번째 집의 비용까지 합쳐진 값이 됩니다.

세 번째 집도 살펴보면 이전에 갱신된 값을 통해 위와 같이 계산이 가능합니다.

결국 최종적으로 세 번째 집을 빨간색(두 번째는 파랑, 첫 번째는 빨강)으로 칠하는 경우가 총 96으로 최소 비용이 되는 것을 알 수 있습니다.

집이 많아져도 집의 개수 당 3번의 비교가 추가되므로 충분히 시간 안에 풀 수 있습니다.

cost = [
    [26, 40, 83],
    [49, 60, 57],
    [13, 89, 99]
]

for i in range(1, 3):
    for j in range(3):
        cost[i][j] += min(cost[i-1][(j+1)%3], cost[i-1][(j+2)%3])

print(*cost, sep="\n")
# [26, 40, 83]
# [89, 86, 83]
# [96, 172, 185]

5) 배낭 문제

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

동적 계획법하면 떠오르는 대표적인 문제인 배낭 문제입니다.

물건마다 담거나 담지 않거나, 두 경우 뿐이므로 2에 물건 개수 제곱(\((2^{물건\: 개수})\))을 하여 모든 경우를 살펴보면(브루트포스) 풀 수 있습니다.

하지만 물건의 개수가 30개만 넘어가도 경우의 수가 10억을 넘어서 현실적인 시간 안에 답을 구하는 게 어렵습니다.

 

또 만약 물건의 크기가 모두 배수 관계에 있다면(예를 들면 10, 50, 100, 500) 물건의 크기 대비 물건의 가치를 계산해 그리디로도 풀 수 있습니다.

하지만 위의 문제는 배수 관계가 아니므로 그리디로도 풀 수가 없습니다.

 

따라서 앞에서와 같이 이전 단계의 답으로 다음 단계의 답을 구할 수 있는지 생각해봅시다.

 

마지막 물건을 담는 경우와 담지 않는 경우 두 경우로 나누어 살펴봅시다.

먼저 마지막 물건을 담으려면, 이전 단계(물건 세 개를 담았을 때 최대값)의 답이 2보다 같거나 작아야 합니다.

왜냐하면 마지막 물건의 크기가 5이므로 물건을 담기 위해서는 여유 공간이 5와 같거나 커야하기 때문입니다.

그리고 마지막 물건을 담지 않는 경우는, 이전 단계의 답이 2보다 큰 경우일 것입니다.

이 두 경우 중 더 큰 값이 정답이 될 것입니다.

문제는 이전 경우가 물건의 개수도 변수로 작용하지만, 담은 물건의 크기도 변수로 작용하고 있습니다.

변수가 두 개이므로 2차원 배열을 만들어서 그곳에 답을 저장하도록 하겠습니다.

 

먼저 물건이 없을 때와 담은 물건의 크기가 0일 때(아무 것도 담지 않음)에는 모두 0으로 초기화 합니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건 1	0
물건 2	0
물건 3	0
물건 4	0

 

물건 1을 담으며 테이블을 채웁니다.

물건 1의 크기가 6이므로 담는 경우 담은 물건의 크기는 6이나 7이 되고, 각각 이전에 담은 물건의 크기가 0이나 1일 때의 값에 물건 1의 가치 13을 더합니다.

여기서 주목할 점은, 물건의 크기가 6이므로 해당 물건을 담았을 때 6이상의 크기가 된다는 점입니다.

담은 물건의 크기가 6보다 작을 때에는 해당 물건을 담지 않은 것이므로 이전 값을 그대로 가져옵니다.

물건 1의 가치가 13이므로 0이나 1일 때의 값에 13을 더한 값과, 이전에 담은 물건의 크기가 6이나 7일 때의 값을 비교하여 더 큰 값을 입력합니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13 vs 0	13 vs 0
물건 2	0
물건 3	0
물건 4	0

 

물건 2(가치 8)도 위와 같은 방법으로 담습니다.

물건 2는 크기가 4이므로 담는 경우 담은 물건의 크기는 4~7(이전에 담은 물건의 크기가 0~3일 때)이 됩니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2	0	0	0	0	8 vs 0	8 vs 0	8 vs 13	8 vs 13
물건 3	0
물건 4	0

 

물건 3(가치 6)도 위와 같은 방법으로 담습니다.

물건 3의 크기가 3이므로 담는 경우 담은 물건의 크기는 3~7(이전에 담은 물건의 크기가 0~4일 때)이 됩니다.

이전에 담은 물건의 크기가 4일 때 값이 8이므로 8에 6을 더하여 계산합니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건 1	0	0	0	0	0	0	13	13
물건 2	0	0	0	0	8	8	13	13
물건 3	0	0	0	6 vs 0	6 vs 8	6 vs 8	6 vs 13	14 vs 13
물건 4	0

 

마지막으로 물건 4(가치 12)도 같은 방법으로 계산합니다.

물건 4의 크기는 5이므로 담는 경우 담은 물건의 크기는 5~7(이전에 담은 물건의 크기가 0~2일 때)이 됩니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건1	0	0	0	0	0	0	13	13
물건2	0	0	0	0	8	8	13	13
물건3	0	0	0	6	8	8	13	14
물건4	0	0	0	6	8	12 vs 8	12 vs 13	12 vs 14

 

이렇게 정리된 표의 맨 오른쪽 아래의 값(물건4, 담은 물건의 크기7)이 답이 됩니다.

그리고 이 값이 결정되는 과정을 살펴보면 어떤 물건들이 선택되었는지도 알 수 있습니다.

물건 4을 담을지 담지 않을지를 되돌아 살펴보면 담지 않는 선택이었습니다.

물건 3을 담을지 담지 않을지를 되돌아 살펴보면 담는 선택이었습니다.

물건 2를 담을지 담지 않을지를 되돌아 살펴보면 담은 물건의 크기가 0일 때 담는 선택이었습니다.

따라서 물건 2와 물건 3을 담아서 만든 값이 답이라는 것을 알 수 있습니다.

담은 물건의 크기	0	1	2	3	4	5	6	7
물건 X	0	0	0	0	0	0	0	0
물건1	0	0	0	0	0	0	13	13
물건2	0	0	0	0	8	8	13	13
물건3	0	0	0	6	8	8	13	14
물건4	0	0	0	6	8	12	13	14

bag = 7
obj = [()] + [(6, 13), (4, 8), (3, 6), (5, 12)]
memo = [[0]*(8) for _ in range(5)]

for i in range(1, 5):
    weight, value = obj[i]
    for bag_weight in range(1, 8):
        case1 = 0
        # 담을 수 있을 때
        if bag_weight >= weight:
            case1 = memo[i-1][bag_weight - weight] + value # 담은 경우
        case2 = memo[i-1][bag_weight] # 담지 않은 경우
        memo[i][bag_weight] = max(case1, case2)

print(*memo, sep="\n")
# [0, 0, 0, 0, 0, 0, 0, 0]
# [0, 0, 0, 0, 0, 0, 13, 13]
# [0, 0, 0, 0, 8, 8, 13, 13]
# [0, 0, 0, 6, 8, 8, 13, 14]
# [0, 0, 0, 6, 8, 12, 13, 14]

2. 누적합

누적합은 배열에 있는 이전 원소들의 값을 모두 합해 놓은 것을 말합니다.

# 원래 배열
li = [1, 2, 3, 4, 5]

for i in range(len(li)-1):
	li[i+1] += li[i]

# 누적합
print(li)
# [1, 3, 6, 10, 15]

누적합은 언제 사용하면 좋을까요? 바로 구간합을 자주 구해야할 때 사용하면 좋습니다.

예를 들어 열흘동안 하루에 공부한 시간을 기록해 배열로 만들었을 경우 아래와 같이 만들 수 있습니다.

[3, 5, 2, 6, 4, 2, 4, 2, 3, 4]

위와 같은 배열은 어떤 날 하루의 공부한 시간을 찾는 데는 효과적입니다.

그러나 어떤 기간동안 공부한 시간(구간합)을 찾는 데는 그 기간의 범위만큼 더하기 연산을 해야하므로 비효율적입니다.

최악의 경우(모든 범위)에는 O(n)만큼의 시간이 걸립니다.

위 배열을 누적합으로 만들면 아래와 같습니다.

[3, 8, 10, 16, 20, 22, 26, 28, 31, 35]

이제는 i번째 날부터 j번째 날까지 공부한 시간을 찾으려면 (j번째 숫자 - (i-1)번째 숫자)(단, 0번째 숫자는 0으로 생각) 계산하면 됩니다.

최악의 경우에도 O(1)의 시간에 구할 수 있습니다.

그림으로 보면 누적합은 위와 같이 미리 쌓아놓은 것과 같고, 구간합은 쌓여 있는 것에서 원하는 구간 만큼 이전에 쌓인 것을 빼면 바로 구할 수 있습니다.

가. 일차원

1) 구간합 구하기 4

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

기본적인 누적합 문제입니다.

배열의 길이가 최대 10만이고, 구간합을 구해야하는 횟수가 최대 10만 번이므로 일일이 구하면 최악의 경우 100억 번의 연산 횟수가 필요합니다.

누적합을 사용하면 최악의 경우에도 10만 번의 연산으로 풀 수 있으므로 제한 시간 안에 답을 찾아낼 수 있습니다.

nums = [5, 4, 3, 2, 1]

# 누적합 만들기
for i in range(4):
    nums[i+1] += nums[i]
    
# 0번째 값(0) 추가하기
nums = [0] + nums

print(nums[3]-nums[1-1]) # 1~3
# 12

print(nums[4]-nums[2-1]) # 2~4
# 9

print(nums[5]-nums[5-1]) # 5~5
# 1

나. 이차원 

1) 구간합 구하기 5

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

이제 이차원 배열로 표 형식에서 행과 열의 특정 범위 내 구간합을 빠르게 구해봅시다.

이차원에서 누적합을 구할 때는 조심해야할 사항이 있습니다.

위 그림과 같이 전체의 합(누적합)을 구하고 싶을 때, A + B + D 를 하면 결과적으로 C가 두 번 더해진 꼴이 됩니다.

따라서 전체의 합을 구하고 싶을 때는 A + B + D - C 를 해야합니다.

 

반대로 구간합 D를 구하고 싶을 때, (전체) - A - B 를 하면 결과적으로 C가 두 번 빠지는 꼴이 됩니다.

따라서 구간합을 구하고 싶을 때는 (전체) - A - B + C 를 해야합니다.

nums = [
    [1, 2, 3, 4],
    [2, 3, 4, 5],
    [3, 4, 5, 6],
    [4, 5, 6, 7]
]

# 계산의 편의를 위해 행과 열에 0번째 항을 추가
nums = [
    [0, 0, 0, 0, 0],
    [0, 1, 2, 3, 4],
    [0, 2, 3, 4, 5],
    [0, 3, 4, 5, 6],
    [0, 4, 5, 6, 7]
]

for i in range(4):
    for j in range(4):
        nums[i+1][j+1] += nums[i][j+1] + nums[i+1][j] - nums[i][j]

print(*nums, sep="\n")
# [0, 0, 0, 0, 0]
# [0, 1, 3, 6, 10]
# [0, 3, 8, 15, 24]
# [0, 6, 15, 27, 42]
# [0, 10, 24, 42, 64]

x1, y1, x2, y2 = 2, 2, 3, 4
print(nums[x2][y2] - nums[x2][y1-1] - nums[x1-1][y2] + nums[x1-1][y1-1])
# 27