이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
https://github.com/AeroCodeX/
이분법(Bisection Method) 요약 |
단조함수의 경우에는 해가 유일하지 않을 수 있다.
유일해 여부를 판단할 때는, 정답구간의 경계를 기준으로 하자.
증가상태와 해의 유일성 |
저번 장에서 설명했던, 단조함수의 4가지 증가상태와 그 특징을 기억해보자.
단조 함수의 증가상태
- 단조 증가 (Monotonically increasing)
- 단조 감소 (Monotonically decreasing)
- 강한 증가 (= 순증가, Strictly increasing)
- 강한 감소 (= 순감소, Strictly decreasing)
순증가, 순감소는 모든해가 유일해이지만,
단조증가, 단조감소에서는 중복해가 있을 수 있다.
중복해에서 파생되는 문제들 |
중복해가 있다는 것은, 해를 갖는 부분구간이 있다는 것이다.
그렇다면 그 부분구간의 정보를 묻는 문제가 나올 수 있다.
파생문제
정답을 만족하는 최솟값은? → 정답구간의 시작점
정답을 만족하는 최댓값은? → 정답구간의 종료점
정답을 만족하는 값의 개수는? → 정답구간의 길이
파생문제를 어떻게 풀까?
간단하지만 느린 방법 → 처음 찾은 정답에서, 양 옆으로 확장.
복잡하지만 빠른 방법 → 정답구간의 경계점을 탐색.
간단하지만 느린 방법 |
파생문제를 푸는 가장 간단한 방법은,
처음 찾은 정답에서 양 옆으로 확장해나가는 것 이다.
원래 사용하던 bisection 메소드를 그다지 수정하지 않아도 된다.
하지만 이 방법은 매우 치명적인 결함을 가지고 있는데,
배열이 전부 정답이라면, 동작이 순차탐색(Linear Search)과 같아지는 것 이다.
시간 복잡도가 log(N)에서 N으로 급증한다!
아래 그림을 살펴보자.
형태적으로는 배열을 절반으로 나누긴 했지만,
양 옆을 열심히 탐색하느라, 결과적으로 순차탐색과 같아진 것에 주목하자.
순차탐색하는 이분법은 쓸모가 없다.
복잡하지만 빠른 방법 |
이분법 메소드 bisection(x)의 정의를 약간 비틀어보자.
애초에 이분법으로 최대/최소를 찾으면 안될까?
기존의 bisection의 정의
bisection(x) → 단조함수 f(x)가 0이되는 값을 구한다.
새로운 bisection의 정의
bisection(x, dir) → dir에 따라, 단조함수 f(x)가 0이되는 x의 최솟값 또는 최댓값을 구한다.
bisection_min(x) → 단조함수 f(x)가 0이되는 x의 최솟값을 구한다.
bisection_max(x) → 단조함수 f(x)가 0이되는 x의 최댓값을 구한다.
직관성을 높이기 위해 정의역의 도메인은 정수로 제한한다.
최소/최대를 찾는 bisection |
이분법을 진행하다가 정답을 발견했다고 해서, 무작정 반복를 종료하면 안된다.
최솟값/최댓값인지 검사하고 난 뒤에, 다음 반복여부를 판단해야 한다.
찾은값이 최소인지 최대인지 어떻게 알 수 있을까?
힌트는 f(x)가 단조함수라는 것 이다.
찾은 값이 최소인 경우 → f(x-1)이 정답이 아닐 때,
찾은 값이 최대인 경우 → f(x+1)이 정답이 아닐 때,
찾은 값이 최소(최대)가 아니라면? 가능성이 없는 구간을 배제하면 된다.
배제할 구간을 선택하는 기준은 현재 정답과 최소(최대)인 정답과의 상대적 위치이다.
아직 mid 왼쪽에 정답인 해가 있다면, 최솟값은 왼쪽에 있다.
아직 mid 오른쪽에 정답인 해가 있다면, 최댓값은 오른쪽에 있다.
최대(최소)-이분법의 결과에 대해 또 다시 최대(최소)-이분법을 수행할 수 있으며,
해를 만족하는 최댓(최솟)값은 점점 구간의 중점에 수렴한다.
아래는 bisection_max의 동작과정이다.
원래의 bisection 메소드와 기능이 같기 때문에 시간복잡도는 log(n)이며,
bisection_min의 동작과정 또한 위와 별반 다를게 없다.
파생문제 풀이
정답을 만족하는 최솟값은? → bisection_min
정답을 만족하는 최댓값은? → bisection_max
정답을 만족하는 값의 개수는? → bisection_max - bisection_min
