8-5. 코딩 테스트: 이진 탐색 문제 풀이

1. 이진 탐색의 기본 원리

이진 탐색 (Binary Search)은 정렬된 데이터 집합에서 특정 값을 효율적으로 찾는 알고리즘입니다. 마치 사전에서 단어를 찾는 과정과 유사합니다. 사전을 펼쳐서 원하는 단어가 있는 페이지를 대략적으로 짐작하고, 해당 페이지의 단어들을 확인한 후, 원하는 단어가 앞쪽에 있는지 뒤쪽에 있는지 판단합니다. 그에 따라 탐색 범위를 절반으로 줄여가며 원하는 단어를 찾습니다.

이진 탐색의 핵심은 탐색 범위를 지속적으로 반으로 줄여나가는 것입니다. 정렬된 데이터라는 전제가 있기 때문에 가능하며, 데이터가 정렬되지 않았다면 사용할 수 없습니다. 이진 탐색은 선형 탐색 (Linear Search)보다 훨씬 빠르며, 특히 데이터의 양이 많을수록 그 효율성은 더욱 두드러집니다.

1) 왜 이진 탐색인가?

선형 탐색은 데이터를 처음부터 끝까지 하나씩 비교하며 탐색합니다. 데이터가 n개일 때, 최악의 경우 n번의 비교를 수행해야 합니다. 반면, 이진 탐색은 탐색 범위를 절반씩 줄여나가므로, 최악의 경우에도 $O(log_2 n)$ 시간 안에 원하는 값을 찾을 수 있습니다.

예를 들어, 1024개의 데이터가 있다면, 선형 탐색은 최대 1024번의 비교가 필요하지만, 이진 탐색은 단지 10번의 비교만으로도 찾을 수 있습니다 ($log_2 1024 = 10$).

2. 이진 탐색의 단계별 프로세스

이진 탐색은 다음과 같은 단계를 거칩니다.

1. 초기화: 탐색 범위의 시작 인덱스 (left)와 끝 인덱스 (right)를 설정합니다. left는 배열의 첫 번째 요소, right는 배열의 마지막 요소의 인덱스가 됩니다.
2. 중간점 계산: 현재 탐색 범위의 중간 인덱스 (mid)를 계산합니다. mid = (left + right) / 2 (정수 나눗셈)
3. 값 비교: mid 위치의 값과 찾고자 하는 값을 비교합니다.
   • 찾고자 하는 값 > mid 위치의 값: left를 mid + 1로 설정하여 탐색 범위를 오른쪽 절반으로 좁힙니다.
   • 찾고자 하는 값 < mid 위치의 값: right를 mid - 1로 설정하여 탐색 범위를 왼쪽 절반으로 좁힙니다.
   • 찾고자 하는 값 == mid 위치의 값: 탐색을 종료하고, mid 인덱스를 반환합니다.
4. 반복: left가 right보다 작거나 같을 때까지 2단계와 3단계를 반복합니다. 만약 left가 right보다 커지면, 탐색할 값이 배열에 없다는 의미입니다.

1) 예시를 통한 이해

다음과 같은 정렬된 배열 arr = [2, 5, 7, 8, 11, 12]에서 값 11을 찾는 과정을 생각해 봅시다.

1. 초기화: left <mark class="highlight"><strong><u> 0, right </u></strong></mark> 5
2. 1차: mid <mark class="highlight"><strong><u> (0 + 5) / 2 </u></strong></mark> 2, arr[2] = 7. 11 > 7 이므로, left = 3
3. 2차: mid <mark class="highlight"><strong><u> (3 + 5) / 2 </u></strong></mark> 4, arr[4] = 11. 11 11 이므로, 탐색 종료. 인덱스 4 반환.

2) 핵심 아이디어

이진 탐색의 핵심은 탐색 범위를 좁혀나가는 방식에 있습니다. 매 단계마다 탐색 범위를 절반으로 줄여나가기 때문에, 매우 빠르게 원하는 값을 찾을 수 있습니다. 이러한 분할 정복(Divide and Conquer) 방식==은 이진 탐색의 효율성의 핵심입니다.

3. 이진 탐색 구현 (Python)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # 정수 나눗셈
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 값을 찾지 못한 경우

