[99클럽/코딩테스트 챌린지/C++] 코딩 테스트 문제에서 이분 탐색을 활용하는 방법

오늘은 문제 해결 과정에서 이분 탐색(Binary Search)을 어떻게 식별하고 적용할지에 대해 정리해보았습니다.

문제 설명

형택이는 과거 스파이더 카드놀이에서 이긴 횟수와 게임 횟수가 주어졌을 때, 승률을 1% 올리기 위해 최소 몇 번의 추가 승리가 필요한지를 구해야 합니다.

문제 링크 : 

https://www.acmicpc.net/problem/1072

문제 접근 방법

처음에는 재귀 함수로 각 경우를 일일이 검사하면서 승률을 올리는 방식을 생각했습니다. 하지만 문제의 입력 범위가 매우 컸기 때문에, 재귀를 통해 모든 경우를 하나씩 검사하는 것은 불필요하게 많은 함수 호출을 야기해 비효율적이었습니다. 특히, 승률이 한 번 변하는 최소 조건을 찾는 문제에서는 이런 순차적인 접근이 적합하지 않았습니다. 큰 입력에 대해 시간 초과가 발생할 수 있었기 때문에, 더 효율적인 방법이 필요했습니다.

 

문제를 다시 분석하며, 승률이 일정하게 증가하는 단조 증가 특성에 주목했습니다. 이 특성 덕분에 특정 조건을 만족하는 최소 게임 횟수를 이분 탐색으로 빠르게 찾을 수 있을 것이라 판단했습니다. 이분 탐색을 사용하면 전체 범위를 반씩 줄여가면서 조건을 확인할 수 있어 큰 입력 값도 효율적으로 처리할 수 있습니다. 문제의 요구 사항과 입력 크기를 고려할 때, 이분 탐색이 더 적합한 접근이라는 것을 깨달았습니다.

1. 승률이 단조 증가: 이긴 게임 수가 증가할수록 승률도 단조적으로 증가하므로 특정 범위에서 최솟값을 찾을 수 있습니다.
2. 최소값 탐색: 특정 조건을 만족하는 최소 게임 횟수를 구해야 하므로 이분 탐색으로 범위를 줄여나가며 값을 찾는 것이 효율적입니다.
3. 큰 검색 공간: X가 최대 10억까지 주어질 수 있어 모든 경우를 순차적으로 검사하는 것은 비효율적입니다. 이분 탐색으로 검색 공간을 반씩 줄여나가는 방식이 적합합니다.

C++ 코드 풀이

아래는 이 문제를 해결하기 위한 C++ 코드입니다:

#include <iostream>
using namespace std;

long long minimumGames(long long X, long long Y) {
    int initialWinRate = (Y * 100) / X;  // 현재 승률 Z
    if (initialWinRate >= 99) {
        return -1;  // 승률이 절대 변하지 않는 경우
    }
    
    long long left = 1, right = 1000000000;
    long long result = -1;

    while (left <= right) {
        long long mid = (left + right) / 2;
        long long newWinRate = ((Y + mid) * 100) / (X + mid);

        if (newWinRate > initialWinRate) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return result;
}

int main() {
    long long X, Y;
    cin >> X >> Y;

    cout << minimumGames(X, Y) << endl;

    return 0;
}

코드 설명

1. 현재 승률 계산: initialWinRate 변수에 형택이의 현재 승률을 계산하여 저장합니다.
2. 이분 탐색 설정: 이분 탐색 범위를 left = 1, right = 1,000,000,000으로 설정하고, mid 값을 반복적으로 확인합니다.
3. 새로운 승률 확인: mid 만큼 추가 게임을 했을 때 승률을 계산하여 newWinRate에 저장합니다.
4. 조건 검사 및 업데이트:
   • 새로운 승률이 초기 승률보다 높다면, mid 값이 조건을 만족하는 최솟값이 될 가능성이 있으므로 result에 저장하고, right를 mid - 1로 줄여 탐색 범위를 줄입니다.
   • 조건을 만족하지 못하면 left를 mid + 1로 증가시켜 더 많은 게임을 이겨야 하는 경우를 탐색합니다.
5. 결과 출력: 탐색이 끝나면 result 값을 반환하고, 승률이 절대 변하지 않는 경우는 -1을 반환합니다.

---

정리: 문제에서 이분 탐색을 식별하는 방법

문제에서 이분 탐색을 고려할 수 있는 신호를 요약하면 다음과 같습니다:

1. 특정 조건을 만족하는 최소 또는 최대 값을 구하려는 경우
2. 문제에서 값이 단조적으로 변화하는지 확인
3. 검색 공간이 큰 경우
4. 특정 조건이 변하는 지점을 찾는 경우

이 과정을 통해 문제에 적합한 알고리즘을 선택하는 것의 중요성을 다시 느꼈고, 문제에서 단조성이나 특정 조건을 만족하는 최소값을 구하는 경우에는 이분 탐색을 우선 고려하는 습관을 가져야겠다고 생각했습니다.