이분탐색

정렬되어 있는 배열에서 특정 데이터를 찾기위해 모든 데이터를 순차적으로 확인하신 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

1920 수 찾기

• 기본적인 이분탐색
  https://www.acmicpc.net/problem/1920

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

• 출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이

1) 배열-오름차순 정렬.
2) 이분탐색 로직 구현

• start, end 두 변수 필요
• mid = (st+ed)/2 -> 중간 지점 값을 통해 st, ed 값을 적절하게 바꾼다.

정답코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] a;
    static int[] b;
    static int n, m;

    static int biSearch(int target) {
        int st = 0;
        int en = n - 1;

        while (st <= en) { // 이분 탐색 종료 조건: 해당 값이 배열에 없을 경우 -> st, en이 역전됨.
            int mid = (st + en) / 2;

            if (a[mid] < target) st = mid + 1;
            else if (a[mid] > target) en = mid - 1;
            else return 1; // 찾은 경우 1 반환 후 종료
        }
        // st > en 일 경우 배열에 없음!
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 배열 요소 개수

        // 배열 a
        a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        m = Integer.parseInt(br.readLine()); // 찾으려는 숫자 개수
        // 배열 b
        b = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(st.nextToken());
        }

        // 이분탐색 로직 구현
        // 배열-오름차순 정렬
        Arrays.sort(a);

        for (int i = 0; i < m; i++) {
            int ans = biSearch(b[i]);
            System.out.println(ans);
        }
    }
}

2110 공유기 설치

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

풀이

예제입력 1

	1	2	4	8	9
1	O	O	O	O	O
3	O		O	O
4	O			O

• 최소거리: 1일때 → 모든 집에 설치 O
• 최소거리: 3일때 → 3개 설치 O
• 최소거리: 4일때 → 2개 설치 O

목표: 설치 가능한 공유기 개수가 C개이면서 최소 거리가 최대인 거리를 구해야 함.

→ 답: 3

이분탐색 로직 구현

• low: 최소거리가 가질 수 있는 최소값(초기화: 1)

• high: 최소거리가 가질 수 있는 최댓값

• mid: 중간값

최소거리가 mid 일때 →설치 가능한 공유기 개수(wifi) 구하기

• 설치 가능한 공유기 개수 < 목표 개수: high = mid
• 설치 가능한 공유개 개수 ≥ 목표 개수: low = mid+1

정답코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] home;
    static int n, c;

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

        n = Integer.parseInt(st.nextToken()); // 집
        c = Integer.parseInt(st.nextToken()); // 공유기 개수

        // 집의 좌표 저장
        home = new int[n];

        for (int i = 0; i < n; i++) {
            home[i] = Integer.parseInt(br.readLine());
        }

        // 가장 인접한 두 공유기 사이 최대 거리
        // 입력이 매우 크고, 수직선 위 집의 좌표이므로: 오름차순 정렬 필요 -> 이분탐색

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

        // 2. 이분탐색 범위 변수 지정
        int low = 1; // 공유기 간 최소 거리의 최솟값
        int high = home[n - 1] - home[0];
        // 정답
        int ans = 0;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (wifi(mid) < c) { // 최소거리가 mid 일때, 설치 가능한 공유기 개수 < 목표값 일때
                high = mid - 1;
            } else { // 아니라면, 최소거리가 가질 수 있는 최대거리 찾아낸다
                low = mid + 1;
                ans = mid;
            }
        }
        System.out.println(ans);
    }

    // 최소거리가 mid 일때 설치 가능한 공유기 개수
    private static int wifi(int dist) {
        int cnt = 1; // 첫번째 집은 무조건 설치
        int pre = home[0]; // 직전 위치 초기화

        for (int i = 1; i < n; i++) {
            int cur = home[i]; // 현재 위치
            if (cur - pre >= dist) { // 직전 위치와의 거리가 최소거리보다 클때
                // 공유기 설치 가능
                cnt++;
                pre = cur;
            }
        }
        return cnt;
    }
}

1939 중량제한

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

문제

n개의 섬으로 이뤄진 나라.
섬에 다리를 설치해 1공장에서 -> 2공장으로 차로 통행.
근데, 다리 마다 중량제한 있음에 주의.

따라서 한번의 이동에서 옮길 수 있는 중량의 최댓값?

*다리 규칙

• 두 섬 사이에 여러 개 다리 o
• 다리는 양방향임.

풀이

문제에 쉽게 접근할 수 없다. 그래프 유형인가 이분탐색 아녔나..
풀이가 잘 떠오르지 않았다.

블로그 포스팅 검색을 해봤고, 다양한 풀이가 존재했다.
유니온파인드, 다익스트라, dfs+이분탐색, bfs+이분탐색 등..

그 중 가장 이해가 잘 간 풀이 방식을 바탕으로 문제를 풀었다.

문제의 핵심은 옮길 수 있는 물품들의 중량의 최댓값이다.
이 물품의 중량에 초점을 맞춰서 문제에 접근해야 한다.

