[알고리즘] 이진 탐색(백준 1920, 10815, 10816, 1654, 2805, 2110 -Java)

[알고리즘] 이진 탐색(백준 1920, 10815, 10816, 1654, 2805, 2110 -Java)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

이진 탐색

데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.
중앙값 비교를 통한 범위 축소 방식 입니다.
시간 복잡도는 O(logN) 입니다.

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘 입니다.

 

이진 탐색 핵심 이론

이진 탐색은 오름차순으로 정렬된 데이터에서 다음 4가지 과정을 반복합니다.

1) 현재 데이터셋의 중앙값 선택
2) 중앙값 > 타겟 데이터 일때 중앙값 기준으로 왼쪽 데이터셋을 선택
3) 중앙값 < 타겟 데이터 일때 중앙값 기준으로 오른쪽 데이터셋을 선택
4) 1~3을 반복하다가 중앙값 == 타겟 데이터일 때 탐색 종료

이진 탐색은 개념은 쉽지만, 이진 탐색 알고리즘 문제는 어려운 것 같다..😱

백준 1920

1920번: 수 찾기

자꾸 시간초과가 발생해서….
결국 스스로 풀지 못했습니다..

 

풀이

public class Quiz1920 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] A = new int[n];
        for(int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 오름차순 정렬
        Arrays.sort(A);

        /**
         * 배열 A에 값이 있는지 확인
         */
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            sb.append(search(A, Integer.parseInt(st.nextToken()), 0, n-1)).append("\n");
        }
        System.out.print(sb);

        br.close();
    }

    private static int search(int[] A, int target, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            // 타겟보다 값이 큰 경우
            if(target < A[mid]) {
                // 끝점을 중앙값 - 1로 조정
                // (중앙 값은 탐색하지 않아도 되기 때문)
                end = mid - 1;
            }
            // 타겟보다 값이 작은 경우
            else if(target > A[mid]) {
                // 시작점을 중앙값 + 1로 조정
                // (중앙 값은 탐색하지 않아도 되기 때문)
                start = mid + 1;
            } else {
                return 1;
            }
        }
        return 0;
    }
}

백준 10815

10815번: 숫자 카드
백준 1920을 풀면 쉽게 해결할 수 있는 문제 입니다.
마찬가지로 이진 탐색을 이용하여 해결할 수 있습니다.

 

풀이

public class Quiz10815 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] card = new int[n];
        for(int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        // card 오름차순 정렬
        Arrays.sort(card);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            sb.append(search(card, Integer.parseInt(st.nextToken()), 0, n-1)).append("\n");
        }
        System.out.println(sb);
    }

    private static int search(int[] card, int target, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            int midValue = card[mid];
            // 타겟보다 중앙값이 크면
            if(target < midValue) {
                end = mid - 1;
            }
            // 타겟보다 중앙값이 작으면
            else if(target > midValue) {
                start = mid + 1;
            } else {
                return 1;
            }
        }
        return 0;
    }
}

백준 10816

10816번: 숫자 카드 2
이진 탐색으로 해결하지 못했고, HashMap을 사용해서 해결했습니다.
하지만 이진 탐색 문제인 만큼 이진 탐색으로 문제를 풀어보겠습니다.

백준 10816번 : 숫자 카드 2 - JAVA 자바
이진 탐색으로 문제를 해결하기 위해서는
중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 알아내는 것이 핵심입니다.
중복 원소의 왼쪽 끝 값과 오른쪽 끝 값을 얻어 구간의 길이를 얻는 접근 방식 입니다.
구간의 길이가 곧 중복 갯수 입니다.!

이런 접근방식을 이해하기 위해서는 lower_bound, upper_bound 개념을 알아야 합니다.
(Java 에서는 Arrays.binarySearch()를 통해 lower_bound 형식의 이진탐색을 제공하고 있습니다.)

lower_bound
타겟의 이상의 값이 처음으로 나타나는 위치를 의미 합니다.

 

lower_bound 동작

 

 

