[알고리즘] 정렬된 범위 내 특정 값 빠르게 찾기 - 이분 탐색 알고리즘 (백준 1654 - Java)

정렬된 범위 내에서 어떠한 값을 찾아야 할 때

이분 탐색 알고리즘을 이용하면 좀 더 빠른 속도로 찾을 수 있다.

 

출처 : 위키백과

위와 같이 오름차순으로 정렬된 숫자 배열에서

7을 찾아야 할 경우 배열 전체를 탐색하는 방법이 아닌

 

1. 시작점과 끝점을 범위 내 양 끝으로 정의
2. 시작점과 끝점을 더한 값을 2로 나눈 위치(중앙) 값과 찾는 값 비교
3. 중앙값이 찾는 값보다 크다면 끝점을 중앙값의 이전값으로 초기화, 작다면 시작점을 중앙값의 다음값으로 초기화
4. 2 ~ 3 반복, 시작점이 끝점 이상이 될 경우 종료

 

의 방법으로 해결할 수 있다.

 

위 그림에서 위와 같은 이분탐색을 활용할 경우

14, 6, 8, 7

총 4번의 탐색만으로 7을 찾을 수 있다.

 

이런 유형의 문제에서 범위의 기준을 어떻게 잡을지를 판별하는 것이 중요한데

 대부분의 경우 답에서 요구하는 값을 기준으로 잡으면 된다.

 

예제 코드 (백준 1654)

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

1654번: 랜선 자르기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

// [백준] 1654. 랜선 자르기 (Java)
public class Main {
	
	static int n; // 필요한 랜선 수
	static int k; // 이미 가지고 있는 랜선 수
	static int max; // 가장 긴 랜선의 길이
	static ArrayList<Integer> cable; // 랜선 길이
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		k = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		cable = new ArrayList<>();
		
		for(int i = 0; i < k; i++) {
			cable.add(Integer.parseInt(br.readLine()));
		}
		
		max = Collections.max(cable);
		
		// 최소 1 이상의 길이로 자르므로 시작은 1
		long left = 1;
		// 제일 긴 케이블보다 크게 자를 수 없음
		long right = max;
		
		while(left <= right) {
			long mid = (left + right) / 2;
			long sum = 0;
			
                    for (int i: cable) { 
                        sum += (i / mid); // 자른 개수 합
                    }
                    // 크거나 같으면 자르는 길이를 늘려봄 
                    if (sum >= n) {
                        left = mid + 1;
                    }
                    // 모자라면 자르는 길이를 줄여봄
                    else {
                        right = mid - 1;
                    }
		}
		
		System.out.println(right);
	}
}

위의 문제에서는 랜선의 최대 길이를 요구하고 있으므로

랜선의 길이를 기준으로 하여 이분탐색을 진행하면 된다.

 

 

 

참고

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98