문제의 입출력 1을 예시로 들어서 설명하자면,
1-2 정점: 중량제한 2
1-3 정점: 중량제한 3
2-3 정점: 중량제한 2인 다리가 있다.

공장의 위치는 1, 3번에 위치함.

따라서, 1<->3으로 갈때 다리가 무너지지 않고 갈 수 있는 중량은 다음과 같다.
1, 2, 3

여기서 최댓값은 3이므로 정답이 3이다.

이를 토대로 이분탐색을 적용하면 다음과 같다.

먼저, 입력으로 들어오는 중량 중 제일 작은 중량-> low, 제일 큰 중량 -> high로 둔다.
low, high 중간값 -> mid로 설정.
그럼 다음과 같을 것이다

low,middle       high
    2             3

이제, 이 mid에 대해 bfs를 돌려준다. bfs에선 한 공장 -> 다른 공장으로 갈 때 mid 값을 가진 중량으로 다리를 안 부시고 갈 수 있는 지 확인하는 용도다.

bfs 코드는 다음과 같다.

    // 해당 mid 값으로 다리를 안 부시고 갈 수 있는지 체크
    private static boolean bfs(int weight) {
        Queue<Integer> q = new LinkedList<>(); // 큐에 정점 저장
        visited = new boolean[n + 1]; // 방문 체크

        q.offer(start); // 큐에 삽입
        visited[start] = true; // 방문 처리

        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == end) return true; //
            for (int[] next : graph.get(cur)) { // next: {정점, 가중치}
                if (weight <= next[1] && !visited[next[0]]) {
                    visited[next[0]] = true;
                    q.offer(next[0]);
                }
            }
        }
        return false;
    }

bfs의 return 값이 true라면 -> mid값을 가진 중량으로 다리 건널 수 있다는 뜻이므로 중량을 더 올려준다.(low = mid +1)

반대로 return 값이 false라면 -> mid값을 가진 중량으로 다리 건널 수 없다는 뜻이므로 중량을 더 낮춘다.(high = mid -1)

이를 코드로 나타내면 다음과 같다.

        while (low <= high) {
            int mid = (low + high) / 2;

            if (bfs(mid)) {
                low = mid + 1;
            } else high = mid - 1;
        }

low ≤ high 인 이유는, 밑의 그림을 보고 이해할 수 있다.

low, mid         high  -> 초기상태

1, 2              3

		low, mid, high -> bfs(2) 수행
				  3
		mid, high    low -> bfs(3) 수행
			3         4     
								  
	low > high 이므로 끝   

다음과 같이 low, high 값이 같을 때도 이분 탐색을 해줘야 하므로 low≤high 로 둔 것이다.

정답코드

import java.io.*;
import java.util.*;

public class Main {

    static int n, m;
    static ArrayList<ArrayList<int[]>> graph;
    static boolean[] visited;
    static int start, end, ans;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 그래프 생성
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 중량 이분탐색용 low, high 설정
        int low = Integer.MAX_VALUE;
        int high = Integer.MIN_VALUE;

        // 양방향 그래프
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph.get(v1).add(new int[]{v2, w});
            graph.get(v2).add(new int[]{v1, w});
            low = Math.min(w, low);
            high = Math.max(w, high);
        }

        // 출발, 도착 공장 입력
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        while (low <= high) {
            int mid = (low + high) / 2;

            if (bfs(mid)) {
                low = mid + 1;
                ans = mid;
            } else high = mid - 1;
        }

        // 중량 최댓값
        System.out.println(ans);
    }

    // 해당 mid 값으로 다리를 안 부시고 갈 수 있는지 체크
    private static boolean bfs(int weight) {
        Queue<Integer> q = new LinkedList<>(); // 큐에 정점 저장
        visited = new boolean[n + 1]; // 방문 체크

        q.offer(start); // 큐에 삽입
        visited[start] = true; // 방문 처리

        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == end) return true; //
            for (int[] next : graph.get(cur)) { // next: {정점, 가중치}
                if (weight <= next[1] && !visited[next[0]]) {
                    visited[next[0]] = true;
                    q.offer(next[0]);
                }
            }
        }
        return false;
    }
}

18870 좌표 압축

문제

수직선 위 n개의 좌표 x1, x2, … xn → 좌표 압축 적용하려고 함.

xi를 좌표 압축한 결과인 x’i=xi>xj를 만족하는 서로 다른 좌표의 개수와 같아야 함.

x1, x2, …, xn에 좌표 압축을 적용한 결과인 x’1, x’2, …, x’n을 출력하기

풀이

문제만 봐선 어떤 걸 답으로 요구하는지 파악하기 쉽지 않았다.

블로그 포스팅을 살핀 결과, 원소의 순위를 출력하는 문제였다.

예제 입력 1을 보면 2, 4, -10, 4, -9에서 -10이 제일 작은 값을 가지므로 0을 출력하고, 그 다음 -9이므로 1을 출력, 그 다음 2는 2을 출력, 4는 동일한 값이 2개 이므로 2개 모두 3을 가진다.

이렇게 순위를 매긴다고 생각하고 접근하는 것이었다.

순위를 매기려면 어떻게 해야할까?