upper_bound
타겟의 초과한 값이 처음으로 나타나는 위치를 의미합니다.
타켓의 값보다 큰 값의 처음 위치를 반환하는 것이 바로 upper_bound 입니다.

 

upper_bound 동작

 

중복원소의 길이 = upper_bound - lower_bound임을 알 수 있다.

 

풀이

public class Quiz10816_2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 카드 갯수
        int n = Integer.parseInt(br.readLine());
        // 카드 저장
        int[] card = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

        // 카드 정렬
        Arrays.sort(card);

        // 카드 비교 군
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            int upperBoundValue = getUpperBound(card, target);
            int lowerBoundValue = getLowerBound(card, target);
            sb.append(upperBoundValue - lowerBoundValue).append(" ");
        }
        System.out.print(sb);
        br.close();
    }

    // 타겟의 카드가 위치한 첫번째 위치 반환
    private static int getLowerBound(int[] card, int target) {
        int start = 0;
        int end = card.length;

        // 위치가 같으면 탈출
        while (start < end) {
            // 중간 위치(탐색 위치)
            int mid = start + (end - start) / 2;

            // 타켓이 중간 위치의 값보다 작거나 같으면
            if(target <= card[mid]) {
                // 왼쪽 탐색을 해야함
                end = mid;
            }
            // 타켓이 중간 위치의 값보다 크면
            else {
                // 오른쪽 탐색을 해야함
                start = mid + 1;
            }
        }
        return start;
    }

    // 타겟의 카드가 위치한 마지막 위치 + 1 반환
    private static int getUpperBound(int[] card, int target) {
        int start = 0;
        int end = card.length;
        // 위치가 같으면 탈출
        while (start < end) {
            int mid = start + (end - start) / 2;
            // 타겟이 중간 위치의 값보다 작으면
            if(target < card[mid]) {
                // 왼쪽으로 탐색 해야함
                end = mid;
            }
            // 타겟이 중간 위치의 값보다 크거나 같으면
            else {
                // 오른쪽 탐색 해야함
                start = mid + 1;
            }
        }
        return start;
    }
}

백준 1654

1654번: 랜선 자르기
기존에는 특정 배열의 인덱스를 찾기 위해 이진탐색을 했습니다.
하지만, 이번 문제에서는 우리는 길이를 찾아야 합니다.
이진 탐색의 범위가 인덱스가 아니라 값 입니다.
또한, 랜선의 중간 값((max + min) / 2)을 구해서 몇 개의 랜선(target)을 만들 수 있는지 확인 하면 됩니다.

 

정리하면
일반적으로 배열에서는 특정 값에 대한 특정 인덱스를 찾고자 했다면,
이 번 문제에서는 특정 개수에 대한 특정 길이를 찾고자 한다는 것 입니다.^^

 

풀이

