📙[Algo] 24.02.01 이진탐색 / 알고리즘

이진탐색 정리

이진탐색 아이디어

• 투포인터와 이진탐색의 핵심 아이디어는 똑같다.
• 이진탐색 개념을 제대로 잡자!
• 현재 후보들 중 가운데를 기준으로, 후보를 절반씩 날린다. ⇒ logN번이면 범위를 1개까지 줄일 수 있다.
  • n, n/2, n/4, n/8, n/16…..
• 잘못 알고 있던 개념
  • 이진탐색은 정렬된 배열에서 특정 값이 있는지 확인하는 알고리즘, 특정 값의 인덱스를 찾는 알고리즘 ⇒ 이진탐색 문제 유형 중 하나

💡 이진탐색
정답의 후보 범위 : [s, e]
mid 값을 볼 때, 후보 절반을 날려버릴 수 있다면 이진탐색이 가능하다. 

• 예시
  • 아래 수열에서 15의 인덱스를 찾고싶다면?

    0	1	2	3	4	5	6	7	8	9
    1	2	5	6	7	8	10	15	20	23

  • s → 0, e → 9를 가리키고 시작. 투포인터처럼 정답 후보를 제거한다는 생각으로 진행.
    투포인터처럼 정답 후보를 제거한다는 생각으로 진행.
    

static int binarySearch(int s, int e, int v, int[] arr) {
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if(arr[mid] == v) return mid;
            else if(arr[mid] < v) s = mid + 1;
            else e = mid - 1;
        }
        return -1; // 정답이 없다면 
    }

 

이진탐색 응용

• 예시
  문자열 S는 게속 ‘X’가 나오다가, 후에 ‘O’가 등장한다. 이때, O 중에 가장 왼쪽에 있는 ‘O’의 인덱스를 찾자.
• x x x x x x x x x x x x o o o o o o o
  s                       m                        e
  
  • m → x
  • m 기준으로 왼쪽은 다 x니까 후보에서 날릴 수 있음
• x x x x x x x x x x x x o o o o o o o
                              s            m       e
  • m → o
    • m 기준 오른쪽은 다 o인데, 구하고자 하는 것은 가장 왼쪽에 있는 o이니까 답의 후보에서 제거
    • 혹시 모르니 현재 인덱스는 정답 변수에 저장
• x x x x x x x x x x x x o o o o o o o
                              s    m   e
  • m → o
    • 정답 갱신

static int binarySearch(int s, int e, String[] arr) {
        int mid, ans = -1;
        while (s <= e) {
            mid = (s + e) / 2;

            if(arr[mid].equals("x")) s = mid + 1;
            else if (arr[mid].equals("o")) {
                ans = mid;
                e = mid - 1;
            }
        }
        return ans;
    }

 

• 예시
  문자열 S가 다음과 같이 주어 졌을 때, ! 중에 제일 오른쪽 인덱스 찾기xxxxxxxxxxxoooooooooooo!!!!!!!!!!!!!!!!!#################
  
  • ‘x’ → s = mid + 1
  • ‘o’ → s = mid + 1
  • ‘!’ → ans = mid, s = mid + 1
  • ‘#’ → e = mid - 1

BOJ10815. 숫자카드

문제 요약 : 상근이가 갖고 있는 N개의 숫자카드에, 주어진 M개의 숫자들이 존재하는지 체크하는 문제(존재하면 1, 없으면 0)

• 풀이1. 이진탐색

static int binarySearch(int s, int e, int key, int[] arr) {
        int mid, ans = 0;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] == key) {
                ans = 1;
                break;
            } else if (arr[mid] < key) {
                s = mid + 1;
            } else {
                e = mid - 1;
            }
        }
        return ans;
    }

• 풀이2. 방문처리 / 카운팅 배열 활용
  • int[] cnt = [0, 0, 0, ….] → 크기는 대략 2000만(숫자카드에 적혀있는 수가 -1000만~1000만까지니까 주어진 숫자에 + 1000만을 더함, 인덱스가 숫자를 의미)
  • 숫자가 들어올 때마다 cnt[숫자] += 1

• 풀이3. 쿼리 정렬 후 투포인터(오프라인 쿼리)
  • 주어진 두 배열을 모두 정렬하고 투포인터 진행
    -10 2 3 6 10
    s1
    -10 -5 2 3 4 5 9 10
    s2
  • 다만 출력 순서가 꼬일 수 있어 따로 처리 필요!

BOJ10816. 숫자카드2

문제 요약 : 숫자카드 문제에서 존재 여부가 아니라 몇 개 갖고 있는지 알아내기
-10 -10 2 3 3 6 7 10 10 10
3이 몇 개?

