탐색 : 이진탐색 이론과 문제

I. 탐색

탐색이란 '주어진 데이터'에서 '자신이 원하는 데이터'를 찾아내는 알고리즘이다.

탐색은 주어진 데이터의 성질(정렬, 비정렬 데이터)따라 탐색알고리즘을 채택하는것이 중요하다

탐색은 그래프를 탐색하기 때문에 선수공부로서 그래프 표현에 대해서 공부가 필요하다

 

II. 이진탐색 이론

1.  들어가며

(1) 정의

1)

이진탐색이란 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다

 

데이터 정렬

-> 데이터의 중간값에서 찾고자 하는 값 비교

-> 데이터 크기 반으로 줄이기

 

2) 특징

타깃 데이터 탐색

 

3) 시간복잡도 

O(log N) 의 시간복잡도를 가진다.

 

 

4) 응용문제

 

 

(2) 핵심이론

오름차순으로 정렬된 데이터를 이용한다. (내림차순이면 조건을 반대로 한다)

 

N개의 데이터에 대해서 O(nog N)번의 연산으로 원하는 데이터 찾을 수 있다.

16개의 데이터 중 찾고자 하면 4번만에 찾을 수 있다.

다만 꼭 정렬 될것

 

(3) Logic (이진탐색 과정)

1) 

현재 데이터의 중앙값을 선택한다 (중앙값은 소숫점이 나올시 내림으로 한다)

 

2)

a. 중앙값 > 타깃데이터 경우

중앙값 기준으로 왼쪽 데이터 셋 선택 (end 가 중앙값으로)

 

b. 중앙값 < 타깃데이터 경우

중앙값 기준으로 오른쪽 데이터 셋 선택 (start 가 중앙값으로)

 

3) 반복

반복 중

 

a. 중앙값 == 타깃데이터 경우 탐색종료

b. start 가 end 보다 크거나 같을 때 찾지못하고 탐색종료

 

 

II. 이진탐색(bianry serach) - 문제 1

[ 백준 1920 ]

1. 문제설명

2. 문제풀이

(1) 문제분석

• 반드시 정렬을 먼저 해야한다 자바의 기본 정렬함수 O(n log n) 이므로 제한시간초과 되지 않는다.

(2) 손으로 풀기

- 블로그에서 생략

(3) 슈도코드 코드 작성

- 블로그에서 생략

(4) 코드 구현 

1)

package datastructrue5;

import  java.util.*;
import  java.io.*;
public class P1920 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int  N = Integer.parseInt(st.nextToken());

        int A[] = new int[N];

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

        //정렬
        Arrays.sort(A);

        st = new StringTokenizer(br.readLine());
        int  M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < M ; i++){
            int target = Integer.parseInt(st.nextToken());
            boolean find = false;

            //시작 끝 인덱스 지정
            int start = 0;
            int end = A.length - 1;

            // start 가 end를 넘어선 순간 끝!
            while (start <= end) {
                //중간값 인덱스 잡기
                int median = (start + end) / 2;
                //중간값
                int mid = A[median];

                //중간값 보다 작을 때
                if (mid > target){
                    //끝점 줄이기
                    end = mid - 1 ;
                }
                //중간값 보다 클 때
                else if (mid < target) {
                    //시작점 줄이기
                    start = mid + 1;
                }
                //둘다 아니면 같은 경우
                else {
                    //찾음 끝
                    find = true;
                    break;
                }
            }
            //찾았을 때 1 출력
            if(find){
                System.out.println(1);
            } else {
                System.out.println(0);
            }

        }
    }
}

 

2)

이진탐색 함수를 이용한 구현 -> 시간초과

이진탐색 함수 구현을 보면 반복문을 마찬가지로 이용함

 

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


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

        //0. 기본
//        버퍼입력받고, 토큰 나누기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st  = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        //1. 데이터 개수 입력만큼 배열선언
        int [] A = new int[N + 1];
        //1-1. 배열에다가 각 값을 대입
        st  = new StringTokenizer(br.readLine());
        for(int i = 1 ; i < N + 1 ; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

//        for(int i = 1 ; i < N + 1 ; i++){
//            System.out.print(A[i]);
//        }
//        System.out.println();
        //1-2 대입한 배열을 정렬하기
        for(int i = 1 ; i < N + 1 ; i++){
            Arrays.sort(A);
        }
//        for(int i = 1 ; i < N + 1 ; i++){
//            System.out.print(A[i]);
//        }
//        System.out.println();

        //2. 데이터 개수만큼 배열선언
        st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        //2-2 각 값에 대해서 탐색 실시
        for (int i = 1 ; i < M + 1 ; i++) {
            int a = Arrays.binarySearch(A, Integer.parseInt(st.nextToken()));

            //2-3 탐색을 하면 그 결과값을 1 출력
            if(a < 0){
                System.out.println(0);
            }
            else{
                System.out.println(1);
            }
        }



    }
}

 

 

4. 보충 및 회고 

(1) 보충

(1) java 의 정렬함수의 시간 복잡도는 O(n log n)이다.

 

 

 

 

 

(2) 회고 : 문제풀이과정에서 어떻게 접근하려고했는지 (접근방법) + 어려움이 있었는데 해결했다.

1)

정렬도 이진탐색도 모두 가능했다.

하지만 시간초과가 되었다. 결국 같은 이진탐색이라고 하더라도 컬렉션에 있는 것은 시간복잡도가 다를수도 있겠다 생각된다.

 

 

 

---

1. 보충

 

 

2. 회고