public class Quiz1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 소유한 랜선 갯수
        int lanNum = Integer.parseInt(st.nextToken());
        // 만들고 싶은 랜선 갯수
        int target = Integer.parseInt(st.nextToken());

        // 소유한 랜선 길이 저장(랜선 길이는 최대 2^31 - 1)
        int[] lanCable = new int[lanNum];
        long max = Long.MIN_VALUE;
        for(int i = 0; i < lanNum; i++) {
            lanCable[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, lanCable[i]);
        }

        // 랜선의 최대 길이를 출력
        // 랜선의 길이를 줄이면서 목표하는 랜선 갯수를 만족하는 최대 랜선 길이를 찾아야 한다.
        // upperBound를 사용하면 된다.
        long upperBound = getUpperBound(lanCable, target, max + 1);
        System.out.print(upperBound - 1);
        br.close();
    }
    private static long getUpperBound(int[] lanCable, int target, long max) {
        long min = 0;
        while (min < max) {
            // 탐색 랜선 길이
            long mid = min + (max - min) / 2;
            // 탐색 랜선 길이로 나눈 랜선의 총 갯수
            long lanCount = 0;
            for(int i = 0; i < lanCable.length; i++) {
                lanCount += (lanCable[i] / mid);
            }
            /**
             * lanCount가 target을 초과한 첫 갯수
             * 따라서 target > lanCount
             */
            // 원하는 랜선 갯수가 탐색길이로 자른 랜선 갯수가 더 많으면
            if(target > lanCount) {
                // 탐색 랜선 길이를 너무 길게 선정함
                // 탐색 랜선 길이를 줄여보자.
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

백준 2805

2805번: 나무 자르기
나무 길이를 조절하면서 원하는 나무 길이와 자른 나무의 합과 비교하며 탐색해야합니다.
문제에서 요구한 나무 길이를 탐색하면 자른 위치를 반환 합니다.
절단기에 설정할 수 있는 높이의 최댓값을 구하기 때문에 upperBound를 사용합니다.

 

이때 탐색 범위는 max + 1 까지이고 upperBound이기 때문에 결과에서 -1을 해야 합니다.

 

풀이

public class Quiz2805 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 나무 갯수
        int treeNum = Integer.parseInt(st.nextToken());
        // 총 나무 길이(target)
        int target = Integer.parseInt(st.nextToken());

        // 나무
        st = new StringTokenizer(br.readLine());
        int[] tree = new int[treeNum];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < treeNum; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, tree[i]);
        }

        // 절단기의 최대 높이(mid의 최대 높이 -> upperBound - 1)
        // max + 1 까지 탐색 해야함
        long result = getUpperBound(tree, target, max + 1);
        System.out.print(result - 1);
        br.close();
    }

    static private long getUpperBound(int[] tree, int target, long max) {
        long min = 0;
        while (min < max) {
            // overFlow 방지
            long mid = min + (max - min) / 2;
            /**
             * 나무 길이를 조절하면서 자른 나무 길이의 합을 탐색해야한다.
             */
            // 탐색한 나무의 길이 총합
            long sumLen = 0;
            for(int i = 0; i < tree.length; i++) {
                // 나무길이(tree[i]) 에서 우리가 정한 길이(mid)로 자른 합(len)을 구함
                // 문제 조건으로 나무를 안 잘라도 되기 때문에 양수인 것만 자른다.
                if(tree[i] - mid > 0) {
                    sumLen += (tree[i] - mid);
                }
            }

            // 원하는 나무 길이(target)가 방금 탐색한 나무 길이(sumLen) 총합 보다 크면
            if(target > sumLen) {
                // 나무를 잘랐을 때 이전 보다 더 커야함.
                // 자르는 길이(mid)를 줄이면 더 크게 자를 수 있다.
                // max를 줄이면 자르는 길이(mid)가 줄어 든다.
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

백준 2512

2512번: 예산
문제를 보면
예산 중 최댓값을 구하면 됩니다.(이때, 상한액 이하의 예산요청을 그대로 배정 해야 합니다.)
최댓값을 구하라고 했으니!
upperBound를 이용하면 됩니다.

 

우리가 임의로 선정한 예산(mid) 보다 지방 예산(budget)이 작으면 예산요청을 그대로 배정해야합니다….!!
아닌 경우에는 우리가 임의로 선정한 예산(mid)를 배정해야 겠죠?

// 최대로 줄 수 있는 예산
long mid = min + (max - min) / 2;
// 최대로 줄 수 있는 예산 총합
long sum = 0;
for(int i = 0; i < budget.length; i++) {
    //  지방 요청 예산(budget) < 최대로 줄 수 있는 예산(mid)
    if(budget[i] < mid) {
        // 상한액 이하의 예산 요청을 그대로 배정
        sum += budget[i];
    } else {
        sum += mid;
    }
}

 

풀이

public class Quiz2512 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 지방 수
        int n = Integer.parseInt(br.readLine());
        // 지방 요청 예산
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] budget = new int[n];
        long max = Long.MIN_VALUE;
        for(int i = 0; i < budget.length; i++) {
            budget[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, budget[i]);
        }
        // 총 예산(목표)
        int target = Integer.parseInt(br.readLine());

        // 예산 중 최댓값을 구하면 된다.(이때, 상한액 이하의 예산요청을 그대로 배정)
        // 최댓값을 구하는 문제이기 때문에, upperBound를 사용한다.
        long upperBound = getUpperBound(budget, max+1, target);
        System.out.print(upperBound - 1);
    }

    private static long getUpperBound(int[] budget, long max, int target) {
        long min = 0;
        while (min < max) {
            // 최대로 줄 수 있는 예산
            long mid = min + (max - min) / 2;
            // 최대로 줄 수 있는 예산 총합
            long sum = 0;
            for(int i = 0; i < budget.length; i++) {
                // 최대로 줄 수 있는 예산 > 지방 요청 예산
                if(budget[i] < mid) {
                    // 상한액 이하의 예산 요청을 그대로 배정
                    sum += budget[i];
                } else {
                    sum += mid;
                }
            }
            // 최대로 줄 수 있는 예산(sum)이 총 예산 보다 크면
            if(target < sum) {
                // 최대로 줄 수 있는 예산을 줄여야 한다.
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

백준 2110

2110번: 공유기 설치

공유기를 설치한 집(house[k])과 인접한 집(house[i])과 거리를 비교해서 설치 횟수(count)를 세고 이를 문제의 라우터 갯수(target)와 비교하여 임의로 정한 집 사이의 거리(mid)를 탐색하는 문제 입니다.

private static long installRouter(int[] house, long mid) {
    int distance = 0;
    int count = 1; // house[0]는 설치
    int k = 0;
    for(int i = 1; i < house.length; i++) {
        distance = house[i] - house[k];
        // 라우터를 설치한 집으로부터 떨어진 다른 집의 거리(distance)가
        // 우리가 임의로 정한 거리보다 크거나 같을 경우
        if(distance >= mid) {
            // 라우터 설치 가능하다는 의미!!
            count++;
            // 집(i)는 라우터 설치가 완료되었다.
            // 따라서 집(i)와 인접한 집 사이의 거리를 구해야 하기때문에
            // 집의 위치(k)를 (i)로 바꿔 준다.
            k = i;
        }
    }
    return count;
}

 

풀이

public class Quiz2110 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 집 갯수
        int houseNum = Integer.parseInt(st.nextToken());
        // 라우터 갯수
        int target = Integer.parseInt(st.nextToken());

        int[] house = new int[houseNum];
        long max = Long.MIN_VALUE;
        for(int i = 0; i < houseNum; i++) {
            house[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, house[i]);
        }

        // 오름차순 정렬
        Arrays.sort(house);

        // 한 집에서는 1개의 공유기만 설치 가능
        // 가장 인접한 두 공유기 사이의 최대 거리
        long upperBound = getUpperBound(house, target, max + 1);
        System.out.print(upperBound - 1);

        br.close();
    }

    private static long getUpperBound(int[] house, long target, long max) {
        long min = 0;
        while (min < max) {
            // 임의로 정한 집 사이의 거리
            long mid = min + (max - min) / 2;
            long count = installRouter(house, mid);

            // 목표 라우터 갯수가 임의로 설치한 라우터 갯수보다 많으면
            if(target > count) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }

    private static long installRouter(int[] house, long mid) {
        int distance = 0;
        int count = 1; // house[0]는 설치
        int k = 0;
        for(int i = 1; i < house.length; i++) {
            distance = house[i] - house[k];
            // 라우터를 설치한 집으로부터 떨어진 다른 집의 거리(distance)가
            // 우리가 임의로 정한 거리보다 크거나 같을 경우
            if(distance >= mid) {
                // 라우터 설치 가능하다는 의미!!
                count++;
                // 집(i)는 라우터 설치가 완료되었다.
                // 따라서 집(i)와 인접한 집 사이의 거리를 구해야 하기때문에
                // 집의 위치(k)를 (i)로 바꿔 준다.
                k = i;
            }
        }
        return count;
    }
}