이진 탐색(binary search, 이분 탐색)
이진 탐색은 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다. 정렬된 데이터의 중앙값과 찾으려는 값을 비교해 탐색 범위를 절반씩 줄이면서 대상을 찾는 방식이다.
이진 탐색은 일반적으로 정렬 데이터에서 원하는 값을 찾는 데 가장 많이 사용되는 알고리즘이다.
이진 탐색의 시간복잡도는 O(nlogn)이다.
이진 탐색의 과정을 예시를 통해 살펴보자.
오름차순으로 정렬된 데이터가 있다. 우리는 23이라는 값을 찾고자 한다.
첫번째 배열에서 중앙값을 찾으면 16이 된다(전체 크기가 짝수일 경우 일반적으로 더 작은 것을 중앙값으로 선택).
16은 찾고자 하는 23보다 작으므로 (16 < 23) 중앙값 왼쪽에 있는 값은 탐색할 필요가 없다.
그럼 이제 남은 배열은 [23, 38, 56, 72, 91]이다.
마찬가지로 중앙값인 56과 23을 비교해보면, 56 > 23이므로 이번엔 중앙값 오른쪽에 있는 값을 버린다.
배열은 [23, 38]이 된다.
이때의 중앙값인 23이 찾고자 하는 값 23과 일치하므로 탐색을 완료한다.
이진 탐색의 과정을 일반화하여 요약하면 다음과 같다.
- 현재 데이터들의 중앙값을 선택한다.
예를 들어, 데이터 크기가 11개라면 6번째 값을, 10개라면 5번째(또는 6번째)를 선택. 구현 시에는 정수형 변수로
나누기 2 연산을 수행하면 중앙값의 index를 구할 수 있다.- 중앙값 > 찾으려는 값 → 중앙값 기준으로 왼쪽 데이터 선택 중앙값 < 찾으려는 값 → 중앙값 기준으로 오른쪽 데이터 선택
- 과정 1~2를 반복하며, 중앙값 == 찾으려는 값일때 탐색 종료
이진 탐색을 활용한 문제를 풀어보자.
백준 #1920번 : 수 찾기
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
풀이
N의 범위를 살펴보면, 최대일 때 100,000이므로 단순 반복으로는 시간 초과가 날 것이다. 따라서 O(nlogn)의 시간복잡도를 가진 이진 탐색을 적용해보자.
이진 탐색은 보통 다음과 같이 구현한다.
int target = 찾으려는값; int start = 0; int end = A.length - 1; int answer = 0; while (start <= end) { int mid = (start + end) / 2; if (A[mid] > target) { end = mid - 1; } else if (A[mid] < target) { start = mid + 1; } else { answer = 1; break; } } System.out.println(answer);
시작 인덱스와 종료 인덱스를 각각 0과 배열 끝으로 초기화한다.
(시작 인덱스 + 종료 인덱스)/2 를 해 중앙값 인덱스를 구하고, 찾고자 하는 값과 중앙값을 비교한다.만약,
중앙값 > 찾으려는 값이라면 종료 인덱스를 중앙값 인덱스보다 1 작게 설정해 중앙값 왼쪽을 선택한다.중앙값 < 찾으려는 값 이라면 시작 인덱스를 중앙값 인덱스보다 1 크게 설정해 중앙값 오른쪽을 선택한다.ㅣ중앙값 == 찾으려는 값 이면 탐색을 종료한다.처음 데이터를 오름차순 정렬하는 것도 잊지 말자.
이 로직을 바탕으로 문제 조건에 맞춰 전체 코드를 작성하면 다음과 같다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; 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()); 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); //오름차순 정렬 int M = Integer.parseInt(br.readLine()); st = new StringTokenizer(br.readLine()); for(int i=0; i<M; i++) { int target = Integer.parseInt(st.nextToken()); int start = 0; int end = A.length - 1; int answer = 0; while(start <= end) { int mid = (start+end)/2; if(A[mid] > target) { end = mid - 1; } else if(A[mid] < target) { start = mid + 1; } else { answer = 1; break; } } System.out.println(answer); } } }
결과 | 메모리 | 시간 |
맞았습니다!! | 52460 KB | 656 ms |
좀 더 응용된 문제를 풀어보자.
백준 #1072번 : 게임
문제
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
- 게임 횟수 : X
- 이긴 게임 : Y (Z%)
- Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
입력
각 줄에 정수 X와 Y가 주어진다.
- 1 ≤ X ≤ 1,000,000,000
- 0 ≤ Y ≤ X
출력
첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.
풀이
주어진 X와 Y에 대하여, 승률 Z가 변하기 위해 더 이겨야 하는 게임의 횟수를 찾는 문제이다.
이진 탐색 범위를 설정할 때, 시작 값(s)를 0으로, 끝 값(e)을 X의 최대 범위인 10억으로 설정한다.
승률은 다음과 같이 계산할 수 있다:
(int)((long)(Y + mid) * 100 / (X + mid))이 값이 초기 승률 Z와 다른지를 확인하여, 만약 이 값이 Z와 다르다면
answer에 mid 값을 저장하고, 이진 탐색의 끝 범위 값을 mid - 1로 설정(중앙값 왼쪽 선택)한다.만약 승률이 같다면, 이진 탐색의 시작 범위 값을
mid + 1로 설정(중앙값 오른쪽 선택)한다.이 과정을 시작 범위가 끝 범위보다 크거나 같을 때까지 반복한다.
이렇게 하면, 최소로 더 이겨야 하는 게임의 횟수를 찾을 수 있다. 만약 승률 Z가 절대 변하지 않는다면, answer의 값은 -1이 된다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; 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 X = Integer.parseInt(st.nextToken()); int Y = Integer.parseInt(st.nextToken()); int Z = (int) ((long) Y * 100 / X); // 현재 승률 int answer = -1; int s = 0; int e = (int) 1e9; //10억 while (s <= e) { int mid = (s + e) / 2; if ((int)((long)(Y + mid) * 100 / (X + mid)) != Z) { answer = mid; e = mid - 1; } else { s = mid + 1; } } System.out.println(answer); } }
결과 | 메모리 | 시간 |
맞았습니다!! | 14212 KB | 132 ms |
댓글