이진탐색
이진 탐색(Binary Search)은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다.
대상 데이터의 중앙값과 찾고자 하는 값을 비교해서 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다.
| 기능 | 특징 | 시간 복잡도 |
| 타깃 데이터 탐색 | 중앙값 비교를 통한 대상 축소 방식 | O(logN) |
구현과 원리가 간단해서 코딩 테스트에서 보통 부분 문제로 포함되어 있는 경우가 많습니다.
이진 탐색의 핵심 원리
이진 탐색을 오름차순으로 정렬된 데이터에서의 예로 찾아보겠습니다. 내림차순으로 정렬되어 있는 경우에도 조건을 반대로 해서 똑같이 실행하면 됩니다.)
이진 탐색 과정
- 현재 데이터셋의 중앙값(median)을 선택.
- 중앙값 > 타겟 데이터(찾고자 하는 데이터) 일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택
- 중앙값 < 타겟 데이터일 때 중앙값 기준으로 오른쪽 데이터 셋을 선택
- 1 ~ 3의 과정 반복. 만약 중앙값 == 타겟 데이터라면 탐색을 종료합니다.
그림으로 보면 단번에 이해가 될 것입니다. 데이터 셋이 {3, 7, 13, 15, 23, 35, 38, 41, 46, 49, 55, 67, 68, 72, 77, 86} 이라고 합시다.
16개의 데이터라면 탐색을 최대 4번으로 타겟 데이터를 찾을 수 있습니다. 즉, N개의 데이터는 O(logN) 의 시간 복잡도를 가진다.
하지만 이진 탐색은 반드시 데이터가 정렬되어 있어야 합니다다.
그림을 보고 눈치챘을 지도 모르지만 이진 탐색과 투 포인터가 어느정도 비슷한 그림을 가지는 것을 보아 두 원리가 같이 쓰이는 문제도 여럿 있을 것 같네요
백준 1920 수 찾기
https://www.acmicpc.net/problem/1920
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
1. 문제 분석
N 개의 수가 배열 A 로 주어지고 M 개의 수들이 배열 A 에 존재하는지를 판단하는 문제입니다. N의 최대값이 100,000, M의 최대값이 100,000 이므로 단순한 완전 탐색을 진행하는 경우 한번의 탐색에서 O(N) 의 시간이 걸리고 M 번 탐색 시 O(N 𝘅 M) = O(100,000 𝘅 100,000) = O(10,000,000,000) 입니다. 100억번의 연산을 해야 하므로 시간 제한인 1초를 훌쩍 넘깁니다.
이진탐색을 이용한다면 데이터를 정렬하는 시간과 탐색 시간을 더한 O(Nlog(N) + Mlog(N) ) 의 시간이 걸립니다. 약 O( 1,700,000+ 1,700,000) = O(3,400,000) 이므로 1초 안에 충분히 가능합니다.
2. 손으로 풀기
3. 슈도코드
N: 수의 개수 A: 배열
A 배열 입력받고 초기화
A 배열 정렬
M: 질의 개수
mIndex: A 배열의 중앙 인덱스
for(질의개수){
입력반은 수 targetData
A 배열에 새로 입력받은 수가 있는지 이진 탐색
// 재귀함수로 구현
binarySearch(sIndex, eIndex){
if(sIndex > eIndex){sout(0); return;}
else{
int mIndex = (sIndex + eIndex)/2
if(A[mIndex] == targetData){ sout(1); return;}
else if (A[mIndex] > targetData){
sIndex = mIndex + 1
binarySearch(sIndex, eIndex, mIndex)
} else //(A[mIndex] < targetData)
{
eIndex = mIndex - 1;
binarySearch(sIndex, eIndex)
}
}
}
4. 코드
import java.io.*;
import java.util.*;
public class BaekJun1920Self {
static ArrayList<Integer> A;
static int targetData;
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
A = new ArrayList<>(N);
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
A.add(i, Integer.parseInt(st.nextToken()));
}
Collections.sort(A);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
targetData = Integer.parseInt(st.nextToken());
binarySearch(0, N - 1);
}
bw.flush();
br.close();
bw.close();
}
static void binarySearch(int sIndex, int eIndex) throws IOException {
if (sIndex > eIndex) {
bw.write("0" + "\n");
} else {
int mIndex = (sIndex + eIndex) / 2;
if (targetData == A.get(mIndex)) {
bw.write("1" + "\n");
} else if (targetData > A.get(mIndex)) {
sIndex = mIndex + 1;
binarySearch(sIndex, eIndex);
} else {
eIndex = mIndex - 1;
binarySearch(sIndex, eIndex);
}
}
}
}
백준 2343 기타 레슨
https://www.acmicpc.net/problem/2343
2343번: 기타 레슨
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
1. 문제 분석
모든 강의는 1편부터 순서대로 녹화됩니다.
블루레이의 크기가 모두 같고 녹화 순서가 바뀌지 않아야 한다는 문제의 조건에서 이진 탐색 알고리즘을 써야 한다는 힌트를 얻을 수 있습니다.
강의 영상이 여러 개 있을 때 블루레이의 크기는 최소한 가장 긴 영상 길이만큼은 되어야 합니다. 그렇지 않다면 한편의 영상 하나가 여러 블루레이로 쪼개지겠죠. 이렇게 되면 안됩니다.
(사실 문제 조건에서 정확히 이 부분에 대해 이야기하고 있지는 않더라구요. 하지만 이 조건이 추가되어야 합니다.)
그리고 블루레이 크기의 최소를 구하는 문제이므로 모든 강의 영상의 길이의 합보다는 블루레이가 더 클 필요가 없습니다. 그러므로 블루레이의 크기를 최소값(영상 길이의 최대값)부터 최대값(영상 길이의 총합) 사이의 값이라는 것을 알 수 있습니다. 이 값 사이에서 이진 탐색을 진행하면 됩니다.
2. 손으로 풀기
문제에서 제시하는 예제 입력을 손으로 풀어보겠습니다.
위와 같은 방법으로 풀면 됩니다.
3. 슈도코드
N: 레슨수, M: 블루레이 수
result: 결과값
lessons: 레슨 배열
sIndex: 레슨 영상 중 최대 길이. eIndex: 모든 레슨 영상 길이의 합
for(레슨 수) {
lessons 초기화. sIndex, eIndex 을 설정
}
binarySearch(sIndex, eIndex);
sout(result)
// 이진 탐색 메소드
binarySearch(sIndex, eIndex){
if(sIndex>eIndex){ sout(result)}
else{
int mIndex = (sIndex+eIndex)/2
// mIndex 가 이번에 검사하고자 하는 블루레이의 크기
int temp = 0;
int cnt = 1; // 블루레이의 개수
for(N){
temp 에 현재 레슨 영상 길이를 더한다.
if(temp > mIndex){
temp = 0
cnt++;
temp에 현재 레슨 영상 길이를 더한다.
}
}
if(cnt <= M) { // 블루레이의 크기를 뎌 줄여야 함.
result = mIndex;
eIndex = mIndex - 1;
binarySearch(sIndex, eIndex)
}else{ // 블루레이 크기를 더 늘려야 함.
sIndex = mIndex + 1;
binarySearch(sIndex, eIndex)
}
}
}
4. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BaekJun2343Self {
static int N, M;
static int[] lessons;
static int result;
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());
lessons = new int[N];
int sIndex = 0;
int eIndex = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int curLesson = Integer.parseInt(st.nextToken());
lessons[i] = curLesson;
if (curLesson > sIndex) {
sIndex = curLesson;
}
eIndex += curLesson;
}
binS(sIndex, eIndex);
System.out.println(result);
}
private static void binS(int sIndex, int eIndex) {
if (sIndex > eIndex) {
return;
} else {
int mIndex = (sIndex + eIndex) / 2;
int temp = 0;
int cnt = 1;
for (int i = 0; i < N; i++) {
temp += lessons[i];
if (temp > mIndex) {
cnt++;
temp = lessons[i];
}
}
if (cnt <= M) {
result = mIndex;
eIndex = mIndex - 1;
binS(sIndex, eIndex);
} else {
sIndex = mIndex + 1;
binS(sIndex, eIndex);
}
}
}
}
백준 1300 K번째 수
https://www.acmicpc.net/problem/1300
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
1. 문제 분석
처음 읽었을 때 문제가 잘 이해가 되지 않았습니다. 이 문제는 코드를 작성하고 손으로 풀기 전에 자세히 분석해 봐야 할 것 같습니다. 이런 의미입니다.
k의 범위는 1 ~ min(10⁹, N²) 입니다. 만약 시간 복잡도가 N² 인 알고리즘을 사용한다면 N⁴ 가 되어서 2초인 시간 제한을 훌쩍 넘기게 됩니다. 여기서는 이진 탐색을 사용해야 합니다.
B[k] 라는 것은 k 번째로 작은 수라는 뜻이면서 B[k] 보다 작은 수가 k-1 개 라는 의미입니다.
2차원 배열 A 는 N행이 N의 배수로 구성되어 있습니다. 그러므로 2차원 배열에서의 k번째 수는 k 를 넘지 않습니다.
N 𝘅 N 에서 k 번째 수를 찾을 때 k 번째 수가
- 1 행에 있다면 -> k 번째 수 = k
- 2 행에 있다면 -> 2N > k > N,
k번째 수 = 2(k - N) = 2k - 2N. 2N > k 이므로 2k - 2N < k. ( ∵ 2k - 2N + (2N - k) < k + (2N - k) ↔ k < 2N )
그러므로 k > 2k - 2N. 즉, k번째수 < k
- 3행에 있다면 -> 3N > k > 2N.
k번째 수 = 3(k - 2N) = 3k - 6N. 3N > k 이므로 3k - 6N < k. ( ∵ 3k - 6N + ( 6N - k) < k + ( 6N - k) ↔ 2k < 6N ↔ k < 3N)
그러므로 k > 3k - 6N. 즉, k 번째 수 < k
그러므로 2차원 배열에서 k 번째 수는 k 보다 크지 않다는 것을 알 수 있습니다. ( k 번째 수 < k ).
사실 이런 식으로 수식을 사용하지 않더라고 직관적으로 알 수 있을 것입니다.
그러므로 B[k] 는 2차원 배열에서 1 ~ k 번째 안에 정답이 있다는 것을 의미합니다. 그렇다면 우리는 이진 탐색을 사용할 수 있겠습니다.
이진 탐색으로 중앙값보다 작거나 같은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B[k] 값을 구합니다. 다시 말해서 작거나 같은 수의 개수가 k-1 개인 중앙값이 정답입니다. .
2. 손으로 풀기
문제 분석 단계에서 이진 탐색을 사용하면 될 것 같다고 어렴풋이 분석했습니다. 이제 실제로 어떻게 푸는지는 아래와 같습니다.
①
먼저 문제에서 예제 입력을 N = 3, k = 7 을 예로 들어봅시다.
시작 값은 1 이고 종료 값은 k = 7입니다. 최초 중앙 값은 4가 되겠습니다.
각 행에서 중앙값 4 보다 작거나 같은 값의 개수는 각 행의 첫번째 값을 중앙 인덱스 4로 나눈 몫과 같습니다. 만약 그 몫이 행과 열의 개수 3(입력에서 N) 보다 크다면 그 행의 모든 값이 작은 것이므로 3(입력에서 N) 이 됩니다.
그러므로 중앙값 4보다 작거나 같은 수의 개수는 6개라는 것을 알 수 있습니다. 즉, 중앙값 4는 6번째 수보다 작거나 같다는 것을 알 수 있습니다. 중앙값 4는 6번째 수보다 큰 수가 될 수 없다는 것이지요.
6 < 7(=k)
우리는 7번째 수를 알고 싶으므로 중앙값 4보다 더 큰 범위에서 탐색해야 합니다. 즉, 시작값이 1에서 4 + 1 = 5( = 기존 중앙값 + 1) 이 되어서 5 ~ 7 의 중앙값을 가지고 탐색하면 됩니다.
②
5 ~ 7 의 중앙값은 6입니다.
위에서와 같은 방법으로 계산을 합니다.
이번에는 중앙값 6 보다 작거나 같은 수의 개수는 8개입니다. 즉, 중앙값 6은 8번째 수보다 작거나 같다는 것을 의미합니다.
8 ≥ 7(=k)
이 때 정답에 현재 중앙값 6을 저장해 놓습니다.
그런데 중앙값 6은 이진 탐색을 위해 따로 만든 인덱스 수입니다. 이 수는 2차원 배열 내부에 없을 수도 있습니다. 그리고 종료값을 내려서 중앙값을 더 내렸을 때의 그 중앙값보다 작거나 같은 수가 7인 중앙값이 있을 수 있습니다.
그러므로 시작값(인덱스) > 종료값(인덱스) 가 될 때까지 이진 탐색을 반복하여 정답을 계속 업데이트해 나가야 합니다.
우리는 7번째 수를 알고 싶으므로 중앙값 6보다 더 작은 범위에서 탐색을 지속해봅시다. 종료값이 7에서 6 - 1 = 5(= 중앙값 - 1) 이 됩니다.
5 ~5 에서 탐색을 합니다.
5 ~ 5 의 중앙값은 5입니다.
이번에는 중앙값 5보다 작거나 같은 수의 개수는 6입니다. 중앙값 5는 6번째 수보다 작거나 같다는 것을 의미합니다.
6 < 7(=k)
우리는 7번째 수를 알고 싶으므로 중앙값 5보다 더 작은 범위에서 탐색을 지속해봅시다.
시작값이 5에서 5 + 1 = 6(= 중앙값 + 1) 가 됩니다. 그런데 이 때 시작값이 종료값보다 더 커집니다. 이 경우 이진 탐색을 지속할 수 없으므로 탐색을 종료하고 정답을 출력합니다.
정담은 위에서 저장해 두었던 6 입니다. 그렇게 6이 출력됩니다.
3. 슈도코드
N: 배열 A 크기, k: 몇번째 수가 궁금한지.
sIndex = 1; eIndex = k;
result: 정답 변수
binSearch(sIndex, eIndex)
sout(result)
// 이진 탐색 메소드
binSearch(sIndex, eIndex){
if(sIndex > eIndex){리턴}
else{
int mIndex = (sIndex+eIndex)/2;
for(N만큼){
각 행에서의 mIndex 보다 작거나 같은 수 의 개수(Math.min(N, mIndex/i)를
모두 더해서 cnt 에 저장
}
if(cnt < k){
int sIndex = mIndex + 1;
binSearch(sIndex, eIndex)
}else{ // cnt >= k
result = mIndex;
int eIndex = mIndex-1;
binSearch(sIndex, eIndex)
}
}
}
4. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BaekJun1300Self {
static int N, k;
static int result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
k = Integer.parseInt(br.readLine());
int sIndex = 1;
int eIndex = k;
binSearch(sIndex, eIndex);
System.out.println(result);
}
private static void binSearch(int sIndex, int eIndex) {
if (sIndex > eIndex) {
return;
} else {
int mIndex = (sIndex + eIndex) / 2;
int cnt = 0;
for (int i = 1; i <= N; i++) {
cnt += Math.min(N, mIndex / i);
}
if (cnt < k) {
sIndex = mIndex + 1;
binSearch(sIndex, eIndex);
} else { // cnt >= k
result = mIndex;
eIndex = mIndex - 1;
binSearch(sIndex, eIndex);
}
}
}
}
그런데 백준 1300 번 K 번째 수에 두가지 의문이 있네요..
- cnt>=k 일 때 정답을 업데이트, 이진 탐색 진행하고 cnt<k 일 때 이진탐색만 진행하는 게 아닌 반대로 cnt<=k 일 때 정답을 업데이트, 이진 탐색 진행을 하고 cnt >k 일 때 이진탐색만 하는 것으로 바꾸면 왜 안되는지...
- 애초에 이진탐색에서 mIndex = (sIndex + eIndex)/2 는 2차원 배열 A 와는 관련이 없는 값이어서 mIndex 가 2차원 배열 A 에 있는 값이 아닐 수도 있는데 어떻게 mIndex 가 항상 2차원 배열 A 에 있는 값이 될 수 있는지
이 부분 혹시 아시는 분 있으면 댓글 남겨주시면 감사하겠습니다....
'Java > 코딩테스트' 카테고리의 다른 글
| 그리디(Greedy) 자바 백준 1931, 1541 (0) | 2023.07.21 |
|---|---|
| 그리디(Greedy) 자바 백준 11047, 1715, 1744 (0) | 2023.07.20 |
| BFS(너비 우선 탐색) 자바 백준 1260, 2178, 1167 (0) | 2023.07.18 |
| DFS(깊이 우선 탐색) 자바 백준 11724, 2023, 13023 (0) | 2023.07.17 |
| 버블 정렬 - 자바 백준 수 정렬하기: 2750, 버블 소트: 1377 (0) | 2023.06.01 |