백준 1020번: 수 찾기 [python]

유형 : 이분 탐색 (이진 탐색)
난이도 : 실버 4
https://www.acmicpc.net/problem/1920

문제 접근

N개의 자연수와 , M개의 자연수를 입력받고
M개의 자연수가 M개의 자연수 들 중에서 있는지 파악하는 문제,
있으면 1 없으면 0을 M개의 줄로 출력한다.

N들을 집합 자료형 set 안에 넣고
M개를 거기에 있는지 확인하는 형식으로 풀어보겠다.

해답 및 풀이

import sys

input = sys.stdin.readline

N = int(input())
N_nums = set(map(int,input().split()))

M = int(input())
M_nums = list(map(int,input().split()))

for num in M_nums:
    if num in N_nums:
        print(1)
    else:
        print(0)

for 문에 num과 그 안 if문에 num는 같은 녀석이다.
즉 M_nums의 요소 num이 N_nums에 들어있나? 있으면 1, 없으면 0 출력이라는 구문이다.

근데 이게 이방법이 이진 탐색으로 푼게 맞을까? 이진탐색이뭐야?

위 방법은 집합 자료형을 활용한 해시테이블 방법이다.
나는 이진 탐색에 대해 공부해보고자 해당 문제를 풀려고 했다.

🔍 그럼 이진 탐색(Binary Search) 이란?
"정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘"
매번 중간값과 비교해서 탐색 범위를 절반씩 줄여나가는 방식

• 전제 조건
  - 탐색 대상은 정렬되어 있어야 함
  - 시간복잡도는 O(log N)

이진 탐색으로 푼 코드

import sys
input = sys.stdin.readline

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

N = int(input())
N_nums = sorted(list(map(int, input().split())))  # 반드시 정렬!

M = int(input())
M_nums = list(map(int, input().split()))

for num in M_nums:
    if binary_search(N_nums, num):
        print(1)
    else:
        print(0)

함수 binary_search

mid인덱스의 값( 가운데 값 ) 을 target과 비교해서
target이 더 크다면 mid의 인덱스를 +1 해주어 다시 비교,
target이 더 작다면 mid의 인덱스를 -1 해주어 다시 비교 하는
포인터를 두개 설정해주어 가운데 부터 탐색해준다.