• 풀이1. 카운팅 배열 → 그대로 접근해서 사용 가능
• 풀이2. 이진탐색(3 중에서 제일 왼쪽 인덱스를 찾고, 3 중에서 제일 오른쪽 인덱스를 찾는다. )

static int leftIdx(int s, int e, int[] arr) {
    int mid, ans = -1;
    while (s <= e) {
        mid = (s + e) / 2;

        if (arr[mid] < 3) {
            s = mid + 1;
        } else if (arr[mid] > 3) {
            e = mid - 1;
        } else {
            ans = mid;
            e = mid - 1;
        }
    }
    return ans;
}

static int rightIdx(int s, int e, int[] arr) {
    int mid, ans = -1;
    while (s <= e) {
        mid = (s + e) / 2;

        if (arr[mid] < 3) {
            s = mid + 1;
        } else if (arr[mid] > 3) {
            e = mid - 1;
        } else {
            ans = mid;
            s = mid + 1;
        }
    }
    return ans;
}

• 풀이3. lower_bound, upper_bound
  • lower_bound(x) : x보다 크거나 같은 것들 중 제일 왼쪽 인덱스
  • upper_bound(x) : x보다 큰 것들 중 제일 왼쪽 인덱스
  • 형태가 단조성을 띄어야 함 → 3기준 왼쪽은 3보다 작거나 같고, 오른쪽은 크거나 같을 때

static int lowerBound(int s, int e, int[] arr) {
    int mid, ans = arr.length;
    while (s <= e) {
        mid = (s + e) / 2;

        if (arr[mid] >= 3) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return ans;
}

static int upperBound(int s, int e, int[] arr) {
    int mid, ans = arr.length;
    while (s <= e) {
        mid = (s + e) / 2;

        if (arr[mid] > 3) {
            ans = mid;
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return ans;
}

• 3보다 작거나 같은 것 중 제일 오른쪽? upper_bound - 1
• 3보다 작은 것 중 가장 오른쪽? lower_bound - 1

매개변수 탐색(Parametric Search)

• 최적화 문제를 결정 문제로 바꿔서 푸는 방식
  • 시간을 줄이는 알고리즘이 아님. 그냥 나무 자르기 문제에서는 최적화 방법으로 이진 탐색을 사용한 것!
  • 최적화 : 최댓값/최솟값 찾기
  • 결정 문제 : 구하고자 하는 값 True/False로 결정되는 문제

BOJ2805. 나무 자르기

문제 요약 : 나무 높이가 주어졌을 때, 우리가 얻고 싶은 양 이상을 얻을 수 있는 높이 중 최대값 찾기

나무 높이 20 15 10 17
7만큼 얻고 싶다.

• 일단 완전탐색으로 접근 → 모든 높이에서 잘라본다.
  • 높이의 최댓값을 구하라 (최적화 문제)
    ⇒ 각 높이를 보면서, 이 높이가 되냐? (결정 문제)
  • 모든 높이에서 잘라봐야 한다. ⇒ 10억
  • 이 높이가 답이 되는지 체크해봐야 한다 ⇒ N
  • O(10억 * N) ⇒ 1번 최적화 필요

• 최적화
  • 중간에서 잘라보며, 정답 후보를 추려내기

---

알고리즘 문제) BOJ 10815. 숫자 카드

10815번: 숫자 카드

문제 요약

• 숫자 카드 N개가 존재
• 정수 M개가 주어졌을 때 숫자 카드에 존재하는지 여부 출력

시간 제한

• 2초

입력

• 숫자 카드 개수 N
  • 1~50만
• N개의 숫자들이 주어짐
  • -1000만~1000만
• M
  • 1~50만
• M개의 정수가 주어짐
  • -1000만 ~ 1000만

출력

• 존재하면 1, 아니면 0

접근법

1. 완전탐색으로 접근하기
   주어진 정수들을 하나하나 숫자카드에 돌면서 있는지 확인한다. 숫자 카드 최대 개수 (N) * 주어진 정수 최대 개수(M) = O(50만*50만)이므로 시간초과가 발생한다. 일단 M은 하나씩 훑어야 하므로 N시간을 줄일 필요가 있다. ⇒ 즉, 모든 숫자를 훑으면 안된다!
2. 최적화 하기

• 이진탐색은 후보를 반씩 날릴 수 있는 문제에 적용할 수 있다. 일단 주어진 숫자카드를 오름차순 정렬하고, s→0, e→N-1을 가리킨다음, s와 e의 정 중앙을 탐색하면서 찾고자하는 값보다 클 경우 중앙 기준 왼쪽에 있는 후보들은 볼 필요가 없으므로 제외시키고, 작을 경우 오른쪽에 있는 후보들을 제거해가는 방향으로 진행한다.
• 카운팅 배열 사용하기 주어지는 숫자범위가 -1000만~1000만 까지라는 걸 고려했을 때, 대략 2000만 크기의 배열을 만들고, 인덱스가 곧 숫자가 되도록 하려면 음수를 처리해야하므로 주어진 숫자 + 1000만에 해당하는 인덱스에 카운팅해준다. 즉, 숫자카드에 적혀있는 숫자들을 카운팅하고, M개의 정수를 돌면서 해당 값이 0인지 아닌지에 따라 답을 출력.

코드

이진탐색

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    static int binarySearch(int s, int e, int key, int[] arr) {
        int answer = 0;
        int mid;

        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] < key) {
                s = mid + 1;
            } else if (arr[mid] > key) {
                e = mid - 1;
            } else {
                answer = 1;
                break;
            }
        }
        return answer;
    }


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

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

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

        Arrays.sort(cards);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append(binarySearch(0, N - 1, nums[i], cards)+" ");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

