[백준] 1920번 : 수 찾기 - JAVA [자바] 이분 탐색 문제

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

1920번: 수 찾기

 

 

 

 

 

 

 

 

---

• 문제

 

 

 

 

 

 

 

 

새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다.

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

 

일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자.

 

이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고, 그렇지 않다면 부분문제를 다시 나누어 위 과정을 재귀적으로 반복하여 문제를 풀이하는 것이었다.

 

예로들어 색종이 만들기 문제나, 쿼드 트리 같은 문제처럼 이미지를 4등분으로 분할해나가면서 문제를 풀 수도 있고, 곱셈 문제나 행렬 곱셈 문제처럼 어떤 수학적 법칙을 이용하여 부분문제로 분할해나가며 결과적으로 전체에 대한 답을 얻을 수 있었다.

 

이분 탐색은 그럼 무엇일까?

 

단어 그대로 해석해보면 이렇다. '이분'은 한자로 보면 二分 으로 두 개로 나눈다는 의미고, '탐색'은 말 그대로 어떤 것을 찾겠다는 것이다. 즉, 좀 더 자연스럽게 말하자면 두 부분으로 쪼개면서 탐색하겠다는 의미다.

 

여기서 중요한 포인트가 있다. 기본적으로 '탐색' 이라는 것이다.

분할정복은 어떤 전체 문제를 해결하기 위해 부분적으로 나눠들어가면서 분할하여 부분 문제를 해결하는 방식이라면, 이분탐색은 위 메커니즘과 유사하게 두 부분으로 나누어 들어가긴 하지만, 특정 값 또는 자료를 찾는 '탐색'이라는 것이다.

 

 

 

참고로 이분 탐색을 이진 탐색이라고도 하는데 나눌 분(分) 대신 나아갈 진(進)이라 두 단어 모두 의미상 큰 차이는 없다.

binary 라는 단어 자체가 공학적으로는 0과 1을 의미하기도 하지만, 두 부분 이라는 의미도 되기 때문에 이분 탐색, 이진 탐색 모두 맞는 말이다.

 

 

아직까지는 이분 탐색이라는 것이 잘 감이 안 올 것이다.

 

가장 쉽게 이해할 수 있는 예시로 Up & Down 게임을 떠올리면 된다.

1 ~ 100 까지 수 중 상대 방이 17로 정했다고 가정할 때, 우리는 수를 맞추기 위해 보통 어디서부터 시작하는가?

100의 절반인 50일 것이다.

 

그리고 상대가 다운(down)이라 하면, 그 다음으로 절반인 25인지를 물을 것이다. 그리고는 12, 그 다음으로는 12와 24의 중간인 18... 이런식으로, 즉 50 → 25 → 12 → 18 .. 이렇게 반으로 쪼개가면서 수를 찾는 방식이라는 것이다.

 

이런 식으로 구간 내 절반을 잘라가면서 값을 찾아나가는게 기본적인 이분 탐색 원리다.

 

이 문제에서의 포인트는 '수가 존재하는지'만 알아내면 되기 때문에 중복 원소에 대한 고려는 하지 않고 구현을 하겠다. (중복원소가 있을 때 크게 가장 왼쪽의 원소의 위치를 반환하는 방법과, 가장 오른쪽 원소의 위치를 반환하는 방법이 있는데, 이는 다음 문제에서 다루도록 하겠다.)

 

 

 

이 번 문제를 보면 결국 처음 배열이 주어지고 그 다음에 각 값이 처음 주어진 배열에 존재하는지를 묻는 것이다.

그럼 임의의 배열이 주어질 때 우리가 찾고자 하는 값을 key라고 하고 이분 탐색은 어떻게 이루어지는지 한 번 보자.

 

 

우리가 만약 찾으려는 값(key)가 7이라면, 위와 같이 진행된다. 이 때 주황색 칸은 탐색 범위를 의미한다. 이 때 이분 탐색을 하기 위해서는 배열이 반드시 정렬 되어있어야 한다. 이 부분은 꼭 주의하시기 바란다.

 

 

