BOJ 1920
위 문제는 백준 사이트의 알고리즘 1920 문제에 관한 설명입니다.
BOJ 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을 출력한다.
package baekjoon;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] array = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
array[i] = Integer.parseInt(st.nextToken());
}
int M = Integer.parseInt(br.readLine());
for (int i = 0; i < M; i++) {
}
Arrays.sort(array);
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
System.out.println(binarySearch(Integer.parseInt(st.nextToken()), array));
}
}
public static int binarySearch(int number, int[] array)
{
int first =0;
int last =array.length-1;
int mid = 0;
while(first <= last)
{
mid = (first+last)/2;
if(number == array[mid]) return 1;
else if(number < array[mid])
last = mid-1;
else first = mid+1;
}
return 0;
}
}
이번 문제의 해결법은 이진탐색을 이용해서 풀었습니다.
일단 선형탐색에 대해서 알아 봅시다.
선형탐색이란?
선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의
처음 인덱스 번째부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다.
장점
- 데이터를 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편
단점
-
데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고,
-
하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있습니다.
예시를 통해 간단한 구현을 해봅시다.
import java.util.Scanner;
public class LinearSearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int number = scanner.nextInt();
int[] array = {3,2,6,4,9,7};
int result = linearSearch(number, array);
if(result == -1)
{
System.out.println("없어요.");
}
else
{
System.out.println(result);
}
}
public static int linearSearch(int number, int[]array){
for(int i =0 ; i <array.length;i++)
{
if(number ==array[i]) return array[i];
}
return -1;
}
}
위의 예시와 처럼 for문과 같은 반복문을 이용해서 구현할 수 있습니다.
그렇지만 만약 찾고자 하는 배열의 길이가 무척이나 길고 심지어 맨 뒤에 있다면?
엄청 오래걸리는게 당연합니다!
이 때 이진 탐색을 사용하면 훨~씬 짧은 시간에 탐색이 가능합니다.
이진탐색이란?
선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘 이지만 이진검색은 중간값부터 탐색을 합니다
선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다.
장점
- 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다
단점
- 데이터의 집합이 반드시 정렬(Sort)되어야 한다
예시를 통해 간단한 구현을 해봅시다.
import java.util.Arrays;
import java.util.Scanner;
public class BinarySearch{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int []array = {1,4,3,2,5,6};
Arrays.sort(array);
int number =scanner.nextInt();
int result = binarySearch(number,array);
if(result == -1)
{
System.out.println("없어요.");
}
else
{
System.out.println(result);
}
}
public static int binarySearch(int number, int[] array)
{
int first =0;
int last =array.length-1;
int mid = 0;
while(first <= last)
{
mid = (first+last)/2;
if(number == array[mid]) return array[mid];
else if(number < array[mid])
last = mid-1;
else first = mid+1;
}
return -1;
}
}
이진 탐색은 정렬이 우선적으로 필요합니다.
이후 원하는 값이 배열 또는 리스트 등등에 있는지를 찾고 싶다면
가운데 있는 값을 기준으로 큰지, 작은지를 확인합니다.
작다면? 왼쪽을 기준으로 다시 중앙값을 구하고 위 과정을 반복
크다면? 오른쪽을 기준으로 다시 중앙값을 구하고 위 과정을 반복
그렇기 때문에 넓은 범위에서 정보를 찾을 때,
선형탐색보다 훨씬 더 적은 연산으로 원하는 결과를 얻을 수 있습니다.
참고로 시간복잡도는 log2n입니다!
그래서 이번 문제의 해결은??
선형 탐색을 사용하면 시간초과가 나올 것 입니다.
이진 탐색을 사용한다면 그것보다 빠른시간안에 찾을 수 있기에 만약 배열에서 탐색이 된다면 1을, 없다면 0을 리턴시켜서 출력시킵니다.
다소 불친절한 설명이지만.. 제가 자료구조 공부하면서 만들었던 저장소 링크도 남깁니다.
잘못된 정보가 있다면 댓글 부탁드립니다.