이분 탐색의 "수 찾기"를 풀어보았습니다.
저는 "이진 탐색"으로 알고 있었는데, "이분 탐색"이라고도 한다네요. 영어 명칭은 "binary search"네요.
문제
N개의 정수가 주어질 때, 이 안에 X라는 정수가 존재하는 지 판별해라.
입출력 해석
처음엔 문제와 입출력이 잘 이해 안가서 고생했습니다 ㅠㅠ 제가 이해한 바를 쉽게 정리해봤습니다.
#입력
5 #1이상 10만 이하의 자연수, 5개의 입력이 주어질 것이라는 뜻
4 1 5 2 3 #5개의 정수 배열(-2^31보다 크고 2^31보다 작은 값)
5 #5개의 찾을 수 X가 주어질 것이다 라는 뜻
1 3 7 9 5 #찾을 수 X의 배열, 앞서 주어진 정수 배열에서 각 X가 존재하는 지 찾으면 된다. (-2^31보다 크고 2^31보다 작은 값)
#출력
1
1
0
0
1
##다섯 개의 X들(1 3 7 9 5)가 앞서 주어진 정수 배열[4 1 5 2 3] 내에 존재하면 1, 존재하지 않으면 0을 출력
이진 탐색
이진 탐색은 "정렬"이 우선되어야 합니다. 정렬된 배열에서 이진탐색을 통해 쉽게 값을 찾을 수 있습니다.
먼저 배열의 중앙값을 찾고 그 중앙값보다 작으면 해당 값의 앞에 있는 값들에 대해서 찾아보고, 크면 해당값 뒤에 있는 값들에 대해 찾아보는 거죠. 숫자 맞추기 게임을 생각해 보시면 더 쉬울 것입니다.
1~10까지의 숫자 중 친구에게 숫자를 생각하라하고, 자신이 그 숫자를 찾는겁니다. 5라고 외쳤을 때 물론 5가 맞다면 제일 좋겠지만, 친구가 더 크다고 하면, 저희는 6~10 중 숫자를 고를 것이고, 작다고 한다면, 1~4 중 숫자를 하나 고르겠죠. 이진 탐색은 이와 같은 원리라고 보시면 될 것 같습니다.
다음은 제가 이 문제에 대해 접근한 방식을 간단한 예시로 설명하겠습니다.
1 3 5 7이 주어졌다고 할 때, 4를 찾고자 한다면 어떻게 될까요? 아래의 작은 숫자는 인덱스 번호를 뜻합니다.
우선, 중앙값을 찾기 위해 중앙값이 있는 인덱스를 구합니다. (0+3)/2 = 1.5 이므로 버림하여 1이 나왔네요. 중앙값 3과 저희가 찾는 값인 4를 비교했을 때 4가 더 큽니다.
4가 더 크므로 찾는 범위를 중앙값이었던 3보다 크게 잡습니다. 인덱스 2 3의 범위로 새로 범위를 설정한 후 중앙값을 구합니다. (2+3)/2 = 2.5이므로 버림하여 2가 나왔네요. 중앙값 5와 비교하니 4가 작습니다.
새로 범위를 설정해야하지만, 중앙값보다 작은 값으로 설정하자니 범위 설정에 오류가 발생합니다. (2~1의 범위, 범위 시작 인덱스 값이 범위 끝 인덱스값보다 크다.) 따라서 저희가 찾는 '4'는 위 배열에 존재하지 않는다고 판단하고 '0'을 출력합니다. 이와 같은 방법으로 배열의 범위를 조절해가며 값이 있는지 확인합니다. 도중에 값을 발견하면 '1'을 출력하고 다음 찾고자 하는 값으로 넘어갑니다.(4 다음에 3을 찾는다면 다시 처음으로 돌아가 3을 찾는 이진탐색 실행)
사용한 코드는 아래와 같습니다.
#1920 수 찾기
N = map(int, input()) #정수 배열의 길이
N_list = list(map(int, input().split())) #주어진 정수 배열
M = map(int, input()) #찾을 수 개수
M_list = list(map(int, input().split())) #찾고자 하는 수 배열
#N_list 안에 존재하는지
N_list.sort() #이진 탐색을 위한 정렬
#case 1: 없을 때
#case 2: 발견
#case 3: 범위 조정
def bin_search(m, st, ed, N_list):
mid = (st+ed)//2
if st>ed: #범위 오류, 이 배열 안에 없다. 0출력
print(0)
elif m == N_list[mid]: #숫자 발견 1출력
print(1)
elif m > N_list[mid]: #중앙값보다 크다, 범위 조정 후 재개
bin_search(m, mid+1, ed, N_list)
elif m < N_list[mid]: #중앙값보다 작다, 범위 조정 후 재개
bin_search(m, st, mid-1, N_list)
for m in M_list:
bin_search(m, 0, len(N_list)-1, N_list)
댓글