기본적인 메커니즘은 아래와 같다.

 

1. 탐색 범위내의 배열의 중간인덱스를 구한다. 

2. 중간 인덱스의 값과 key값을 비교한다.

3. 값이 중간 값보다 작다면 왼쪽 부분을, 값이 중간 보다 크다면 오른쪽 부분을 탐색하고, 같다면 해당 인덱스를 반환하고 종료한다. 

 

 

 

위 3가지 과정을 반복하다보면 결과적으로 두 가지 경우의 수가 나온다.

- 찾으려는 값을 찾았을 경우

- 찾으려는 값이 없을 경우

 

찾으려는 값이 있을 경우, 즉 위 처럼 7이라는 값이 배열에 있을 경우에는 그대로 index 3이 반환 되겠지만, 찾으려는 값이 없는 경우도 있다.

 

쉽게 예를 들어 8을 찾는다고 해보자.

그러면 위 이미지처럼 맨 마지막 과정까지는 똑같이 거칠 것이다. 위 이미지를 보면 언젠가는 탐색 범위가 한 개인 경우가 있다는 것을 볼 수 있다. 근데 한 개의 인덱스에 있는 값이 찾으려는 값인 8과 동일하지 않기 때문에 이분탐색을 더 해나아가야 하나, 그 이후에는 더이상 탐색 할 수 있는 곳이 없기 때문에 그대로 끝나고 말 것이다.

 

쉽게 말해 탐색 범위의 왼쪽 끝과 오른쪽 끝이 같은 경우까지 탐색을 했는데 그 값이 key값과 같지 않을 경우 해당 배열에는 key값이 존재하지 않는다는 의미다.

보통은 해당 값을 못찾을 경우 음수를 반환하거나(Java의 Arrays.binarySearch 방식), 혹은 key값에 가장 근접한 인덱스를 반환한다. (흔히 c++의 upper_bound, lower_bound의 방식)

 

 

여기서는 값의 존재 유무를 판별하면 되기 때문에 음수로 반환하는 것이 현명할 것이다. 

 

 

그러면 시간 복잡도는 어떻게 될까? 알고리즘 많이 풀어보신 분이라면 바로 감이 오시겠지만, 이러한 이진 트리 형태의 경우는 거의 대다수가 O(logN) 의 시간 복잡도를 갖는다.

 

 

간단하게 증명해보자면, 다음과 같다.

N개의 요소를 갖고있는 리스트가 주어졌다고 해보자. 그리고 우리가 이분 탐색에서 N/2 씩 쪼개가면서 탐색을 한다.

 

 

즉, 다음과 같다.

 

 

 

즉, K번 반복한다고 할 때, (1/2)K * N 이 된다는 의미다.

이 때, 위 이미지에서 보면 결국 최악의 경우인 마지막 탐색 범위가 1인 경우가 있을 것이다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국 K만큼 반복한다고 했으니 K에 대해 풀어보면 다음과 같다.

 

 

 

즉, N개의 리스트에서 어떤 수를 찾는 과정에 대한 시간 복잡도는 O(logN)이라는 것이다.

 

 

그럼 시간 복잡도도 알아보았으니 한 번 위를 토대로 작성을 하나씩 해보자. 

일단, '정렬 된 배열'이 들어온다는 가정하에, 파라미터로 배열과 찾으려는 값인 key 변수가 들어온다고 해보자.

 

그럼 기본적으로 세팅해야 할 변수들은 다음과 같다.

 

/**
* @param arr 정렬 된 배열
* @param key 찾으려는 값
* @return key와 일치하는 배열의 인덱스
*/
public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

}

 

 

우리가 이분 탐색 과정을 거치기 위해서는 탐색 범위를 알아야 할 것이다. 그렇기 때문에 탐색 범위의 왼쪽 끝을 가리키는 변수와 오른쪽 끝을 가리키는 변수가 필요하다. 이를 각각 lo, hi로 둘 것이다.

