직접 풀기 까다로운 수학 문제의 근사해를 구하는 기법들인 수치 해석 알고리즘을 소개한다. 프로그래밍 대회에 흔히 사용되는 수치 해석 알고리즘은 몇 가지 되지 않지만, 언제 사용할 수 있는지 잘 파악하고 신중하게 구현하지 않으면 걸려 넘어질 수 있는 다양한 함정들이 존재.
수치 해석(numerical analysis)은 직접 풀기 힘든 수학 문제를 근사적으로 푸는 알고리즘과 이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야로, 공학, 과학, 금융공학 등 다양한 범위에 널리 사용된다. 수치 해석을 깊 이 있게 다루는 문제가 프로그래밍 대회에 등장하지는 않습니다만, 기초적인 몇 가지 알고리즘은 자주 유용하게 쓰인다.
그 중 가장 유용하게 사용되는 이분법과 삼분 검색에 대해 소개한다.
이진 탐색과도 밀접하게 연관되어있으므로 우리들에게 친숙하다. 이분법의 이론적인 배경과 구현에 관한 유의사항들을 소개한다.
이분법은 주어진 범위 [lo, hi] 내에서 어떤 함수 f(x)의 값이 0이 되는 지점을 수치적으로 찾아내는 기법.
func f(_ x: Double) -> Double {}
func bisection(_ lo: Double, _ hi: Double) -> Double {
// 반복문 불변식을 강제한다.
if f(lo) > 0 { swap(lo, hi) }
// 반복문 불변식: f(lo) <= 0 < f(hi)
while fabs(hi - lo) > 2e-7 {
var mid = (lo + hi) / 2
var fmid = f(mid)
if fmid <= 0 { lo = mid }
else { hi = mid }
}
// 가운데 값 반환.
return (lo + hi) / 2
}-
위 코드는 f(lo)와 f(hi)의 부호가 다르다는 조건 대신 f(lo)는 항상 0이하이고 f(hi)는 항상 양수라는 반복문 불변식을 유지. 이것을 위해 처음에 주어진 lo, hi의 값을 체크하고 swap함으로써 강제한다. 이 방법의 이유는 이분법의 진행 과정이 반드시 lo<=hi일 필요는 없기 때문. 이와 같은 불변식을 강제함에 따라, f(mid)가 0이하인지 판단하는 것 만으로 두 부분 구간 중 어느 쪽을 선택해야 할지 판단가능.
-
위 코드는 f(x)가 0을 반환하는 경우를 따로 처리하지 않음. f(lo) <= 0 <= f(hi)라는 불변식만 유지한다면 항상 답이 그쪽으로 수렴하기 때문.
-
bisection() 반복문 모두 종료 후 답의 후보 구간의 중간 값을 반환한다. 이는 반복문 불변식에 의한 원하는 답이 [lo, hi]에 있을 때, 이 중 최대 오차를 최소화할 수 있는 답이 중간 값이기 때문.
정확도와 수행 속도 사이에서 적절히 타협 종료 한다. 대부분의 프로그래밍 대회 문제에서는 정답과 아주 작은 오차가 있는 답들 또한 정답으로 인정한다. 그게 보통 2e-7정도가 되며 위 와같은 코드에서 2e-7을 종료조건으로 사용한 이유가 그것이다.
크기가 작을 때는 훌륭하게 동작하지만, 값의 크기가 커지면 문제가 생길 수있다.
부동소수점은 가수부(mantissa)라고 부르는 정수 부분과 이 변수에서 소수점의 위치를 나타내는 지수부(exponent)의 조합으로 표현된다. 표현할 수 있는 수의 집합이 제한되어 있다. 따라서 숫자의 절대 값이 커지면 커질수록 표현할 수 있는 수들이 듬성듬성해지는데.
// 종료되지 않는다.
func infiniteBisection() {
var lo = 123456123456.1234588623046875
var hi = 123456123456.1234741210937500
while (abs(hi - lo) > 2e-7) {
hi = (lo + hi) / 2.0
}
}이전에 배운 대로 lo와 hi를 double 변수형으로 표현해 보면 지수 비트와 부호 비트가 완전히 똑같고, 가수 비트는 최하위 비트를 제외하고 완전히 똑같습니다. 따라서 이 두 실수 사이에 들어가는 IEEE 754 실수는 존재할 수 없습니다.
그래서 경험 많은 프로그래밍 대회 참가자들은 이와같은 방법을 쓰지 않는다.
단순하고도 유용한 방법으로 while문을 for문으로 대체하는것. 반복문을 100번 수행하면 우리가 반환하는 답의 절대 오차는 |lo - hi| / 2^101이 된다. 2^101은 대략 서른한 자리의 수로, |hi -lo|가 대략 10^20미만의 수이면 오차는 항상 10^-7보다 작다. 따라서 큰 숫자를 다루는 경우에도 충분히 답을 구할 수 있다. 또한 최대 수행 시간을 예상하기도 수월하다. 반복문 내부를 100번 수행할 수 있는가만 확인하면 되기 때문.
// 위가 최대치를 찾고 싶어하는 함수.
func f(_ x: Double) -> Double {}
// [lo, hi] 구간에서 f(x)가 최대치를 갖는 x를 반환한다.
func ternary(_ lo: Double, _ hi: Double) -> Double {
var lo = lo, hi = hi
for _ in 0..<100 {
let a = (2*lo + hi) / 3.0
let b = (lo + 2*hi) / 3.0
if f(a) > f(b) {
hi = b
} else {
lo = a
}
}
return (lo + hi) / 2.0
}미분할 수 없는 함수에도 사용할 수 있으며, 국소 탐색보다 훨씬 빠르며 수렴 판정이 용이하기 때문.
쓰는 곳
- 볼록(Convex) 함수와 오목(Concave) 함수
- 볼록 껍질(Convex Hull)
심슨 방법은 주어진 구간의 함수를 2차 함수로 근사해서 적분하며, 적분하는 함수가 2차 이하의 함수라면 항상 정확한 값을 반환하기 때문에 특히 유용.