카운팅 배열

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


public class Main {

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] cards = new int[20000010];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[Integer.parseInt(st.nextToken()) + 10000000]++;
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            if (cards[Integer.parseInt(st.nextToken()) + 10000000] > 0) {
                sb.append(1 + " ");
            } else {
                sb.append(0 + " ");
            }
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 10816. 숫자 카드 2

10816번: 숫자 카드 2

문제 요약

• 숫자 카드 N개에서 주어진 M개의 정수가 각각 몇 개 존재하는지 출력

시간 제한

• 1초

입력

• 숫자 카드 개수 N
  • 1~50만
• N개의 숫자들이 주어짐
  • -1000만~1000만
• M
  • 1~50만
• M개의 정수가 주어짐
  • -1000만 ~ 1000만

출력

• 몇 개 갖고 있는가?

접근법

완전탐색으로 접근한다면, 각각 숫자마다 숫자카드를 돌면서 존재하는 수 카운팅하면 된다. 그러나 O(N*M)은 시간초과가 뜨므로, 숫자 카드를 모두 보지 않도록 최적화 할 것.

카운팅 배열 사용 가능 → 일단 pass(숫자카드에서 다뤄봤으니)

이진탐색으로 어떻게 개수를 출력할 수 있을까?
특정 숫자 key가 적힌 숫자 카드 중 가장 오른쪽에 존재하는 카드의 인덱스 - 가장 왼쪽에 존재하는 카드의 인덱스 + 1하면 구할 수 있음.
즉, 일단 숫자카드를 오름차순 정렬하고, 이진탐색으로 후보 절반을 제거해 간다. 만약 해당 key가 존재한다면 일단 해당 숫자의 인덱스를 저장해놓고, 가장 왼쪽을 탐색하는 거면 오른쪽 제거, 가장 오른쪽을 탐색하는 거면 왼쪽을 제거한다.

lower bound, upper bound를 사용해서도 풀 수 있다.
lower bound는 key보다 크거나 같은 것들 중 제일 왼쪽 인덱스
upper bound는 key보다 큰 것들 중 제일 왼쪽 인덱스
⇒ 즉 포함하면 lower, 포함하지 않으면 upper…
만약 key보다 작거나 같은것들 중 가장 오른쪽은 upperbound-1
만약 key보다 작은 것 중 가장 오른쪽은 lower bound - 1
이걸 이용해서 풀어본다면, upper bound - lower bound가 답이 됨.

코드

이진탐색

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


public class Main {