이 때 당연하지만, 초기값으로는 초기 탐색 볌위가 0 ~ 배열의 끝이므로 lo = 0, hi = arr.length - 1 이 될 것이다.

 

 

그 다음으로 무엇을 해야할까?

바로 탐색 과정을 반복 하기 때문에 반복문부터 작성을 해주어야 할 것이다. 음.. 반복 조건을 어떻게 알죠?

이 부분은 이미 앞서 힌트를 주었다.

 

바로 위에서 언급 했던 "탐색 범위의 왼쪽 끝과 오른쪽 끝이 같은 경우까지 탐색을 했는데 그 값이 key값 ...." 이 문장이다.

핵심이 왼쪽 끝과 오른쪽 끝이 같은 경우까지 탐색이라는 것이다.

 

우리가 위에서 변수로 lo와 hi로 탐색 범위를 가리키는 변수를 두었다. 탐색 범위가 오른쪽 끝과 왼쪽 끝이 같을 때 까지 탐색한다고 하면 언제까지 반복인 것일까?

바로 lo가 hi보다 커질 때다. 즉, lo > hi 이라면 더이상 반복하지 않는다는 것이다.

 

즉 아래처럼 반복문 틀을 작성할 수 있다.

 

public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

}
}

 

 

 

 

그럼 이제 반복문 내에 탐색과정을 본격적으로 구현해보자.

일단, 우리가 이분 탐색에서 크게 보자면 세 가지 과정을 거쳤다.

 

1. 중간 인덱스를 구한다.

2. 중간값과 key값을 비교한다.

3. 비교값에 따라 범위를 왼쪽, 오른쪽 혹은 값이 같은 경우는 해당 인덱스를 반환한다.

 

이를 코드로 작성해보면 다음과 같다.

 

public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

int mid = (lo + hi) / 2; // 중간위치를 구한다.

// key값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]) {

}
// key값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]) {

}
// key값과 중간 위치의 값이 같을 경우
else {

}
}
}

 

 

 

 

위 처럼 세 가지 경우의 수가 나뉠 것이고, 해당 경우에 따라 위치를 재조정해주어야 할 것이다.

 

 

하나씩 살펴보자.

key < arr[mid] 일 경우는 어떻게 될까?

 

이는 key값(찾으려는 값)이 배열의 중간(mid)위치보다 왼쪽에 있다는 의미일 것이다. 즉, 탐색 범위의 오른쪽 끝을 가리키는 hi가 재조정되어야 한다는 의미다.

그러면 어떤 값으로 재조정 되는지를 생각해본다면, 결국 우리가 찾으려는 key는 lo~mid 사이에 있다는 의미다. 이 때, arr[mid]는 이미 비교작업을 했으니 mid(중간)을 제외한 왼쪽 부분을 탐색 범위로 보면 된다.

 

(예로들어 Up & Down 게임에서 1~100의 범위에서 50을 외쳤는데 Down이라면, 그 다음에는 50을 제외한 1~49 사이의 수가 탐색 범위인 것과 같은 의미다.)

 

즉, hi = mid - 1 이 재조정 된 값이 되는 것이다.

 

 

 

 

그 다음으로 key > arr[mid] 일 경우에는 어떻게 될까?

 

이는 위와 반대로 key값(찾으려는 값)이 배열의 중간(mid)위치보다 오른쪽에 있다는 의미일 것이다. 즉, 탐색 범위의 왼쪽 끝을 가리키는 lo가 재조정되어야 한다는 의미다.

 

즉, 재조정 되는 lo의 값은 lo = mid + 1 이 되는 것이다.

 

 

 

 

마지막으로 위 조건 모두 만족하지 않은 경우, 즉 key == arr[mid] 일 경우에는 이미 찾고자하는 값을 찾았으므로 mid 를 반환하면 된다.

 

 

자, 그러면 위 3가지 경우를 채워넣으면 다음과 같이 될 것이다.

 

public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

int mid = (lo + hi) / 2; // 중간위치를 구한다.