1) 코드 해설

• binary_search(arr, target) 함수는 정렬된 배열 arr과 찾고자 하는 값 target을 입력으로 받습니다.
• left와 right 변수를 초기화하여 탐색 범위를 설정합니다.
• while 루프는 left가 right보다 작거나 같을 때까지 반복됩니다.
• mid 변수를 계산하여 중간 인덱스를 구합니다. 정수 나눗셈(//)을 사용합니다.
• if-elif-else 구문을 사용하여 arr[mid]와 target을 비교합니다.
• 만약 값을 찾지 못하면 -1을 반환합니다.

2) 주의사항

• 반드시 정렬된 배열에서만 작동합니다.
• mid를 계산할 때, 정수 나눗셈을 사용해야 합니다.
• while 루프의 조건은 left <= right입니다. left < right로 하면, 마지막 값이 비교되지 않을 수 있습니다.

4. 이진 탐색의 시간 복잡도

이진 탐색의 시간 복잡도는 $O(log_2 n)$입니다. 이는 데이터의 크기 n에 대해, 최악의 경우에도 로그 시간 안에 탐색을 완료할 수 있다는 의미입니다. 선형 탐색의 $O(n)$에 비해 매우 효율적입니다.

1) 로그 시간 복잡도의 의미

로그 시간 복잡도는 데이터의 크기가 증가해도 탐색 시간이 크게 증가하지 않는다는 것을 의미합니다. 예를 들어, 데이터의 크기가 2배로 증가하더라도, 이진 탐색의 탐색 횟수는 1번만 더 증가합니다. 이러한 특성 때문에, 이진 탐색은 대용량 데이터 처리에 매우 적합합니다.

2) 공간 복잡도

이진 탐색은 추가적인 메모리를 거의 사용하지 않으므로, 공간 복잡도는 $O(1)$입니다. 즉, 입력 데이터의 크기에 관계없이 일정한 메모리 공간을 사용합니다.

5. 이진 탐색의 활용

이진 탐색은 다양한 문제 해결에 활용될 수 있습니다.

1) 값 탐색

가장 기본적인 활용 사례로, 정렬된 배열에서 특정 값을 찾는 문제입니다. 앞서 설명한 예시가 이에 해당합니다.

2) lower bound / upper bound

이진 탐색을 응용하여, 특정 값보다 크거나 같은 값 중 가장 작은 값 (lower bound) 또는 특정 값보다 작거나 같은 값 중 가장 큰 값 (upper bound)을 찾을 수 있습니다.

3) 최적화 문제

이진 탐색은 최적화 문제에도 활용될 수 있습니다. 예를 들어, 특정 조건을 만족하는 최댓값 또는 최솟값을 찾아야 하는 경우, 이진 탐색을 통해 효율적으로 해답을 찾을 수 있습니다. 이러한 접근 방식은 결정 문제(Decision Problem)를 해결하는 데 효과적입니다.

4) 실전 문제 예시

문제: 길이가 n인 정렬된 배열 nums가 주어지고, target 값이 주어졌을 때, target의 첫 번째 등장 위치의 인덱스를 반환하는 함수를 작성하세요. 만약 target이 배열에 없으면 -1을 반환합니다.

해결: 이 문제의 경우, lower bound를 찾는 이진 탐색을 응용할 수 있습니다. target보다 크거나 같은 값 중 가장 작은 값의 인덱스를 찾고, 해당 인덱스의 값이 target과 일치하는지 확인합니다.

def first_occurrence(nums, target):
    left, right = 0, len(nums) - 1
    index = -1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            index = mid  # target을 찾았지만, 첫 번째 등장 위치를 찾기 위해 계속 탐색
            right = mid - 1  # 왼쪽으로 탐색 범위를 좁힘
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return index

5) 추가 팁

• 이진 탐색 문제는 정렬되어 있다는 조건을 항상 확인해야 합니다.
• mid 계산 시 오버플로우를 방지하기 위해 mid = left + (right - left) // 2 와 같은 방법을 사용할 수도 있습니다.
• lower bound, upper bound, 최적화 문제 등, 다양한 응용 문제를 풀어보면서 이진 탐색에 대한 이해를 높이는 것이 중요합니다.