새로운 알고리즘을 어떻게 고안할 것인가에 대해 공부했지마만, 새로운 알고리즘을 만드는 것이 프로그래밍 대회의 전부는 아님. 적절한 추상화와 모델링 과정을 거쳐 알고리즘을 적용하는 것, 정확한 코드를 작성하는 것 또한 대회에서 평가하는 중요한 역량임.
13장 수치해석
13.1 도입
직접 풀기 힘든 수학 문제르 근사적으로 푸는 알고리즘과 이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야.
13.2 이분법
이분법의 정의
주어진 범위내에서 어떤 함수의 값이 0이 되는 지점을 수치적으로 찾아내는 기법임. 꼭 단조 함수가 아니더라도 답이 여러 개 있는 함수라도 연속이기만 하다면 이분법을 사용해 근을 찾을 수 있음. 이분법은 매 반복마다 구간의 크기를 절반으로 줄여 나감.
double f(double x);
double bisection(double lo, double hi) {
if (f(lo) > 0)
swap(lo, hi);
while (fabs(hi - lo) > 2e-7) {
double mid = (lo + hi) / 2;
double fmid = f(mid);
if (fmid <= 0)
lo = mid;
else
hi = mid;
}
return (lo + hi) / 2;
}
절대 오차를 이용한 종료 판정
이분법에서 가장 중요한 부분은 while문의 종료 조건임. while문을 많이 수행할수록 오차가 줄어들 테지만, 알고리즘을 영원히 수행할 수는 없는 노릇이니 우리는 정확도와 수행 속도 사이에서 적절히 타협하는 종료 조건을 선택해야 함. 그러나 모든 경우에 안정적으로 동작하는 이분법의 종료 조건을 선택하기란 놀랍도록 어려움. 반복문 불변식을 강제하기 위해 lo > hi가 될 수도 있기 때문에 항상 hi-lo의 절대값을 취해야 한다는 데 유의하세요.
상대 오차를 이용한 종료 판정
lo, hi가 음수인 겅우 코드는 복잡해짐.
정해진 횟수만큰 반복하기
이와 같은 방법은 절대로 무한 반복에 빠지지 않으며, 프로그램의 최대 수행 시간을 예상하기도 쉽다는 장점이 있음. 반복문 내부를 100번 수행할 수 있는가만 확이낳면 되기 때문에.
예제: 단변수 다항 방정식의 수치적 해법
어떤 함수의 극점은 항상 미분 값이 0이 되는 위치에 있음. 극점이란 함수가 증가하다가 감소하는 위치, 혹은 감소하다가 증가하는 위치이기 때문에, 해당 지저메서는 기울기가 항상 0이기 때문임. 따라서 주어진 다항식을 미분한 뒤 재귀 호출로 해당 다항식이 0이 되는 지점을 찾고, 여기서 얻은 극점들 사이에서 이분법을 이용해 방정식의 근을 찾는 알고리즘을 작성할 수 있음.
13.5 삼분 검색
라면 끓이기
13.8 다른 주제들
14. 정수론
14.1 도입
14.2 소수
15. 계산기하
15.1 도입
15.2 계산 기하의 도구들
댓글