오늘의 학습 내용
- 이분탐색
- 시간 초과
공부한 내용
이분 탐색(또는 이진 탐색)은 정렬된 배열이나 리스트에서 특정한 값을 효율적으로 찾는 알고리즘이다탐색은 분할 정복(divide and conquer) 방법을 사용하여 검색 범위를 반씩 줄여 나가는 방식으로 동작한다. 이 알고리즘은 O(log n)의 시간 복잡도를 가지며, 매우 큰 데이터 세트에서도 빠르게 검색을 수행할 수 있다.
초기 설정: 검색할 배열이나 리스트는 정렬되어 있어야 합니다. 배열의 처음과 끝 인덱스를 설정
반복 과정:
배열의 중간 인덱스를 계산한다.
중간 값과 찾고자 하는 값을 비교한다.
찾고자 하는 값이 중간 값과 같으면 검색이 완료된다.
찾고자 하는 값이 중간 값보다 작으면 검색 범위를 중간 값의 왼쪽 절반으로 좁힌다.
찾고자 하는 값이 중간 값보다 크면 검색 범위를 중간 값의 오른쪽 절반으로 좁힌다.
종료 조건: 검색 범위가 더 이상 존재하지 않으면(즉, 시작 인덱스가 끝 인덱스를 초과하면) 찾고자 하는 값이 배열에 없다는 의미다.
오늘의 회고
첫번째 시도에서는 이중 for 문을 돌아가면서 cards배열에 test배열이 있으면 1을 반환하게끔 구현하였다. 그러나 시간초과가 발생했다. 해당 코드는 O(n^2) 이라서 좀더 적은 복잡도를 가질 수 있는 방법을 구상하다가 생각해낸 방식은 이분탐색방식이었다.
두번째 시도에서는 이분탐색을 이용했는데 재귀함수 내에서 while문을 가지지만 이는 O(log n)의 복잡도를 가져 첫번째 시도보다 현저히 빠른 속도를 가진다고 할 수 있겠다. 첫번째 시도와 유사하게 test 배열을 순회하면서 test의 값이 정렬된 cards의 low와 high를 비교하면서 존재하는지 여부를 판단한다.
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다
내풀이
1) 시간초과
package baekjoon.이분탐색;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class 숫자_카드 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 상근이가 가지고있는 카드 개수
int[] cards = new int[N];
StringTokenizer 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[] test = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++){
test[i] = Integer.parseInt(st.nextToken());
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<M; i++){
boolean answer = false;
for(int j=0; j<N; j++){
if(test[i] == cards[j]){
answer = true;
break;
}
}
if(answer == true){
sb.append(1).append(" ");
}else{
sb.append(0).append(" ");
}
}
System.out.print(sb);
}
}
2) 이분탐색
- 두번째 시도에서
binarySearch(test[i], 0, N)이라고 처음에 구현했더니 IndexOutOfRange 에러가 발생했다. 해당 이분탐색에서 low와 high는 test의 인덱스범위를 의미하기 때문에 0부터 N-1로 두면 해결할 수 있다.
package baekjoon.이분탐색;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 숫자_카드 {
static int[] cards, test;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 상근이가 가지고있는 카드 개수
cards = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
cards[i] = Integer.parseInt(st.nextToken());
}
int M = Integer.parseInt(br.readLine()); // 테스트 카드 개수
test = new int[M];
st = new StringTokenizer(br.readLine());
for(int i=0; i<M; i++){
test[i] = Integer.parseInt(st.nextToken());
}
StringBuilder sb = new StringBuilder();
Arrays.sort(cards);
for(int i=0; i<M; i++){
sb.append(binarySearch(test[i], 0, N-1)).append(" ");
}
System.out.print(sb);
}
public static int binarySearch(int key, int low, int high){
int mid;
while(low <= high){
mid = (low + high) / 2;
if(key == cards[mid]){
return 1;
}else if(key < cards[mid]){
high = mid-1;
}else {
low = mid+1;
}
}
return 0;
}
}
