Python으로 비토닉(Bitonic) 시퀀스에서 비토닉 포인트 찾기

비토닉 시퀀스(Bitonic Sequence)란 처음에는 엄격하게 증가하다가, 어느 한 지점을 기준으로 다시 엄격하게 감소하는 수열을 의미합니다. 이때 증가에서 감소로 전환되는 지점을 비토닉 포인트(Bitonic Point)라고 부르며, 사실상 수열의 최댓값에 해당합니다.

다만, 끝까지 계속 증가만 하거나 감소만 하는 단조 수열에는 비토닉 포인트가 존재하지 않습니다.

문제 예시

예를 들어 입력이 [7, 8, 9, 12, 10, 6, 3, 2]라면 출력은 12입니다. 12까지는 값이 계속 커지고, 그 이후부터는 작아지기 때문입니다.

해결 접근 방식

정렬된 배열에서 값을 찾듯이, 이진 탐색(Binary Search)을 활용하면 선형 탐색(O(n))보다 훨씬 효율적인 O(log n) 시간 복잡도로 비토닉 포인트를 찾을 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.

1. binary_search(array, l, r) 함수를 정의합니다.
2. l <= r 조건을 만족하는 동안 반복합니다.
   • 중간 인덱스를 m = (l + r) // 2로 계산합니다.
3. array[m-1] < array[m]이면서 array[m] > array[m+1]이라면, 해당 위치가 증가와 감소가 만나는 지점이므로 m을 반환합니다.
4. array[m] < array[m+1]이라면 아직 증가 구간에 있는 것이므로, 오른쪽 절반(m + 1 ~ r)을 재귀적으로 탐색합니다.
5. 그렇지 않다면 이미 감소 구간에 진입한 것이므로, 왼쪽 절반(l ~ m - 1)을 재귀적으로 탐색합니다.
6. 모든 탐색이 끝나도 찾지 못하면 -1을 반환합니다.

구현 코드

아래는 위 알고리즘을 Python으로 구현한 예제입니다.

def binary_search(array, l, r):
    if (l <= r):
        m = (l + r) // 2
        if (array[m - 1] < array[m] and array[m] > array[m + 1]):
            return m
        if (array[m] < array[m + 1]):
            return binary_search(array, m + 1, r)
        else:
            return binary_search(array, l, m - 1)
    return -1

array = [7, 8, 9, 12, 10, 6, 3, 2]
n = len(array)
index = binary_search(array, 1, n - 2)
if (index != -1):
    print(array[index])

입력

[7, 8, 9, 12, 10, 6, 3, 2]

출력

12

마무리

이처럼 이진 탐색을 응용하면 비토닉 시퀀스의 최댓값을 매우 빠르게 찾을 수 있습니다. 탐색 범위를 절반씩 줄여 나가기 때문에 데이터 크기가 클수록 선형 탐색 대비 성능 차이가 더욱 두드러집니다. 다만 이 방법은 수열이 실제로 비토닉 형태(증가 후 감소)를 이룬다는 전제 하에 동작한다는 점을 유의해야 합니다.