    // 나보다 크거나 같은 것들 중 가장 왼쪽 찾기
    static int lowerBound(int s, int e, int key, int[] arr) {
        int ans = -1;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] >= key) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

    // 나보다 큰 것들 중 가장 왼쪽 찾기
    static int upperBound(int s, int e, int key, int[] arr) {
        int ans = arr.length;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] > key) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

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

        Arrays.sort(cards);
        int ub, lb;
        for (int i = 0; i < M; i++) {
            ub = upperBound(0, N - 1, nums[i], cards);
            lb = lowerBound(0, N - 1, nums[i], cards);

            sb.append(ub - lb + " ");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

lower bound, upper bound

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


public class Main {

    // 나보다 크거나 같은 것들 중 가장 왼쪽 찾기
    static int lowerBound(int s, int e, int key, int[] arr) {
        int ans = arr.length;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] >= key) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

    // 나보다 큰 것들 중 가장 왼쪽 찾기
    static int upperBound(int s, int e, int key, int[] arr) {
        int ans = arr.length;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] > key) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

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

        Arrays.sort(cards);
        int ub, lb;
        for (int i = 0; i < M; i++) {
            ub = upperBound(0, N - 1, nums[i], cards);
            lb = lowerBound(0, N - 1, nums[i], cards);

            sb.append(ub - lb + " ");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 16498. 작은 벌점

16498번: 작은 벌점

문제 요약

• 3명의 플레이어 별로 한 장 이상의 숫자카드를 받게 되고, 그 중 한 장을 선택해 내려 놓음
• 이때 3 개의 숫자 중 최댓값-최솟값의 차이가 벌점
• 주어진 숫자카드를 통해 만들 수 있는 가장 작은 벌점 구하기

시간 제한

• 1초

입력

• 플레이어 순서대로 각자 받은 숫자 카드 개수 A, B, C
  • 1 ≤ A, B, C ≤ 1,000
• 첫 번째 플레이어가 받은 숫자 카드에 적힌 수
• 두 번째 플레이어가 받은 숫자 카드에 적힌 수
• 세 번째 플레이어가 받은 숫자 카드에 적힌 수
  • 각 숫자는 -1억 ~ 1억 범위 내 정수

출력

• 세 플레이어가 만들 수 있는 가장 작은 벌점?

접근법

1. 완전 탐색으로 생각하기
   각자 카드 하나씩 꺼내는 모든 경우의 수를 구하고 그중 최소 벌점을 찾는다.
   세 플레이어가 만들 수 있는 카드 조합 경우의 수 100010001000
   ⇒ 10억 연산이 발생하므로 최적화 필요
2. 최적화 하기
   모든 조합을 보면 안된다!!! 또한 2중 for문 까지만 가능하다.
   각 플레이어 별로 무조건 선택이 안 되는 카드가 있을 수 있따!!
   ⇒ 즉 해당 카드가 어떤 조합에서도 크기가 중간에 위치하는 경우
   1
   6 9 15
   2 3 6 6
   
   4
   6 9 15
   2 3 6 6
   
   5
   6 9 15
   2 3 6 6
   
   8
   6 9 15
   2 3 6 6 x ⇒ pass
   
   10
   6 9 15
   2 3 6 6 x ⇒ pass
   
   ⇒ 사실상 처음부터 오름차순 정렬하고 사용하면 8부터 뒤는 싹다 안 봐도 됨
   ⇒ 플레이어별로 돌아가면서 해당 플레이어(p)가 선택한 값이 무조건 최솟값이 될 수 있는 경우의 수를 찾는데, 나머지 플레이어의 카드를 lower bound를 돌면서 그 중 p보다 크거나 같은 것들 중 가장 왼쪽에 있는 애들을 2개로 추려낸다. 그리고 그 중 큰 값이 max 값이 되게 하고 둘의 차이값을 정답값으로 갱신한다. 그리고 중간에 lower bound를 돌렸을 때 인덱스가 배열 범위 밖을 벗어나는 경우 애초에 p가 최솟값으 선택될 수 있는 조합이 없다는 뜻이므로 pass
   ⇒ 즉 위 구조를 총 3번 하는거!!
   
   

코드

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


public class Main {

    // 나보다 크거나 같은 것들 중 가장 왼쪽 찾기
    static int lowerBound(int s, int e, int key, int[] arr) {
        int ans = -1;
        int mid;
        while (s <= e) {
            mid = (s + e) / 2;

            if (arr[mid] >= key) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }
        return ans;
    }

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

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

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

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

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

        Arrays.sort(cardsA);
        Arrays.sort(cardsB);
        Arrays.sort(cardsC);

        int answer = Integer.MAX_VALUE;
        int idx1, idx2;

        // 플레이어 A가 선택한 카드가 최솟값이 되게 할 때
        for (int i = 0; i < A; i++) {
            idx1 = lowerBound(0, B - 1, cardsA[i], cardsB);
            idx2 = lowerBound(0, C - 1, cardsA[i], cardsC);

            if(idx1 < 0 || idx2 < 0) break;

            answer = Math.min(answer, Math.abs(Math.max(cardsB[idx1], cardsC[idx2]) - cardsA[i]));
        }

        // 플레이어 B가 선택한 카드가 최솟값이 되게 할 때
        for (int i = 0; i < B; i++) {
            idx1 = lowerBound(0, A - 1, cardsB[i], cardsA);
            idx2 = lowerBound(0, C - 1, cardsB[i], cardsC);

            if(idx1 < 0 || idx2 < 0) break;

            answer = Math.min(answer, Math.abs(Math.max(cardsA[idx1], cardsC[idx2]) - cardsB[i]));
        }

        // 플레이어 C가 선택한 카드가 최솟값이 되게 할 때
        for (int i = 0; i < C; i++) {
            idx1 = lowerBound(0, A - 1, cardsC[i], cardsA);
            idx2 = lowerBound(0, B - 1, cardsC[i], cardsB);

            if(idx1 < 0 || idx2 < 0) break;

            answer = Math.min(answer, Math.abs(Math.max(cardsA[idx1], cardsB[idx2]) - cardsC[i]));
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}