이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
https://github.com/AeroCodeX/
이분법(Bisection Method) 요약 |
- 이분법은 단조함수의 해를 구하기 위해 사용.
- 구간을 균일하게 2개로 나누고, 중간값과 비교하여, 정답 가능성이 없는 구간 하나를 배제.
이분법의 이해 |
이분법은 특정 조건을 만족하는 함수의 해를 구하기 위해 사용되며,
전체구간을 균일하게 2구간으로 쪼갠 뒤, 그 중 정답 가능성이 없는 구간 하나를 찾아 배제하는 기법이다.
이분법의 결과에 대해 또 다시 이분법을 수행할 수 있으며,
함수의 해는 점점 구간의 중점에 수렴한다.
배제할 구간을 선택하는 기준은 중간값과 정답의 상대적 위치 (대소관계)이다.
정답이 mid 의 왼쪽에 있다면, 오른쪽 구간은 배제된다.
정답이 mid 의 오른쪽에 있다면, 왼쪽 구간은 배제된다.
예를들어 범위가 [1, 100)인 업-다운 게임에서,
updown(50) == "DOWN" 이라면, [50, 100) 에는 정답이 있을 수 없다.
이분법의 제약 |
이분법을 적용하려는 함수는 다음 규칙을 만족해야 한다.
함숫값이 항상 이전과 같거나 증가(또는 감소)해야 한다.
이분법이 추측범위를 절반으로 줄이는 근거는, 정답과의 상대적 위치인데,
상대적 위치가 아무런 도움이 되지 않는 상황에서는, 그 근거가 없어지는 것 이다.
어떤 등산로에서의 상황을 가정하자.
A : 야, 너 어디야? 나 지금 "M" 지점에 있어.
B : 아 진짜? 너 보다 낮은 곳에 있어. 금방갈게.
Q1. 등산로의 상황이 다음과 같을 때, B가 존재할 가능성이 없는 구간은?
1. 구간 [S, M)
2. 구간 (M, E]
3. 확신할 수 없다.
Q2. 등산로의 상황이 다음과 같을 때, B가 존재할 가능성이 없는 구간은?
1. 구간 [S, M)
2. 구간 (M, E]
3. 확신할 수 없다.
양쪽 구간 전부, M보다 낮은 지점이 있다.
증가상태 |
함숫값이 항상 이전과 같거나 증가하는 상태를 단조 증가라고 부르며,
단조증가 중에서 항상 증가 하는 상태를 강한 증가라고 부른다.
이 때, 단조성을 갖는 함수를 단조 함수라고 부르며,
위의 구분에 따라, 단조 함수는 4개 형태의 증가상태를 가질 수 있다.
단조 함수의 증가상태
- 단조 증가 (Monotonically increasing)
- 단조 감소 (Monotonically decreasing)
- 강한 증가 (= 순증가, Strictly increasing)
- 강한 감소 (= 순감소, Strictly decreasing)
이분법의 제약을 유식하게 재정의하면,
이분법을 적용하려면 단조함수여야 한다라는 것 이다.
증가상태와 해의 유일성 |
단조증가와 강한증가를 구분하는 가장 큰 이유는
같은 함수값을 가지는 다른 x값의 존재성은 매우 중요하기 때문이다.
직설적으로 말하자면,
우리가 찾은 해가 유일해가 아닐 수 있다.
업-다운 게임에서 1차이는 정답으로 인정한다고 했을 때,
N이 정답이라면, N은 유일해가 아니다. [N-left, N+right) 형태로 표현되어야 한다.
N-left : 정답 중, 최솟값
N+right : 정답 중, 최댓값
단조 함수에서는 또 다른 해가 있는지 체크해야 한다.
유일성을 빠르게 검사하는 기법은 이분법(2)에서 설명한다.
정의역의 도메인 |
정의역이 유리수인 경우에는, 정답이 점점 구간의 중점으로 수렴한다.
하지만 무한번 수행한다고 구간의 중점이 정답과 같아질 수 있다고 보장할 수 없다.
컴퓨터가 부동소수점을 데이터로 표현하는데 근본적 한계가 있기 때문인데,
대표적인 예시로 < 0.4 / 2.0 == 0.199999... > 일 수 있다.
때문에, 우리가 예상하는 정답과 같아질 리 없다.
하지만 정의역이 정수로 제한된다면, 정확한 정답을 구할 수 있다.
정수에서는 구간의 중점과 정답지점이 정확히 같아질 수 있기 때문이다.
하지만 유리수도, 100번 정도 반복하고 나면,
구간의 중점이 충분히 정답에 근접한다.
예제 # 오름차순으로 정렬된, 중복허용 배열에서 원소찾기 |
함수의 특성을 생각해보자.
- 오름차순으로 정렬, 중복허용 → 단조 증가
- 정의역이 정수 → 정확한 정답을 찾을 수 있음
- 단조 증가 → 또 다른 해가 있는지 체크
여기서는 또 다른 해가 있는 검사하기 위해,
처음으로 찾은 정답의 옆을 순차탐색했다.
예제 # N차 다항함수의 근 찾기 |
N차 다항함수의 모든 해을 찾아보자.
사용된 그래프는 다음과 같다.
이분법을 적용할 수 있는지 체크하자.
- 단조함수인가? → No.
딱 봐도 전체 구간에서 단조가 아니기 때문에, 이분법을 적용할 수 없다.
하지만, 단조를 만족하는 부분구간의 합으로는 표현할 수 있을 것 같다.
f'(x)==0를 만족하는 점 사이의 인접한 구간은 단조성을 갖는다는 성질을 이용하자.
도함수의 해는 재귀적인 방법으로 구할 수 있다.
전체구간 (MIN, MAX)는 단조성을 만족하지 않지만,
부분구간 (MIN, -0.757) , (-0.757, 0.695) , (0.695, 1.187) , (1.187, MAX)은 단조성을 만족한다.
전체구간에 대해서는 이분법을 적용하지 못했지만,
단조성을 만족하도록 잘라내어 강제로 이분법을 적용할 수 있게 했다.
부분구간의 특징을 정의하자.
단조함수인가? → Yes.
값의 중복을 허용하는가? → No. (순함수)
정확한 정답을 구할 수 있는가? → No. (정의역이 유리수)
결과구간의 중점이 해에 수렴하므로, 평균을 출력하도록 한다.
아래는 실제 프로그램 실행결과이다.
아래는 실제 프로그램의 소스코드이다.
활용 # 문제를 단조함수로 바꿔서 풀기 |
문제를 단조함수로 표현할 수 있다면, 이분법은 매우 효과적인 도구이다.
만약 정의역이 유리수라면 최대오차를 허용하는 문제일 것이며,
100번 정도 반복하면 구간의 중앙이 충분히 정답에 근접한다.
만약 정의역이 정수라면 정확한 정답만을 요하는 문제일 것 이며,
다행히 유한번의 동작으로 정확한 정답을 얻을 수 있다.
