Code/Codility

14. 이진 탐색 (Binary Search) Codility Lesson 한국어 정리본 (JavaScript ver.)

haeunkim.on 2025. 3. 2. 16:24

1. 이진 탐색(Binary Search)이란?

이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘 으로, O(log n) 시간 복잡도를 가진다. 이 알고리즘은 반복적으로 검색 범위를 절반으로 줄이면서 원하는 값을 찾는다.

예를 들어, 1부터 16까지의 숫자 중에서 목표 숫자를 찾는다고 가정해 보자. 단순 선형 탐색(linear search)으로는 최악의 경우 16번의 비교가 필요하지만, 이진 탐색을 사용하면 최대 4번의 비교만으로 찾을 수 있다.

2. O(log n) 시간 복잡도의 이진 탐색 구현

JavaScript 코드:

function binarySearch(A, x) {
    let left = 0, right = A.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (A[mid] === x) return mid;
        else if (A[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

시간 복잡도: O(log n) (검색 범위를 절반씩 줄이므로)

이 알고리즘은 다음과 같은 과정으로 동작한다:

  1. 배열의 중앙값을 선택한다.
  2. 찾는 값 x가 중앙값보다 크면 오른쪽 절반을 탐색하고, 작으면 왼쪽 절반을 탐색한다.
  3. 이 과정을 반복하여 값을 찾는다.

3. 이진 탐색을 활용한 최적 값 찾기 (Binary Search on the Result)

이진 탐색은 단순한 숫자 검색뿐만 아니라 최적의 값을 찾는 문제 에도 활용될 수 있다. 예를 들어, 길이가 n인 지붕에 0과 1로 표시된 구멍이 있고, k 개의 동일한 크기의 판자를 사용하여 모든 구멍을 덮어야 하는 문제를 생각해 보자. 이때, 판자의 최소 크기를 찾는 것이 목표이다.

JavaScript 코드:

function boards(A, k) {
    let n = A.length;
    let left = 1, right = n, result = -1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (check(A, mid) <= k) {
            right = mid - 1;
            result = mid;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

이 코드는 check(A, mid) 함수를 사용하여 주어진 크기의 판자로 모든 구멍을 덮을 수 있는지 검사한다. 범위를 좁혀가며 최적의 크기를 찾는 방식이다.

4. 판자가 충분한지 확인하는 함수 (Greedy Check)

이제, 특정 크기의 판자로 모든 구멍을 덮을 수 있는지 확인하는 함수를 구현해 보자.

JavaScript 코드:

function check(A, k) {
    let n = A.length;
    let boards = 0, last = -1;
    
    for (let i = 0; i < n; i++) {
        if (A[i] === 1 && last < i) {
            boards++;
            last = i + k - 1;
        }
    }
    return boards;
}

시간 복잡도: O(n) (배열을 한 번 순회하며 필요한 판자 개수를 계산)

이 함수는 배열을 왼쪽에서 오른쪽으로 탐색하면서, 아직 덮이지 않은 구멍이 나오면 새로운 판자를 추가하는 방식으로 동작한다.

5. 이진 탐색을 활용한 최적화 문제 해결 패턴

이진 탐색은 단순한 값 검색 외에도 다음과 같은 문제를 해결하는 데 유용하다:

  • 최적의 크기 찾기 (예: 위의 지붕 구멍 문제)
  • 최소/최대 비용 계산 (예: 특정 조건을 만족하는 최소 비용 찾기)
  • 시간 최적화 (예: 가장 짧은 시간 내에 작업을 완료하는 방법 찾기)

이러한 문제들은 보통 조건을 만족하는 최소/최대 값을 찾는 형태 로 변형하여 이진 탐색을 적용할 수 있다.

반응형