[알고리즘] 이분 탐색

이분 탐색 문제의 특징은 아래와 같다.

 

• 최적화 문제에서 "최소" 또는 "최대"를 구하는 유형.
• "가능한 최소 시간"을 찾는 문제는 이분 탐색으로 해결 가능할 때.
• 완전 탐색(브루트 포스)으로 전체를 확인하기엔 너무 연산의 크기가 클 때.

---

 

 

 

위는 이분 탐색으로 풀 수있는 문제로, 최소한의 시간을 요구하는 문제이다.

이를 이분 탐색으로 풀면 아래와 같이 나온다.

public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) 
{
        long min = 0;
        long max = (long)1e14; // 최대 가능 시간 설정
        long answer = max;

        while (min <= max) 
        {
            long mid = (min + max) / 2;
            
            long totalGold = 0; // 총 운반 가능한 금
            long totalSilver = 0; // 총 운반 가능한 은
            long totalMineral = 0; // 총 운반 가능한 금 + 은

            for (int i = 0; i < g.Length; i++) {
                long trips = mid / (t[i] * 2); // 왕복 횟수
                if (mid % (t[i] * 2) >= t[i]) trips++; // 편도로 추가 이동 가능하면 +1
                
                long maxCarry = trips * w[i]; // 해당 시간동안 운반 가능한 최대 광물
                totalGold += Math.Min(g[i], maxCarry);
                totalSilver += Math.Min(s[i], maxCarry);
                totalMineral += Math.Min(g[i] + s[i], maxCarry);
            }

            // 필요한 금과 은을 운반할 수 있는지 확인
            if (totalGold >= a && totalSilver >= b && totalMineral >= (a + b))
            {
                answer = mid; // 최소 시간 갱신
                max = mid - 1; // 시간을 줄이기
            } 
            else 
            {
                min = mid + 1; // 시간을 늘리기
            }
        }
        
        return answer;
    }

 

여기서 중점적으로 볼 부분은, 이론상 최대 수치 (10^9  *  10^5)를 구하여, 이것을 반으로 쪼개어 해당 상태로 요구하는 조건을 만족할 수 있는지 연산을 하는 부분이다.

그리고 원하는 최소수치는 min = mid + 1로 min 값이 max값을 넘는 순간이 정답이 되는 지점이다.