백준 알고리즘 1920번 이분탐색 수 찾기 자바 JAVA

 

 

 

백준 알고리즘 1920번 수찾기 문제는 이분탐색 알고리즘을 사용해서 문제를 풀어야 한다. 이분탐색이란 검색 대상이 되는 데이터들을 절반씩 나누어 가면서 검색하는 탐색알고리즘이다.

 

참고로 탐색 알고리즘에는 크게 6가지 종류의 알고리즘이 있다.

선형탐색	검색 대상 데이터를 처음 부터 순차적으로 비교해서 검색하는 탐색 알고리즘
이분(이진)탐색	검색 대상 데이터를 절반씩 나눠가며 탐색하는 알고리즘
보간 탐색	찾을 값의 위치값을 예상해서 검색하는 사전형식의 탐색 알고리즘
블록 탐색	대량의 데이터를 그룹별로 블록화해서 인덱싱을 통해 검색하는 알고리즘
이진 트리 탐색	검색 대상 데이터를 이진 트리로 변경하여 검색하는 탐색 알고리즘
해싱 탐색	해싱 함수를 통해 데이터를 검색하는 알고리즘

 

선형탐색(Linear Search) 알고리즘 적용

 

백준 알고리즘 1920번을 순차탐색 알고리즘을 사용해서 먼저 풀어봤다. N과 M값을 입력받아서 for 문으로 입력데이터들을 순회하면서 하나씩 비교하는 간단한 알고리즘이다. 선형탐색(Linear Search) 알고리즘은 데이터가 정렬되어 있지 않거나 데이터의 수를 알지 못해도 풀수 있다는 장점이 있다. 데이터 수가 적어서 복잡한 알고리즘을 사용해 얻는 이득이 크지 않을 때 사용하는 알고리즘이다.

 

선형탐색(Linear Search) 알고리즘의 시간복잡도는 N(n)이다. 즉 입력값에 따라서 점진적으로 연산횟수가 증가하는 알고리즘이다. n개의 데이터를 가진 자료구조의 평균 비교횟수는 (n+1)/2이다.

 

import java.util.Scanner;

/*
    Owner : Developer Blog
    Title : 백준 알고리즘 1920 수 찾기
    Algorithm : 순차탐색
*/

public class A_1920 {
    public static int arr[];
    public static StringBuilder sb = new StringBuilder();
    public static int result;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]=in.nextInt();
        }
        int M = in.nextInt();
        for(int i=0; i<M; i++){
            int finderValue = in.nextInt();
            result=0;
            for(int num:arr){
                if(num==finderValue){
                    result++; 
                }else{
                    continue;
                }
            }
            sb.append(result+"\n");
        }
        System.out.println(sb); 
    }
}

백준 알고리즘의 가장 큰 벽은 시간초과 발생이다. 백준 알고리즘 1920번의 경우 메모리 제한 128MB, 시간제한 1초다. 순차 탐색 알고리즘을 적용해서 검색시 바로 시간초과가 발생한다.

 

 

이분탐색(이진탐색) 알고리즘(Binary Search Algorithm)

이분탐색은 대상 데이터를 절반씩 쪼개가면서 검색하는 알고리즘이다. 절반으로 나누기 때문에 반드시 선제조건으로 입력되는 데이터의 갯수를 알고 있어야 한다. 나눠진 데이터 그룹을 선택하는 기준의 값은 대소관계다. 반드시 정렬작업이 선행되어야 한다. 

 

이분탐색의 시간복잡도는 O(logn)이다. 데이터를 처리하는 연산횟수가 특정 요인에 의해서 줄어드는 폭이 점점 커지는 로그의 형태를 가진다. 

 

이분탐색 알고리즘 과정

1. 데이터 정렬(오름차순 || 내림차순 상관없음)
2. 시작위치와 끝위치를 통해 중간위치 계산  
   
   
3. 중간위치의 값과 찾을 값을 비교해서 이분된 영역 중 하나를 선택한다.
   ♠ 오름차순 데이터에서 특정 데이터가 찾을 값보다 작다면 오른쪽 영역에 존재함, 현재 시작위치를 중간 위치로 변경
   ♠ 오름차순 데이터에서 특정 데이터가 찾을 값보다 크다면 왼쪽 영역에 존재함. 현재 끝 위치를 중간 위치로 변경
   ♠ 변경된 시작과 끝값을 기반으로 새로운 중간 위치를 계산. 중간 위치값이 실수인 경우는 소수점 버림한다.
   
   
4. 값을 찾거나 혹은 못찾는 경우 탐색을 종료한다.
   ♠ 중간 값을 찾게 되면 검색된 위치를 반환함
   ♠ 시작위치와 끝 위치 값이 같아지면 찾는 데이터가 없다는 뜻으로 프로그램 종료.

JAVA 코드(해결)

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

/*
    Owner : Developer Blog
    Title : 이분탐색 수 찾기
    Algorithm : 이분탐색 알고리즘
*/

public class A_1920 {
    public static int arr[];
    public static StringBuilder sb = new StringBuilder();
    public static int startPoint;
    public static int endPoint;

    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        
        // 입력값의 갯수를 입력받음
        arr = new int[N];

        // 입력 데이터를 배열에 추가함
        for(int i=0; i<N; i++){
            arr[i]=in.nextInt();
        }

        // 배열값을 정렬함
        Arrays.sort(arr);
        
        // 찾을 데이터의 갯수를 입력받음
        int M = in.nextInt();
        
        // 이분탐색 알고리즘 시작
        for(int i=0; i<M; i++){
            if(binarySearch(0, arr.length-1, in.nextInt())>=0){
                sb.append(1+"\n");
            }else{
                sb.append(0+"\n");
            }
        }
        //
        System.out.println("\n=======================\n"+sb);
        
    }
    public static int binarySearch(int start, int end, int findValue){
        try{
            while(start<=end){
                int midPoint=(int)Math.floor((start+end)/2);
                if(arr[midPoint] > findValue){
                    end=midPoint-1;
                }
                else if(arr[midPoint] < findValue){
                    start=midPoint+1;
                }
                else{
                    return 1;
                }
            }
        }catch(Exception e){
            e.getMessage();
        }
        return -1;
        
    }
}

이분탐색 알고리즘으로 코드 길이는 더 길어졌지만, 1320ms 시간으로 해결이다.