정수 수열 S의 부분 수열이란 S에서 0개 이상의 숫자를 지우고 남은 수열을 말한다.
예) [1 2 4]는 [1 5 2 4 7]의 부분 수열
부분 수열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다.
주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 문제.이 문제는 유명한 문제이며 최대 증가 부분 수열 (LIS, Longest Increasing Subsequence). 찾기 문제입니다.
최대 증가 부분 수열을 찾는 문제를 숫자 하나씩으로 조각낸 뒤, 한 조각에서 숫자 하나씩을 선택하는 완전 탐색 알고리즘을 만들어 보자.
수열 A를 입력 받아 LIS의 길이를 반환하는 재귀함수 lis(A)는, A의 모든 증가 부분 수열을 만든 뒤 그 중 가장 긴 것의 길이를 반환한다. 한 조각마다 숫자 하나를 선택. lis(A)는 수열의 첫 번재 수를 고르고 나머지 부분을 재귀적으로 만들것.
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
A[j] |
3 | 2 | 1 | 7 | 5 | 4 | 2 | 6 |
lis(A)가 수열의 첫 숫자로 A[j]를 선택했을 때. A[j]에서 시작하는 증가 수열 중 가장 긴 증가 수열을 찾으려면 A[j+1...]부분 수열에서 A[i]보다 큰 숫자들만 고른 부분 수열 B를 만들고 B의 LIS를 재귀 호출로 계산.
func lis(_ A: [Int]) -> Int {
if A.isEmpty { return 0 }
var ret = 1
for i in 0..<A.count {
var B = [Int]()
for j in stride(from: i+1, to: A.count, by: 1) {
if A[i] < A[j] {
B.append(A[j])
}
ret = max(ret, 1 + lis(B))
}
}
return ret
}이코드는 메모이제이션을 적용하기 까다롭다. 우선 입력이 정수가 아니라 정수의 배열이기 때문 STL의 map과 같은 연관 배열을 써서 메모이제이션 할 수 있지만 이것은 엄청 느리다. A의 정의를 이용해 A를 좀더 간단하게 표현하는 방법을 생각해보자.
A는 항상 다음 두가지 중 하나가 된다.
- 원래 주어진 수열 S
- 원래 주어진 수열의 원소 S[i]에 대해, S[i+1...] 부분 수열에서 S[i]보다 큰 수들만 포함하는 부분 수열
이 정의에서 유념하게 볼 것은 2번 정의에 포함되는 A는 S의 인덱스와 1:1 대응 된다는 점이다.
A로 주어질 수 있는 입력은 전부 N+1가지밖에 없다는 이야기.
그래서 부분 문제 정의를 lis(start) = S[start]에서 시작하는 부분 증가 수열 중 최대의 길이로 문제를 재정의 한다고 하면 아래와 같이 구현 할 수 있다.
var cache = Array(repeating: -1, count: 100)
var S = [1,2,3,4,5,0,1,2,3,4,5]
var n = S.count
var maxLen = 0
for i in 0..<n{
maxLen = max(maxLen, lis2(start: i))
}
print(maxLen)
func lis2(start: Int) -> Int {
var ret = cache[start]
if ret != -1 { return ret }
// 항상 S[start]는 있기 때문에 길이는 최하 1
ret = 0
for next in start..<n {
if S[start] < S[next] {
ret = max(ret, lis2(start: next) + 1)
}
}
return ret
}maxLen를 통해 찾는 법이 아닌 다른 방법도 있다.
import Foundation
var n = Int(readLine()!)!
var S = readLine()!.split(separator: " ").map{Int(String($0))!}
var cache = Array(repeating: -1, count: 101)
//S[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환한다.
func lis3(start: Int) -> Int {
var ret = cache[start + 1]
if ret != -1 { return ret }
ret = 1
for next in stride(from: start+1, to: n, by: 1) {
if start == -1 || S[start] < S[next] {
ret = max(ret, lis3(start: next) + 1)
}
}
return ret
}
print(lis3(start: -1) - 1)사실 이 O(n²) 알고리즘은 LIS를 찾는 가장 빠른 방법이 아니다. O(nlgn)에 LIS를 찾을 수 있는 알고리즘이 있기 때문. 텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지를 추적. 예를 들어 S의 첫 다섯 원소가 [5, 6, 7, 1, 2]라고 하였을 때, 이 부분 수열의 LIS는 길이가 3인 [5, 6, 7] 하나밖에 없다. 반면 길이가 2인 부분 증가 수열은 [5, 6], [5, 7], [1, 2]의 세 개가 있을 수 있다. 이 중 가장 유리한 것은 [1, 2]인데, 다음 수로 3이나 4가 주어질 경우 [1, 2]뒤에는 연결해서 길이 3인 원소를 만들 수 있는데, [5, 6] 뒤에는 연결할 수 없기 때문. 원소를 추가하는 과정에서 다음과 같은 배열을 유지.
C[i] = 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막 값
이 값을 이용하도록 코드를 개선하면 LIS의 길이 k에 대해 O(nk) 시간에 LIS를 찾을 수 있다. 여기서 한발짝 더 나아가 C[]가 항상 순증가한다는 사실을 깨닫고 나면, C[]에서 이분 검색을 함 으로써 LIS를 O(nlgk) <= O(nlgn)에 찾는 알고리즘을 만들 수 있다.
동적 계획법에 익숙해지기 전 어떤 식으로 생각해야 할 지에 대한 대략적 지침
- 모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계
- 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.
- 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 우리의 목표는 가능한 한 중복 되는 부분 문제를 많이 만드는 것. 입력의 종류가 줄어들면 줄어들 수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한도로 활용할 수 있다.
- 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 한다.
- 메모이제이션을 적용한다.
삼각형 위의 최대 경로 문제를 해결한 과정을 이 레시피에 맞춰서 설명할 수 있다.
- 모든 경로를 만들어 보고 전체 합 중 최대치를 반환하는 완전 탐색
path1()알고리즘 구현. path1()가 전체 경로의 최대 합을 반환하는 것이 아니라 (y, x) 이후로 만난 숫자들의 최대 합만을 반환하도록 변경(재정의)- 이렇게 반환 값의 정의를 바꿨기 때문에 이전에 한 선택에 대한 정보인 sum 입력 값이 불필요. 그 이유는 문제에 최적 부분 구조가 성립하기 때문입니다.
- 이 항목은 필요하지 않음.
- 메모이제이션을 적용합니다.
삼각형 문제에서 쓸 일이 없었던 4번 항목의 좋은 예로는 최대 증가 부분 수열 문제를 해결할 때, A가 항상5의 부분 수열이며 S의 각 위치에 1：1 대응된다는 점을 이용해 입력을 배열에서 정수로 바꾼 것을 들 수 있다.
어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부른다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부른다.
두 개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 하였을때. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)라고 부르자. 예를 들어 '1 3 4 7 9'는 '1 9 4'와 '3 4 7'의 JLIS다.
A와 B가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하라.
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합 니다.
입력의 첫 줄에는 테스트 케이스의 수 C(l <= C <= 50)가 주어집니다. 각 테스트
케이스의 첫 줄에는 A와 B의 길이 n과 m(l <= n, m<= 100)이 주어집니다. 다음 줄에는 n개의 정수로 A의 원소들이, 그 다음 줄에는 m개의 정수로 B의 원소들이 주어집니다. 모든 원소들은 32비트 부호 있는 정수에 저장할수 있습니다.
각 테스트 케이스마다 한 줄에 JLIS의 길이를 출력합니다.
3
3 3
1 2 4
3 4 7
3 3
1 2 3
4 5 6
5 3
10 20 30 1 2
10 20 30
5
6
5
두 개의 수열에서 고를 수 있다는 것 뿐이며, 본질적으로는 LIS 찾기 문제와 그다지 다르지 않다. 두 수열의 LIS를 찾아서 각각 합치면 안된다.
수열 S의 최대 증가 부분 수열을 찾는 재귀 함수 lis3()의 정의는 다음과 같았다.
lis3(start) = S[start] 에서 시작하는 최대 증가 부분 수열의 길이
이제 수열이 A, B 두 개로 늘었으니 재귀 함수도 두 개의 입력을 받아야 한다.
jlis(indexA, indexB) = A[indexA]와 B[indexB]에서 시작하는 합친 증가 부분 수열의 최대 길이
두 수의 순서는 지정하지 않았으니, A[indexA]와 B[indexB] 중 작은 쪽이 앞에 온다고 하자. 그러면 이 증가 부분 수열의 다음 숫자는 A[indexA + 1] 이후 혹은 B[indexB + 1]이후의 수열 중 max(A[index], B[indexB])보다 큰 수 중 하나 그리고 A[nextA]를 다음 숫자로 선택했을 경우 합친 증가 부분 수열의 최대 길이는 1 + jlis(nextA, indexB)가 된다. 점화식은 다음과 같다.
이때 NEXT(indexA)와 NEXT(indexB)는 증가 부분 수열의 다음 위치에 올 수 있는 A와 B원소의 인덱스.
lis3()과 같이 A[-1] = B[-1] = -∞로 두고, 이 둘은 항상 JLIS에 포함된다고 가정.
// 입력이 32비트 부호 있는 정수의 모든 값을 가질 수 있으므로
// 인위적인 최소치는 64 비트여야한다.
let NEGINF = Int.min
for _ in 0..<Int(readLine()!)! {
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n, m) = (input[0], input[1])
let A = readLine()!.split(separator: " ").map{Int(String($0))!}
let B = readLine()!.split(separator: " ").map{Int(String($0))!}
let cache = Array(repeating: Array(repeating: -1, count: 101), count: 101)
// min(A[indexA], B[indexB]), max(A[indexA], B[indexB])로 시작하는
// 합친 증가 부분 수열의 최대 길이를 반환한다.
// 단 indexA == index B == -1 혹은 A[indexA] != B[indexB]라고 가정한다.
func jlis(indexA: Int, indexB: Int) -> Int {
// 메모이 제이션
var ret = cache[indexA + 1][indexB + 1]
if ret != -1 { return ret }
ret = 0
let a = (indexA == -1 ? NEGINF : A[indexA])
let b = (indexB == -1 ? NEGINF : B[indexB])
let maxElement = max(a, b)
// 다음 원소를 찾는다
for nextA in indexA+1..<n {
if maxElement < A[nextA] { ret = max(ret, jlis(indexA: nextA, indexB: indexB) + 1)}
}
for nextB in indexB+1..<m {
if maxElement < B[nextB] { ret = max(ret, jlis(indexA: indexA, indexB: nextB) + 1)}
}
return ret
}
print(jlis(indexA: -1, indexB: -1))
}숫자를 세 자리에서 다섯 자리까지로 끊어서 외 우는데, 가능하면 55555나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법 을 택하곤 합니다. 이때 각 조각들의 난이도는 다음과 같이 정해집니다.
| 경우 | 예 | 난이도 |
|---|---|---|
| 모든 숫자가 같을 때 | 333,5555 | 1 |
| 숫자가1씩 단조 증가하거나 단조 감소할 때 | 23456,3210 | 2 |
| 두 개의 숫자가 번갈아가며 나타날 때 | 323,54545 | 4 |
| 숫자가 등차 수열을이룰 때 | 147,8642 | 5 |
| 이 외의모든경우 | 17912,331 | 10 |
원주율의 일부가 입력으로 주어질 때, 난이도의 합을 최소화하도록 숫자들을 세 자리에서 다섯 자리까지 끊어 읽고 싶습니다. 최소의 난이도를 계산하는 프로그램을 작성하세요.
프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C（1 <= C <= 50）가 주어지고, 그 후 C 줄에 하나씩 각 테스트 케이스가 주어집니다. 각 테스트 케이스는 8자리 이상 10,000 자리 이하의 자연수이며, 맨 앞자리가 0일 수도 있습니다.
각 테스트 케이스마다 한 줄에 최소의 난이도를 출력합니다.
5
12341234
11111222
12122222
22222222
12673939
4
2
5
2
14
예제 입력의 숫자들은 다음과 같이 쪼개면 최소 난이도를 얻을 수 있습니다. • 12341234 → {1234,1234} • 11111222 → {11111,222} • 12122222 → {1212, 2222} • 22222222 → {2222, 2222}, {222, 22222} 혹은 {22222, 222} • 12673939 → {1267, 3939} 혹은 {12673, 939}
어떤 방식이든지 완전 탐색으로 이 문제를 해결하기란 불가능하다는 것을 본능적으로 알 수 있다. 사실 이 문제의 모든 답의 수를 계산하는 방법은 그다지 간단하지 않다. （답의 수를 세는 문제도 동적 계획법으로 풀 수 있다.） 이것을 완전 탐색으로 세어본다면. 길이 7인 수열 1111222를 봅시다. 문제의 규칙 에 따르면 이 수열을 쪼갤 수 있는 방법은 두 가지. {1111, 222} 혹은 {111, 1222} 따라서 길이 7인 수열이 n개 있으면 이들을 이렇게 쪼갤 수 있는 방법의 수는 2ⁿ개가 되는데, 길이 10,000인 수열에는 길이 7인 수열이 1,428개가 들어간다.
하지만 적절한 완전 탐색 알고리즘을 만들면 메모이제이션으로 이 문제를 해결할 수도 있다. 이 문제를 푸는 완전 탐색 알고리즘은 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보며 그중 난이도의 합이 가장 작은 조합을 찾아낸다. 각 재귀 함수는 한 번 불릴 때마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 재귀적으로 쪼깬다. 첫 조각의 길이는 3, 4, 5 중의 하나이므로 각 경우마다 하나씩의 부분 문제를 풀어야 한다. 이때 세 개의 부분 문제에 대한 최적해를 각각 구했다고 하면, 전체 문제의 최적해는 다음 세 경우 중 가장 작은 값이 된다.
- 길이 3인 조각의 난이도 + 3글자 빼고 나머지 수열에 대한 최적해
- 길이 4인 조각의 난이도 + 4글자 빼고 나머지 수열에 대한 최적해
- 길이 5인 조각의 난이도 + 5글자 빼고 나머지 수열에 대한 최적해
나머지 수열의 최적해를 구할 때 앞의 부분을 어떤 식으로 쪼갰는지는 중요하지 않다. (최적 부분 구조가 성립한다는 뜻) 따라서 부분 수열의 시작 위치 begin이 주어졌을 때 최소 난이도를 반환하는 함수 memorized()를 다음과 같이 정의할수 있다.
여기서 Nbegin,L은 N[begin]에서 시작하는 길이 L인 부분 문자열이고, classify()는 해당 조각의 난이도를 반환하는 함수라고 할때, 이 함수는 begin이 같을 때 항상 같은 값을 반환하므로, 메모이제션으로 쉽게 최적화 할 수 있다.
아래 코드는 이 문제를 해결하는 동적 계획법 알고리즘을 구현한 것. 이 코드는 크게 숫자의 한 조각이 주어졌을 때 난이도를 판정하는 classify()와 실제 메모이제이션을 구현하는 memorize()로 나뉨. 조각의 난이도를 판정하는 것은 번거롭지만 어렵거나 시간이 오래 걸리는 작업은 아니다. 따라서 효율성보다는 구현의 용이성과 간결함에 초점을 맞춰 구현하는 것이 좋다. 실제 최소의 난이도 조합을 구하는 함수 memorize()의 구현은 점화식으로부터 간단하게 얻을 수 있다. 이 알고리즘에는 최대 n개의 부분 문제가 있고, 각 부분 문제를 해결하는 데 최대 세 개의 부분문제를 본다. 따라서 아래 코드의 시간복잡도는 O(n).
코드가 너무 길어서 링크로 대체 > PI Code
Quantization(양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말합니다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이며, 키가 161,164,178,184인 학생 넷을 ‘160대 둘, 170대 하나, 180대 하나이라고 축약해 표현하는 것 또한 양자화라고 할수있습니다.
1,000 이하의 자연수들로 구성된 수열을 s가지의 자연수만을 사용하도록 양자화하려고 합니다. 양자화를 하는 방법은 여러 가지가 있습니다. 수열 1 2 3 4 5 6 7 8 9 10을 두 가지의 숫자만을 써서 표현하려면, 3 3 3 3 3 7 7 7 7 7과 같이 표현할 수도 있고, 1 1 1 1 1 10 10 10 10 10으로 할 수도 있지요. 우리는 이 중 각 숫자별 오차 제곱의 합을 최소화하는 양자화 결과를 알고 싶습니다.
예를 들어 수열 1 2 3 4 5를 2 2 3 3 3으로 양자화하면 각 숫자별 오차는 -1, 0, 0, 1, 2이고, 오차 제곱의 합은 1 + 0 + 0 + 1 + 4 = 6이 됩니다. 그러나 2 2 2 4 4로 양자화하면 오차 제곱의 합은 1 + 0 + 1 + 0 + 1 = 3이 됩니다. 수열과 s가 주어질 때, 가능한 한 오차 제곱의 합의 최소치를 구하는 프로그램을 작성하세요.
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C(l <= C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 수열의 길이 n(l <= n <= 100), 사용할 숫자의 수 s(1 <= s <= 10)가 주어집니다. 그 다음 줄에 n개의 정수로 수열의 숫자들이 주어지며, 수열의 모든 수는 1,000 이하의 자연수입니다.
각 테스트 케이스마다 한 줄에 주어진 수열을 s개의 수로 양자화할 때 오차 제곱의 합의 최소치를 출력합니다.
2
10 3
3 3 3 1 2 3 2 2 2 1
9 3
1 744 755 4 897 902 890 6 777
0
651
지금까지의 연습 문제와는 달리 이 문제는 주어진 그대로 재귀적인 해법을 찾으려고 하면 성공할 수 없습니다. 단순하게 생각해 보면 양자화된 결과 수열을 답으로 생각하고, 맨 앞의 숫자에서부터 하나씩 채워 나가는 접근 방법을 택하게 됩니다. 주어진 수열 A의 첫 번째 숫자를 어떤 숫자로 표현할 것인지를 결정하고, 나머지 수열에 대해 재귀 호출로 문제를 해결하는 식이지요. 이런 형태의 재귀 호출 함수를 사용하면 될까요?
quantize(A) = A에 속한 수를 양자화해서 얻을수 있는 최소오차제곱의 합
그런데 이 문제에서는 사용할 수 있는 숫자의 가짓수에 제한이 있기 때문에 남은 문제를 재귀적으로 해결할 때는 이 함수처럼 지금까지 사용한 숫자들을 무시할 수가 없습니다. 이미 s가지의 숫자를 다 쓴 상태라면 이 중 하나의 숫자를 선택해야 하기 때문입니다. 다시 말하면 최적 부분 조건이 성립하지 않는다.
quantize() 남은 숫자들만이 아니라 이전 숫자들을 어떤 숫자로 양자화했는지 또한 알아야 하기 때문에, 지금까지 사용한 숫자들의 집합 또한 입력으로 받아야 합니다. 결국 다음과 같은 형태의 함수를 구현하게 됩니다.
quantize(A, U) = U가 지금까지 한 번 이상 사용한 숫자들의 집합일 때 A에 속한 수를 양자화해서 얻을 수 있는 최소 오차 제곱의 합
그러면 quantize()는 A의 첫 번째 숫자를 어떻게 표현할지를 결정하고 나머지를 재귀 호출해서 해결하게 됩니다. 그러나 이런 완전 탐색 코드는 실로 엄청나게 많은 수의 답을 하나하나 만들게 됩니다. 원본 수열에 포함된 수들의 범위가 1,000 이하의 자연수이니, U의 크기가 10인 경우에만도 （1000 10）개의 부분문제가 존재할 수 있다. 메모이제이션에 필요한 메모리를 확보할 수 없는 것은 물론 이고, 아마 인류문명이 멸망할 때까지 답을 구할수 없을 겁니다.
이와 같이 부분 문제의 개수가 너무 많을 때 우리가 시도할 수 있는 방법은 굉장히 많습니다. 그중 이 문제에 유용하게 쓰이는 방법은 답이 항상 어떤 구조를 가질 것이라고 예측하고 그것을 강제하는 것입니다.
답이 갖는 구조를 예측한다고 해서 꼭 복잡한 것은 아닙 니다. 예제 입력을 포함한 작은 입력 몇 개를 손으로 풀어 보면, 두 숫자 a<b에 대해 a에 대응되는 숫자가 b에 대응되는 숫자보다 커서는 안 된다는 사실을 깨달을 수 있습니다.
예를 들어 1을 7로 바꿨는데, 9를 6으로 바꾸는 것은 절대로 최적해가 될 수 없습니다. 대응되는 두 숫자를 서로 바꾸면 항상 더 작은 오차를 얻을 수 있기 때문이죠. 이것을 좀더 일반화하면 다음과 같이 주장할 수 있습니다.
주어진 수열을 정렬하면, 같은 숫자로 양자화되는 숫자들은 항상 인접해 있다!
예를 들어 보면 좀더 당연합니다. {1, 2, 3, 4}를 양자화하는데, 최적해가 {2, 2, 3, 2}와 같은 형태일 리는 없는 거죠. 이렇게 생각하면 이 문제를 해결하는 방법이 보입니다. 우선 입력에 주어지는 수들을 정렬한 뒤, 인접한 숫자끼리 묶음으로 적절히 분할하고, 각 묶음을 한 숫자로 표현해서 오류를 최소화하는 것이지요. 오차 제곱의 합은 각 숫자의 순서가 변하더라도 상관 없기 때문에 이와 같이 풀 수 있습니다.
따라서 이 문제는 이제 주어진 수열을 s개의 묶음으로 나누는 문제가 됩니다. 이것은 비교적 쉽게 재귀적으로 해결할 수 있지요! 매 재귀 호출 때마다, 첫 묶음의 크기가 얼마일지를 결정하면 됩니다. 첫 묶음의 크기를x라고 한다면 이제 나머지 n-x개의 숫자를 s-1개의 묶음으로 나누면 되죠. 이때 나머지 s-1 묶음의 오류 합이 최소여야 전체도 최소 오류이기 때문에, 최적 부분 구조 또한 성 립한다는 것을 알 수 있습니다.
from 번째 이후의 숫자들을 parts개의 묶음으로 묶을 때, 최소 오류 제곱 합을 반환하는 함수 quantize(from, parts)가 있다고 합시다. parts개 의 묶음 중 첫 번째의 크기는 1 이상 n-from 이하의 값이므로, 이들을 각각 다 계산해 보면 되겠지요. 첫 번째 묶음의 크기가 size일 때의 최소 오류는 minError(from, from + size - 1) + quantize(from + size, parts -1)이 됩니다. (minError(a,b)는 a번째 숫자부터 b번째 숫자까지를 하나의 수로 표현했을 때의 최소 오류를 반환 한다고 합시다.)
따라서 다음과 같은 점화식이 성립합니다.
이 점화식을 구현하면 동적 계획법 알고리즘을 얻을 수 있지요. quantize()가 이전 묶음들에 대한 정보를 전혀 입력받지 않는다는 것을 눈여겨봅시다. 남은 숫자들을 최적으로 묶는 데 이전 조각의 정보는 필요가 없지요. 이것은 이 문제에서도 최적 부분 조건이 성립함을 나타냅니다.
위에서 언급한 minError()를 실제로 어떻게 구현해야 할까요? minError{a, b}에서 해야하는 일은크게 두가지입니다.
- 주어진 구간을 어떤 수로 표현해야 할지 결정하기
- 결정한 수 m으로 해당 구간을 표현했을 때 오차를 계산하기
이 문제의 시간 제한은 이들을 가능한 한 간단한 방법을 이용해 풀더라도 문제를 해결할 수 있게끔 조정되어 있지만, 여기에서는 참고 삼아 다른 방법들 또한 이야기해 보겠습니다.
우선 해당 구간을 표현할 숫자를 결정하는 방법들에 대해 생각해 보죠. 무식하게 풀 수 있을까?라는 질문에 가장 적절하게 대답한 예는, 바로 가능한 모든 숫자를 다 시도해 본다는 것입니다. 예를 들어 {74, 81, 96, 100}을 한 숫자로 표현하려면, 74부터 100까지 하나하나 시도해 보며 오류를 최소화하는 숫자를 고릅니다. 모든 구간에 대해 답을 미리 계산해 두려면 이 방법은 이론상 수행해야 하는 반복문의 수가 n^3X1000에 비례하지만, 대부분의 경우 구간 길이는 n보다 짧고, 사용 가능한 종류 수는 1000보다 작기 때문에 시간 안에 나올 수도 있습니다.
복잡한 계산 과정이 귀찮다면 위와 같은 방법을 사용할 수도 있지만, 미분을 이용하면 길이 2 이상인 구간 수열 A[a•••b]에 대해 오차 제곱의 합을 최소화하는 m을 쉽게 찾을 수 있습니다. 오차 제곱의 합을 다음과 같이 풀어 써 봅시다.
이 식은 m에 대한 2차식이고, 2차항의 계수가 양수이므로 미분을 통해 최소점을 찾을 수 있습니다. m에 대해 미분한 뒤, 0이 되는 점을 다음 식을 풀어서 찾을수 있지요.
위 식의 답이 되는 m은 다음과 같다.
즉 모든 값의 평균을 사용하면 오차를 최소화할수 있다는 사실을 알 수 있습니다. 우리는 정수만을 사용할 수 있으므로 평균에 가장 가까운 정수, 곧 반올림한 값을 사용합니다. 주어진 구간의 평균을 계산하는 작업은 O(n)의 시간이 걸리지만, 17장에서 소개하는 기법인 부분 합을 이용해 다음과 같이 O(1)에 계산할수도 있습니다. 우선 다음 정의에 따라 A의 부분 합을 계산합니다.
이 식을 이용하면 A[a]부터 A[b]까지의 합을 다음과 같이 구할 수 있습니다.
(a = 0인 경우는 예외로 칩시다.) 이것을 b-a + 1로 나누면 평균 m은 상수 시간에 구할 수 있습니다. 오차 제곱의 합은 어떻게 구할까요? 역시 또 한 번 ‘무식하게 풀기’를 적용해서, 반복문을 수행하면서 각 수의 오차 제곱을 일일이 구해서 더할 수도 있습니다. 그러나 오차 제곱을 구하는 식을 다음과 같이 전개해봅시다.
마지막 식을 주목해 봅시다. 여기서 계산하는 데 오래 걸리는 부분은 A[]^2의 부분합과 A[]의 부분합인데, 이들은 m과는 관련이 없습니다. 따라서 한 번 더 부분 합을 사용해 이 식을 O(1)에 계산하는 것이 가능합니다. 이상의 방법에 의해 minError(a, b)를 O(1)에 계산할 수 있습니다. 따라서 알고리즘의 전체 시간 복잡도는 부분 문제의 수 0(=)에 각 부분 문제의 답을 계산하는 데 드는 시간 O(n)을 곱한 O(n^2s)가 됩니다.