이진 검색(이분 탐색) 완벽 가이드: 개념부터 문제 풀이까지 with. 프로그래머스 징검다리

 

이진 검색(이분탐색)이란?

 

1 ~ 100까지의 수 중 생각하고 있는 수를 맞춰봅시다

바로 생각나는 방법은 1부터 100까지 맞는지 물어보는 것입니다

이렇게하면 최악의 경우 100번을 물어봐야 합니다 더 적게 물어볼 방법은 없을까요?

반씩 잘라서 그 수보다 작은지 큰지 물어보는 것입니다
50 - 25 - 13 - 7 - 4 - 2 - 1 최악의 경우라도 7번만의 답을 찾을 수 있습니다

정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘으로 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방법

 

그러면 알고리즘 테스트에서 이진 검색은 언제 사용할까요?

10^9의 배열이 주어졌을 때 10억번의 연산이 필요하므로 약 10초가 필요하지만 대부분의 알고리즘은 1~2초 내에서 문제를 해결하기에 시간 초과가 발생합니다

이진 검색은 O(logN)의 시간 복잡도를 가지므로 약 30번의 연산으로 찾을 수 있기에 훨씬 효율적으로 찾을 수 있습니다

 

단, 정렬된 경우에만 사용할 수 있다는 것에 주의합시다. 일반적으로 정렬은 O(NlogN)의  시간복잡도를 가지므로 정렬되지 않은 10^9의 배열은 정렬 후 이진 검색을 수행하면 약 10^9 * 30 즉, 300억의 연산이 필요합니다

 

이진 검색 구현

 

    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
       	// 1. 중간 인덱스 계산
            int mid = left + (right - left) / 2;

	// 2. key와 현재 인덱스 값 비교
            // 2-1. key가 중간 값과 같은 경우 : 정답, 해당값 반환
            if (arr[mid] == key) {
                return mid;
            }

            // 2-2. key가 중간 값보다 작으면 왼쪽 부분을 탐색
            if (arr[mid] > key) {
                right = mid - 1;
            } 
            // 2-3. key가 중간 값보다 크면 오른쪽 부분을 탐색
            else {
                left = mid + 1;
            }
        }

     // 3. key를 찾지 못한 경우 음수 반환
        return -1;
    }

 

이진 검색은 대표적인 분할 정복 알고리즘 유형으로 다음과 같은 과정으로 구현합니다

1. 중간값 계산
   • 중간 인덱스를 구할 때 Overflow가 발생할 수 있으므로 (left + right) / 2로 구하지 않도록 주의합시다 
2. 양 끝 인덱스 조정
   • key와 중간값이 같다면 해당 인덱스를 반환합니다
   • key가 중간값보다 작으면 오른쪽 범위를 중간값 이전으로 축소합니다
   • key가 중간값보다 크면 왼쪽 범위를 중간값 이후로 축소합니다

이진 검색은 제공되는 binarySearch메서드를 활용하면 구현하지 않고도 편리하게 사용할 수 있습니다

 

    public static void main(String[] args) {
        // 정렬된 배열
        int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15};
        
        // 찾고자 하는 값
        int key = 5;
        
        int result = binarySearch(numbers, key);
        
        // 결과 출력(값 5는 인덱스 2에 있습니다.)
        System.out.println("값 " + key + "는 인덱스 " + result + "에 있습니다.");
        }
    }

 

단, 분할 정복 중간에 추가적인 작업이 필요한 경우는 실제로 구현을 해야 합니다

예제를 통해 확인해봅시다

 

이진검색 예제

 

- 프로그래머스 징검다리 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

mport java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
    	// 이진 검색을 사용하기 위해 정렬 필요
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        int answer = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2; // 돌 사이의 목표 거리
            int removedRocks = 0; // 제거한 돌의 수
            int prevRock = 0; // 이전 돌 위치(초기값은 시작 위치)
            
            // 돌을 하나씩 확인
            for (int rock : rocks) {
            	// 이전 돌과의 거리가 목표 거리보다 작은 경우 돌 제거
                if (rock - prevRock < mid) {
                    removedRocks++;
                // 이전 돌과의 거리가 목표 거리보다 큰 경우 돌 유지, 이전 돌 갱신
                } else {
                    prevRock = rock;
                }
            }
            
            // 도착 지점에서 이전 돌까지의 거리가 목표 거리보다 작은 경우 돌 제거
            if (distance - prevRock < mid) {
                removedRocks++;
            }
            
            // 제거한 돌이 n보다 작은 경우, 조건 만족 -> 답 갱신 -> 목표 거리 증가
            if (removedRocks <= n) {
                answer = Math.max(answer, mid);
                left = mid + 1;
            // 제거한 돌이 n보다 큰 경우, 조건 불만족 -> 목표 거리 감소
            } else {
                right = mid - 1;
            }
        }
        
        return answer;
    }
}

 

문제 풀이

1. 이진 검색을 활용하기 위해 정렬
   • 10^9이어서 시간 초과 할 것 같지만 정렬은 돌 50000개만 하므로 50,000 * log(50,000) = 약 780,000번의 연산으로 가능
   • 10^9에서 목표로 하는 최소 거리는 최대 30번의 연산으로 구할 수 있음
2. 시작위치부터 각 돌까지의 거리 비교하며 돌 제거
   
   • 목표 거리보다 작으면 제거
   • 목표 거리보다 크면 유지
3. 마지막 돌에서 도착위치까지의 거리 비교하고 돌 제거
   
   • 목표 거리보다 작으면 제거
   • 목표 거리보다 크면 유지
4. 제거한 돌이 n보다 작은 경우 더 큰 최소거리 찾기 위해 왼쪽 경계를 올림
   • 현재 목표 거리는 가능, 더 큰 목표 거리도 가능한지 확인
5. 제거한 돌이 n보다 큰 경우 더 작은 최소거리 찾기 위해 오른쪽 경계를 내림
   • 현재 목표 거리보다 큰 경우 불가능, 더 작은 목표 거리로 확인

 

ex ) 

distance	rocks	n	return
25	[ 2, 14, 11, 21, 17]	2	4

 

• 정렬한 바위 : [2, 11, 14, 17, 21]

 

• 첫 번째 중간값 mid = 13:
  • 바위 간 최소 거리 13을 유지하려면 2, 11, 17, 21 제거 (removedRocks > 2)
  • 최소 거리를 줄이기 위해 right = mid - 1로 줄임 (left = 1, right = 12)
• 두 번째 중간값 mid = 6:
  • 바위 간 최소 거리 6을 유지하려면 2, 14, 21 제거 (removedRocks > 2)
  • 최소 거리를 줄이기 위해 right = mid - 1로 줄임 (left = 1, right = 5)
• 세 번째 중간값 mid = 3:
  • 바위 간 최소 거리 3 유지 가능 2 제거 (removedRocks <= 2)
  • 답을 3으로 갱신하고 최소 거리를 늘리기 위해 left = mid + 1 (left = 4, right = 5)
• 네 번째 중간값 mid = 4:
  • 바위 간 최소 거리 4 유지 가능 2, 14 제거 (removedRocks <= 2)
  • 답을 4로 갱신하고 최소 거리를 늘리기 위해 left = mid + 1 (left = 5, right = 5)
•  다섯 번째 중간값 mid = 5:
  • 바위 간 최소 거리 5를 유지하려면 2, 14, 21 제거 (removedRocks > 2)
  • 최소 거리를 줄이기 위해 right = mid - 1로 줄임 (left = 5, right = 4)
  • right > left 이므로 반복 중단, 정답은 4