1. 등수를 매기기 위해, 중복을 제거한 set 집합 만들기
   • Set를 사용해 중복을 제거한 원소의 개수를 확인.
2. 집합의 요소를 오름차순 정렬한다.
   • List에 Set의 원소를 담고, Collections.sort()를 사용해 오름차순 정렬
3. 순위를 하나씩 증가해가면서 등수를 매긴다.
   • 정렬된 리스트를 순회하며, 작은 값부터 큰 값 순으로 순위 부여.
   • 이때 요소를 key로 한 딕셔너리를 만들어 순위를 저장한다(동일 원소 처리) → 원본 배열에서 key로 찾아서 등수 출력 가능
4. 등수 출력
   • 입력받은 원소 배열을 순회하면서, hashmap에서의 value를 출력한다

정답코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 원소 배열
        int[] arr = new int[n];

        String line = br.readLine(); // 두 번째 줄 전체 읽기
        StringTokenizer st = new StringTokenizer(line); // 공백 기준으로 나누기

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //System.out.println(Arrays.toString(arr));

        // 0. set 배열 만들기
        Set<Integer> number = new HashSet<>();
        for (int num : arr) {
            number.add(num); // 배열을 set에 추가
        }

        // 1. 집합의 요소를 오름차순 정렬한다.
        List<Integer> sortedKey = new ArrayList<>(number);
        Collections.sort(sortedKey);

        // 2. 등수 매기기
        int rank = 0;
        HashMap<Integer, Integer> rankMap = new HashMap<>();

        for (int key : sortedKey) {
            rankMap.put(key, rank++); // 순위 증가
        }

        // 4. 입력받은 원소 배열을 순회하면서 hashmap에서 value(등수) 출력
        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
            sb.append(rankMap.get(num)).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}

3079 입국심사

문제

m명의 사람, n개의 입국심사대.

k번 심사대에서 심사하는데 걸리는 시간 Tk임.

한 심사대에서는 한 번에 한 사람만 심사 가능.

→ 심사를 받는데 걸리는 시간의 최솟값?

풀이

예제 입력 1 보게되면,

2 6
7
10

28

2개의 입국심사대, 6명이 모두 심사를 받는데 걸리는 시간의 최솟값을 구하려면,

• 7초 소요: 1번 심사대에서 4명
• 10초 소요: 2번 심사대에서 2명이 심사를 받으면

28초만에 6명 모두가 심사받으며, 최소값은 28초이다.

또 예제 입력 2 보게되면,

7 10
3
8
3
6
9
2
4

8

7개의 입국심사대, 10명이 모두 심사를 받는데 걸리는 시간의 최솟값을 구하려면,

• 1번 심사대: 2명
• 2번 심사대: 1명
• 3번 심사대: 2명
• 4번 심사대: 1명
• 5번 심사대: 0명
• 6번 심사대: 3명
• 7번 심사대: 1명

8초만에 10명 모두가 심사받으며, 최소값은 8초이다.

풀이

모두 심사를 받는 최소 시간를 구하려면, 각 심사대의 심사를 마치는 최소, 최대 사이의 중간값을 바탕으로 가능한지 판단하자. → 이분탐색 진행.

1. 시간 범위 설정
   • 최소 시간: low= 1 (최소 1초는 걸림)
   • 최대 시간: high= m * max(Tk) (가장 느린 심사대에서 모든 사람이 처리되는 경우)
2. 이분탐색
   • mid: 심사를 받는데 걸리는 시간
   • mid 시간 동안, 몇 명이 입국심사 할 수 있는지?
     • 각 심사대에서 최대로 심사할 수 있는 사람 수 구해 → people 라는 변수에 저장
   • 만약 people > m(사람 수) : high=mid-1
     • mid 시간 내에 모든 사람을 처리할 수 있으므로 시간 줄여야 함.
   • people < m 이라면: low = mid+1
     • mid 시간내 모든 사람 처리 불가 → 시간 늘려야 함.
3. 결과 반환
   • 이분탐색이 끝난 후, 최소 시간이 mid에 저장됨.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); // 공백 기준으로 나누기

        int n = Integer.parseInt(st.nextToken()); // 심사대
        int m = Integer.parseInt(st.nextToken()); // 사람

        // 입국심사 시간 배열
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 이분 탐색
        Arrays.sort(arr);
        long low = 1;
        long high = (long) m * arr[n - 1]; // 10억 * 10억 -> int형 표현 범위(21억) 벗어나기 때문에 -> long형 사용
        long ans = high; // 정답: 최소 시간 저장

        while (low <= high) {
            long mid = (low + high) / 2;

            long people = 0; // 현재 시간(mid)동안 처리할 수 있는 사람 수

            for (int time : arr) {
                people += mid / time;
                if (people >= m) break; // 이미 필요한 사람 수를 초과할때 더 계산할 필요 없음
            }

            if (people >= m) {
                ans = mid; // 가능한 경우 최솟값 갱신
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

주의

입력값이 크므로, 자료형 오버플로우에 주의해야 한다.
이분탐색에 필요한 변수들이 long형임에 주의하자.