[이코테 - 이진탐색] 부품 찾기

 

• 문제 설명

첫 번째 줄에 N을 입력받고 두 번째 줄에 N개의 부품을 입력받는다. 세 번째 줄에 M을 입력받고 네 번째 줄에 N개의 부품을 입력받은 후 N개의 부품이 M개 부품에 포함되는지 판단하여 포함되면 yes 안되면 no를 출력하면 된다.

---

• 개념 설명 

문제를 풀기 전에 먼저 이진 탐색의 개념을 잡고 넘어가려 한다.

이진 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다.

이때 이진 탐색을 사용할 때는 꼭 정렬된 상태에서 사용할 수 있다는 점을 기억해두자! 시간 복잡도는 O(logn)이다.

1. 반복문 사용

def binary_search(target, data):
    data.sort()
    start = 0 			# 맨 처음 위치
    end = len(data) - 1 	# 맨 마지막 위치

    while start <= end:
        mid = (start + end) // 2 # 중간값

        if data[mid] == target:
            return mid 		# target 위치 반환

        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1
        else:                    # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return

 

2. 재귀 함수 사용

def binary_search(target, start, end):
    if start > end:		 # 범위를 넘어도 못찾는다면 -1을 반환
        return -1

    mid = (start + end) // 2  # 중간값

    if data[mid] == target:	# 중간값의 데이터가 target과 같다면 mid를 반환
        return mid 

    elif data[mid] > target: # target이 작으면 왼쪽 탐색
        end = mid - 1
    else:                    # target이 크면 오른쪽 탐색
        start = mid + 1

    return binary_search(target, start, end) # 줄어든 범위를 더 탐색

def solution(target, data):
    data.sort()  # 정렬(필수)
    start = 0
    end = len(data) - 1
    return binary_search(target, start, end)

 

이진 탐색을 이용하는 알고리즘은 거의 위 코드를 사용하므로 암기해두면 좋을 것 같다!

 

그럼 다시 문제로 돌아와서 위 코드를 이용해 문제를 풀어보겠다.

 

• 문제 코드

def binary_search(array,target,start,end):
    while start <= end:
        mid = (start+end)//2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

N = int(input())
N_lst = list(map(int,input().split()))
N_lst.sort()
M = int(input())
M_lst = list(map(int,input().split()))

for i in M_lst:
    result = binary_search(N_lst,i,0,N-1)
    if result != None:
        print("yes",end=" ")
    else:
        print("no",end=" ")

 

• 느낀점

아직 문제를 보고 이진 탐색을 필요로 하는지 생각이 나는 수준이 아니기 때문에 관련 문제를 많이 풀어봐야 할 것 같고 혹시라도 정렬이 되어 있는 형태로 문제가 주어진다면 이진 탐색을 먼저 생각해야겠다. 그리고 위 형식의 코드를 익숙하게 사용하기 위해 암기를 하면 도움이 많이 될 것 같다.