[알고리즘] 이진 탐색 (Binary Search)

package CLUB_99.Day250114;

import java.util.Scanner;

public class BOJ1654 {
    // 랜선 자르기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력
        int K = sc.nextInt(); // 가지고 있는 랜선의 개수
        int N = sc.nextInt(); // 필요한 랜선의 개수
        long[] cables = new long[K];

        long max = 0; // 랜선의 최대 길이
        for (int i = 0; i < K; i++) {
            cables[i] = sc.nextLong();
            max = Math.max(max, cables[i]); // 가장 긴 랜선의 길이를 저장
        }

        long left = 1; // 랜선의 최소 길이
        long right = max; // 랜선의 최대 길이
        long result = 0;

        // 이분 탐색
        while (left <= right) {
            long mid = (left + right) / 2; // 중간 길이
            long count = 0;

            // mid 길이로 자른 랜선의 개수 계산
            for (long cable : cables) {
                count += cable / mid;
            }

            // 랜선을 충분히 만들 수 있으면 길이를 늘려본다
            if (count >= N) {
                result = mid; // 가능한 길이 저장
                left = mid + 1;
            } else {
                right = mid - 1; // 길이를 줄여본다
            }
        }

        // 결과 출력
        System.out.println(result);
        sc.close();
    }
}

💡 추가 학습 개념

⚽ 이진탐색 ( Binary Search )

 

이진 탐색이란?
정렬된 데이터에서 값을 효율적으로 찾기 위해 검색 범위를 반씩 줄여가며 탐색하는 알고리즘

 

 

이진 탐색을 사용하는 이유

1. 빠른 탐색: 시간 복잡도가 O(log⁡N)O(\log N)O(logN)으로, 대규모 데이터에서 매우 효율적
2. 정렬된 데이터 필수: 정렬 상태가 유지된 데이터에서만 작동

 

이진 탐색 작동 과정

1. 중간값 계산: 데이터의 중간 인덱스를 구한다.
2. 값 비교:
   • 찾는 값이 중간값보다 크면 오른쪽 탐색.
   • 찾는 값이 중간값보다 작으면 왼쪽 탐색.
   • 같으면 값을 반환.
3. 범위 좁히기: 위 과정을 반복하며 탐색 범위를 줄여 나감.

 

이진 탐색 주요 활용

• 값의 존재 여부 확인.
• 최적화 문제(예: 특정 조건을 만족하는 최대/최소값 찾기).