// key값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]) {
hi = mid - 1;
}
// key값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]) {
lo = mid + 1;
}
// key값과 중간 위치의 값이 같을 경우
else {
return mid;
}
}
}

 

 

 

 

그리고, while(lo <= hi) 안에서 반환값(return mid)이 없다면, 즉 while문이 종료되었다는 것은 찾고자 하는 값이 없는 것이라고 했다.

이 때는 앞서 말했듯 근사값의 인덱스를 반환하거나, 음수를 반환한다고 했고, 여기서는 음수를 반환해주기로 했다.

 

 

즉, 최종적으로 코드를 작성하면 다음과 같다.

 

public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

int mid = (lo + hi) / 2; // 중간위치를 구한다.

// key값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]) {
hi = mid - 1;
}
// key값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]) {
lo = mid + 1;
}
// key값과 중간 위치의 값이 같을 경우
else {
return mid;
}
}

// 찾고자 하는 값이 존재하지 않을 경우
return -1;

}

 

 

 

 

 

위와 같이 이분 탐색을 구현해보았다.

사실 잠깐 언급했지만, 자바에서는 Arrays 클래스에 binarySearch 메소드를 제공하고 있다. (위와 거의 유사한 방식이다.)

차이점이라면 음수값을 기존 리스트에서 어느 값 사이에 있는지를 알 수 있는 방식으로 반환을 한다는 점이다. (참고로 -1을 반환 해주어도 이 번 문제에서는 무방하다)

자바에서는 음수 값을 -(low + 1) 으로 반환하는데, 이는 해당 값이 어디 위치에 가까운지를 알 수 있기 때문이다.

 

예로들어 리스트 {2, 4, 7, 8} 이 있고, 리스트에서 3을 찾고자 한다면 해당 리스트에는 3이 없기 때문에 음수를 반환할 것이다. 이 때, 3은 2와 4 사이에 있었으므로 -2를 반환한다.

 

무슨 말인가 하면 이렇다.

 

우리가 음수 0, 즉 -0은 구분하고 있지 않기 때문에 A0 보다 작은 값일 경우 -1 index이 되는 것이다. 즉, -1부터 시작하여 감소하는 방향인 것이다.

그렇기 때문에 low 에 1을 더한 뒤 음수를 취하는 이유가 위와 같은 이유 때문이다.

 

다시 앞선 예시를 보자.

{2, 4, 7, 8} 이 있다. 그리고 3을 찾고자 한다면 index[0] < 3 < index[1] 사이에 위치한다. 그러면 위 규칙에 따라 음수값으로 표현하게 된다면 -2를 반환 하게 된다.

 

 

일단은 이 정도로만 알아두면 될 것 같다.

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

이 번 문제는 위에서 설명한 이분 탐색 알고리즘을 그대로 이용하여 입력 방식을 바꾸어 테스트해보겠다. 단, 출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하고자 한다.

 

그리고 마지막으로 Arrays.binarySearch() 메소드 사용 방법도 추가해놓도록 하겠다.

 

 

 

1. Scanner

2. BufferedReader

3. BufferedReader + Arrays.binarySerach()

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner]

 

import java.util.Scanner;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int N = in.nextInt();
int[] arr = new int[N];


for(int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}


// 배열은 반드시 정렬되어있어야한다.
Arrays.sort(arr);

int M = in.nextInt();


StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {

// 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
if(binarySearch(arr, in.nextInt()) >= 0) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
}
System.out.println(sb);
}


/**
* @param arr 정렬 된 배열
* @param key 찾으려는 값
* @return key와 일치하는 배열의 인덱스
*/
public static int binarySearch(int[] arr, int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

int mid = (lo + hi) / 2; // 중간위치를 구한다.

// key값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]) {
hi = mid - 1;
}
// key값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]) {
lo = mid + 1;
}
// key값과 중간 위치의 값이 같을 경우
else {
return mid;
}
}

// 찾고자 하는 값이 존재하지 않을 경우
return -1;

}
}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

