이분탐색(1)_수찾기(1920)

작성일 | In

BJO 1920 수찾기

문제이해 : N개의 정수가 주어지고, 그 다음 M개의 정수가 주어졌을 때, M개의 수들이 A안에 존재하는지 알아내는 문제

생각한 방법

우선 N개 입력 받고 리스트에 저장 또한 M개 입력 받고 리스트에 저장. M개에서 하나씩 꺼내서 N개 비교하면서 있으면 1 없으면 0 출력

binarySearch를 구현하는 문제 다른 사람 코드 참고하지 말고 직접 구해보려고 선택했다.

갑자기 짜려니까 모르겠어서 기존에 공부했던 SWE 자료 복습했다.

이진 검색 과정

  1. 자료의 중앙에 있는 원소 선택
  2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교
  3. 목표값 < 중앙 원소의 값 : 자료의 왼쪽 반에 대해서 새로운 검색 수행. 목표값 > 중앙 원소의 값 : 자료의 오른쪽 반에 대해서 새로운 검색 수행
  • 이진 검색의 경우 자료에 삽입이나 삭제가 발생하였을 때, List의 상태를 항상 정렬 상태로 유지해 줘야 한다.

1. 반복문을 이용한 방법

def binarySearch(arr,key):
    start = 0
    end = len(arr)-1
    while(start <= end):
        middle = start + (end-start)//2 # start를 더해주고, (end-start)//2를 더해줘야. 반복적으로 탐색 가능
        if(key == arr[middle]) : # 검색 성공
            return True
        elif(key <arr[middle]):
            end = middle-1 # 1을 빼주는 이유는 middle의 왼쪽 한칸으로 이동해서 end를 정해줘야 다시 반복
        else:
            start =  middle +1
    return False # 검색 실패

2. 재귀함수를 이용한 이진 검색 구현

    def binarySearch2(arr,low,high,key):
        if low > high : # 검색 실패 시작값이 끝값보다 크다면. 탐색 그만
            return False
        else:
            middle = (low + high ) // 2
        if key = a[middle]: # 검색 성공
            return True
        elif key < a[middle]:
            return binarySearch2(a, low, middle-1, key)
        elif a[middle] < key:
            return binarySerach2(a, iddle+1, high, key)

3. bisect 라이브러리 사용

bisect_left(a,x,lo=0,hi=len(a))

import bisect
myList = [1,2,3,7,9,11,33]
print(bisect.bisect_left(myList,3))

정렬된 순서를 유지하기 위해 x를 a에 삽입할 위치를 찾는다 매개 변수 lo와 hi는 고려해야할 리스트의 부분집합을 지정하는데 사용 기본적으로는 전체 리스트에 적용 x가 a에 이미 있으면 기존 항목 앞(왼쪽)이 반환된다. 반환 값은 a가 이미 정렬되어있다고 가정할 때, list.insert()의 첫 번쨰 매개변수로 사용하기 적합하다.

bisect_right(a,x,lo=0,hi=len(a))

bisect_right()는 bisect_left()와 비슷하지만, x의 오른쪽에 삽입 위치를 반환한다. bisect.bisect는 right와 똑같은 함수다.

bisect.insort_left(a,x,lo=0,hi=len(a))

a에 x를 정렬된 순서로 삽입한다. 즉 a가 이미 정렬되었다고 가정할 때, a.insert(bisect.bisect_left(a, x, lo, hi), x)와 동일하다.

bisect.insort_right(a,x,lo=0,hi=len(a))

insert_left()와 비슷하지만, a에 x를 기존 항목 다음에 삽입

코드

import sys

def binarySearch(arr, key):

    start = 0
    end = len(arr)-1
    while(start <= end):
        middle = start + (end-start)//2
        if(arr[middle] == key):
            return 1
        elif(arr[middle] > key):
            end = middle - 1
        else:
            start = middle+1
    return 0


N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
arr2 = list(map(int, sys.stdin.readline().split()))
arr.sort()
for i in arr2:
    print(binarySearch(arr, i))

참고자료 [bisect]https://docs.python.org/ko/dev/library/bisect.html

0%