[알고리즘] 이분법(Bisection method)

※ 해당 포스팅은 개인의 공부 정리용 글입니다. 틀린 내용이 있다면 추후 수정될 수 있습니다.

※ 해당 포스팅은 하기 출처들을 참조하였습니다.

- https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84%EB%B2%95_(%EC%88%98%ED%95%99) 

 

 

 

 

 이번 포스팅에서는 이분법 알고리즘에 대해 알아보겠습니다.

1. 이분법(Bisection Method)의 정의

 이분법(Bisection method)이란 수학에서 해를 구하는 접근법입니다. 해가 반드시 존재하는 폐구간을 정한 뒤, 중간 값이 해를 만족하는지 검사한 후 결과에 따라 폐구간의 범위를 좁혀가며 계산해나가는 방식입니다.

 

그림 1. y= ax + b

 

상기 그림은 y = ax + b의 그래프를 그린 것입니다. 단순한 1차 함수이므로 바로 x = -b/a라는 해를 찾을 수 있지만, 해당 함수에 이분법을 적용하여 해를 찾는 예를 들어보도록 하겠습니다. 

 

 우선 b > 0, a > b 라는 조건이 걸려있다면 a,b는 모두 양수이므로 -b/a는 반드시 음수가 됩니다. 또한 a > b 이므로 b/a는 1보다 작은 값이고, 따라서 -b/a는 -1보다 큰 값이 됩니다. 따라서 폐구간의 최솟값을 -1로, 최댓값을 0으로 잡으면 해당 구간안에 반드시 해가 존재하게 됩니다.

 

그림 2. 폐구간 검사(0보다 작은 경우)

그림 3. 폐구간 검사(0보다 큰 경우)

 이제 폐구간의 중간값을 함수에 넣어 해를 만족하는지 검사합니다. 그림 2처럼 계산 결과가 0보다 작다면 해가 중간값보다 큰 값이라는 뜻이므로, 폐구간의 최솟값을 방금 검사한 중간값으로 변경합니다. 그림 3처럼 계산 결과가 0보다 크다면 해가 중간값보다 작은 값이라는 뜻이므로, 폐구간의 최대값을 방금 검사한 중간값으로 변경합니다. 해당 과정을 반복하면 매 검사 후 폐구간의 크기가 절반으로 줄어들게 되고, 결국 해를 발견하게 됩니다.

 

 

2. 이분법 알고리즘

 이러한 이분법을 활용하여 조건을 만족하는 값을 찾는 문제에 사용할 수 있습니다. 이분법 자체는 알고리즘이라기 보다는 일종의 방법론으로 특정 값을 구하는 문제라면 사용 가능하지만, 보통 다음과 같은 문제에 활용합니다. 

 

- 1) 문제의 해(원하는 값)를 포함하는 폐구간을 설정할 수 있는 문제(최댓값과 최솟값을 정할 수 있는 문제)

- 2) 문제의 해(원하는 값)가 정수로 떨어지는 문제(실수도 적용은 가능하나, 종료 조건을 설정하기 어려워짐)

- 3) 해를 구하는 데 정해진 공식이 없는 문제(특정 공식이나 알고리즘이 있다면 이분법으로 접근할 이유가 없음)

 

 상기 조건들을 만족한다면, 이분법을 적용하기에 적합합니다. 다음은 C#으로 구현한 이분법 적용 예시입니다(간단한 예를 들기 위해 3번을 무시하고 1차 함수를 이용했습니다). 

static void Main(string[] args)
{
    int high = int.MaxValue;
    int low = 0;

    while(low < high)
    {
        int mid = (low + high) / 2 + 1;
        if (Check(mid)) // 조건 만족
            low = mid;
        else
            high = mid - 1;
    }
    Console.WriteLine($"가능한 최댓값: {low}");
}

// 조건 체크(y = -2x + 10000)
static bool Check(int val)
{
    return val * (-2) + 10000 >= 0 ? true: false;
}

사진 1. 이분법 예시

 상기 코드에서는 해가 양수가 되도록 y= -2x + 10000의 해를 구하는 과정을 작성하였고 최솟값은 0, 최댓값은 아주 큰 양수로 설정하였습니다. 중간값은 ((최솟값 + 최댓값) / 2 + 1)로 계산하였고, 조건을 만족하지 않을 경우 최댓값을 (중간값 - 1)로 설정하였습니다. 이는 최댓값과 최솟값을 정확하게 중간값으로만 계산할 경우, 차이가 1이 되면 무한 루프에 빠질 수 있기 때문입니다(ex. (5000 + 5001) / 2 = 5000).

 

 조건 체크(함수 계산) 내용은 별도의 함수 Check()로 작성하였고, 계산값이 0 이상이라면 true, 0보다 작다면 false를 반환하도록 했습니다. 이제 반복문을 돌며 조건 체크 결과가 true라면 최솟값을 증가, false라면 최댓값을 감소시키고 이를 반복하면 원하는 값을 구할 수 있습니다.

 

 

3. 결론

 이분법은 적용하기 적합한 문제는 많지 않지만, 구현이 비교적 간단하므로 이분법을 적용할 수 있다면 활용하는 것이 좋습니다. 폐구간의 범위를 매 조건 확인 후 절반으로 줄이므로, O(log(n))의 시간복잡도로 원하는 값을 찾을 수 있습니다. 다만 조건 체크 로직이 복잡할 경우(특히 조건 체크 내에서 반복문이 사용될 경우) 시간복잡도가 증가하게 되므로, 조건 체크 로직을 최대한 간결하게 구현할 수 있도록 해야겠습니다.