알고리즘도 설명한 방식 그대로 갖고왔다. 

 

 

 

---

- 방법 2 : [BufferedReader]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

 

또한 구조를 조금 변경했다. 위 문제를 보면 하나의 리스트에 대해서만 이분 탐색을 하기 떄문에 우리가 굳이 매 번 파라미터로 배열을 넘겨 줄 필요가 없다. 즉, 전역변수로 두는 것이다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static int[] arr;

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());
arr = new int[N];

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


// 배열은 반드시 정렬되어있어야한다.
Arrays.sort(arr);

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

st = new StringTokenizer(br.readLine(), " ");

StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {

// 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
if(binarySearch(Integer.parseInt(st.nextToken())) >= 0) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
}
System.out.println(sb);
}


/**
* @param key 찾으려는 값
* @return key와 일치하는 배열의 인덱스
*/
public static int binarySearch(int key) {

int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

// lo가 hi보다 커지기 전까지 반복한다.
while(lo <= hi) {

int mid = (lo + hi) / 2; // 중간위치를 구한다.

// key값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]) {
hi = mid - 1;
}
// key값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]) {
lo = mid + 1;
}
// key값과 중간 위치의 값이 같을 경우
else {
return mid;
}
}

// 찾고자 하는 값이 존재하지 않을 경우
return -1;

}
}

 

 

 

크게 어려울 것은 없을 것이다. 

만약 여러분이 조금 더 성능을 높이고자 한다면, 중간 위치를 구하는 (lo + hi) / 2 에서 2를 나누는 방식을 비트 시프트를 이용한 방식으로 변경해도 좋다.

 

즉, int mid = (lo + hi) >>> 1;  이런식으로 바꾸면 조금 더 좋은 성능이 나올 수 있을 것이다.

 

(참고로 >> 와 >>> 의 차이는 비트를 밀어낼 때 비게 되는 비트를 정수 값의 최상위 비트로 채우느냐, 0으로 채우느냐의 차이다. 우리는 0으로 채워야 하기 때문에 >>> 을 써야한다.)

 

 

 

 

 

 

 

---

- 방법 3 : [BufferedReader + Arrays.binarySearch()]

 

 

 

 

 

가장 간단한 방법이다.

Arrays 클래스의 binarySearch 메소드를 활용하는 방법이다.

 

API문서는 아래 링크로 두겠다.

 

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#binarySearch-int:A-int-

Arrays (Java Platform SE 8 )

 

 

메소드를 보면 binaraySearch(int[] a, int key); 로 주어지는데, 앞서 우리가 알고리즘 구현한 것과 동일한 파라미터다. a는 배열이고, key는 찾고자 하는 값이다.

 

이를 이용하면 좀 더 코드가 짧아질 것이다.

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

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];

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


// 배열은 반드시 정렬되어있어야한다.
Arrays.sort(arr);

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

st = new StringTokenizer(br.readLine(), " ");

StringBuilder sb = new StringBuilder();
for(int i = 0; i < M; i++) {

// 찾고자 하는 값이 있을 경우 1, 없을 경우 0을 출력해야한다.
if(Arrays.binarySearch(arr, Integer.parseInt(st.nextToken())) >= 0) {
sb.append(1).append('\n');
}
else {
sb.append(0).append('\n');
}
}
System.out.println(sb);
}


}

 

 

 

기존에 있는 메소드를 사용하기만 하면 되기 때문에 가장 간편한 방법이 될 수는 있겠으나.. 사실 위와 같은 풀이 방법은 별로 추천드리지는 않는다.

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 31092349  -  방법 3 : BufferedReader + Arrays.binarySearch()

채점 번호 : 31092345  -  방법 2 : BufferedReader

채점 번호 : 31092339  -  방법 1 : Scanner

 

 

 

알고리즘은 거의 같은 알고리즘이라 사실 알고리즘 자체의 성능을 평가한다기보단 입력의 성능을 보여주는 것이다. 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

 

 

해당 글은 https://st-lab.tistory.com/261 에서 발췌하였습니다.