C++ 코딩테스트 강좌, 이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 방법입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누어 목표 값을 찾기 때문에 O(log n)의 시간 복잡도를 가집니다. 본 강의에서는 이진 탐색의 기본 개념, 구현 방법, 그리고 이를 활용한 실습 문제를 다루고자 합니다.

이진 탐색의 기본 원리

이진 탐색은 다음과 같은 절차로 동작합니다:

  1. 배열의 중앙 요소를 확인합니다.
  2. 중앙 요소와 목표 값을 비교합니다:
    • 목표 값이 중앙 요소보다 작으면 배열의 왼쪽 절반을 대상으로 검색합니다.
    • 목표 값이 중앙 요소보다 크면 배열의 오른쪽 절반을 대상으로 검색합니다.
    • 목표 값이 중앙 요소와 같으면 검색이 완료됩니다.

이 과정을 반복하여 목표 값을 찾습니다.

문제: 정렬된 배열에서 특정 값 찾기

주어진 정수 배열 arr와 정수 target이 있을 때, target의 인덱스를 반환하는 프로그램을 작성하시오. 만약 target이 없는 경우 -1을 반환해야 합니다.

입력 형식

  • 첫 번째 줄에는 배열의 크기 n이 주어집니다. (1 ≤ n ≤ 105)
  • 두 번째 줄에는 오름차순으로 정렬된 배열 arr가 주어집니다.
  • 세 번째 줄에는 찾고자 하는 숫자 target가 주어집니다.

출력 형식

타겟의 인덱스를 출력합니다. (0 이상 n-1 이하의 정수)

예제

입력:
    5
    1 3 5 7 9
    5

    출력:
    2

문제 풀이 과정

1단계: 문제 이해

먼저 문제를 정확히 이해하는 것이 중요합니다. 정렬된 배열에서 특정 요소를 빠르게 찾는 것이니, 이진 탐색을 이용해야 합니다.

2단계: 이진 탐색 알고리즘 구현

이진 탐색 알고리즘을 C++로 구현해보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;  // 타겟을 찾았다.
        } else if (arr[mid] < target) {
            left = mid + 1;  // 오른쪽 반으로 이동.
        } else {
            right = mid - 1;  // 왼쪽 반으로 이동.
        }
    }
    return -1;  // 타겟을 찾지 못했다.
}

int main() {
    int n;
    cout << "배열의 크기를 입력하세요: ";
    cin >> n;
    
    vector<int> arr(n);
    cout << "배열의 요소를 입력하세요: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int target;
    cout << "찾고자 하는 숫자를 입력하세요: ";
    cin >> target;

    int result = binarySearch(arr, target);
    if (result != -1) {
        cout << "타겟의 인덱스: " << result << endl;
    } else {
        cout << "타겟을 찾지 못했습니다." << endl;
    }

    return 0;
}

3단계: 코드 설명

– binarySearch 함수는 정수 벡터와 목표 값을 입력으로 받고, 목표 값의 인덱스를 반환합니다.
– left와 right는 탐색 구간의 시작과 끝 인덱스를 나타냅니다.
– while 루프는 left가 right보다 작거나 같은 동안 실행됩니다.
– 각 반복에서 중앙 인덱스 mid를 계산하고, 중앙 요소와 목표 값을 비교하여 다음 탐색 구간을 결정합니다.

4단계: 테스트 및 검증

코드를 작성한 후, 다양한 테스트 케이스에 대해 실행하여 올바른 결과를 반환하는지 확인해야 합니다. 다음과 같은 테스트를 고려할 수 있습니다:

  • 배열에 목표 값이 존재하는 경우
  • 배열에 목표 값이 없는 경우
  • 배열의 크기가 1인 경우
  • 중복된 요소가 있는 경우

결론

이진 탐색은 매우 유용한 알고리즘입니다. 특히, 정렬된 배열에서 속도 면에서 뛰어난 성능을 발휘합니다. 본 강의에서는 이진 탐색의 기본 원리를 이해하고, 실제 코드를 작성해보았습니다. 이진 탐색을 마스터하면, 다른 많은 알고리즘 문제를 해결하는 데도 큰 도움이 될 것입니다.

다음 강의에서는 이진 탐색의 변형 문제 및 다양한 응용 사례에 대해 다룰 예정입니다. 지속적인 학습을 통해 알고리즘 능력을 향상시키시길 바랍니다!

© 2023 알고리즘 강좌 | C++ 이진 탐색