[백준] 1920번 수 찾기 파이썬 문제 풀이

 

문제 고민

처음 이 문제를 봤을때는 간단하게 생각하고 쉽게 풀었습니다. 하지만 다른 알고리즘들이 그렇듯 시간초과 문제가 발생했었고, 한참 고민하다 이진탐색 알고리즘을 알게 되었습니다. 그래서 이진탐색 알고리즘에 대해서 공부를 하게 됐습니다.

 

이진탐색 알고리즘

해당 배열이 있을때 시작, 중간, 끝점을 정해두고 찾고자 하는값이 중간점보다 큰지 작은지 비교한다.

만약에 중간점보다 값이 작다면(2 혹은 3)

아래와 같은 그림으로 끝점은 중간점보다 1칸 작은값으로 이동하게 되고 시작점과 비교해 중간점을 구합니다.

만약 이때 중간점이 구해진다면 일반적인 순차 탐색이라면 최대 8번이 걸릴 수 있었던 과정을 2번의 탐색으로 구할 수 있게 되는 알고리즘입니다.

 

정리

1. 시작점과 끝점을 구해주고 중간점을 구한다.
2. Target값과 중간점을 비교하여 중간점보다 작다면 중간값 -1을 끝점에 위치시키고
3. Target값과 중간점을 비교하여 중간점보다 크다면 중간값 +1을 시작점에 위치시킨다.
4. 중간값이 Target값과 일치한다면 탐색을 종료한다.

 

소스코드 - 이분 탐색 (이진 탐색)

import sys

result = []
N = int(sys.stdin.readline().rstrip())
arrA = sorted(list(map(int, sys.stdin.readline().rstrip().split())))
M = int(input())
arrM = list(map(int, sys.stdin.readline().rstrip().split()))


def binary_search(arr, target, start, end):
    if start > end:
        return 0
    # 중간점 찾기
    mid = (start + end) // 2
    # 데이터를 찾은 경우
    if arr[mid] == target:
        return 1
    # 중간점보다 왼쪽에 데이터가 있는 경우
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid - 1)
    # 중간점보다 오른쪽에 데이터가 있는 경우
    else:
        return binary_search(arr, target, mid + 1, end)


for i in arrM:
    print(binary_search(arrA, i, 0, len(arrA) - 1))

위와 같은 그림을 해당 문제에 적용한다면 다음과 같이 적용이 가능합니다.