- 이진탐색 이해하기
- 이진탐색 구현하기
- 알고리즘 문제 풀어보기
1. 이진탐색 이해하기
(1) 이진탐색이란?
정렬된 리스트에서 검색하고자 하는 키 값 x를 찾아내는 알고리즘이다.
(2) 로직 이해하기
이진탐색의 탐색 방법은 다음과 같다.
- 정렬된 배열에서 가장 가운데 값과 키 값을 비교한다.
- 가운데 위치한 값이 키 값과 같으면 이 값의 위치를 반환한다.
- 키 값이 더 크다면 가운데 값을 기준으로 오른쪽을, 키 값이 더 작다면 왼쪽을 탐색한다.
- 키 값을 찾을 때 까지 반복한다.
(3) 시간 복잡도
이진 탐색에서의 시간 복잡도는 탐색 과정 중에 수행되는 비교 횟수의 합으로 결정된다. 우선 가운데 값이 키 값과 같은지 비교하는 상수 시간과, n/2로 나눈 부분 배열에 대한 비교 횟수를 합하면 T(n) = T(n/2) + 1 이 된다. 이를 계산하면 이 알고리즘의 시간 복잡도는 O(log n)가 됨을 알 수 있다.
(4) 특징
- 이진 탐색은 키의 값이 중앙 값보다 크냐 작냐에 따라 다음 탐색 지점이 달라지기 때문에 탐색 대상 리스트는 반드시 정렬된 데이터여야 한다.
- 삽입 및 삭제 시 데이터의 이동이 발생한다. 삽입/삭제 후에는 데이터의 정렬 상태를 유지하기 위해서 데이터의 이동이 발생한다. 따라서 삽입/삭제가 빈번한 문제에서는 비효율적이다.
2. 이진탐색 구현하기
이진 탐색은 재귀함수를 사용한 순환 형태와 반복문을 사용한 형태로 구현할 수 있다.
(1) 순환형태의 알고리즘
def binary_recursion(key, search_list, left, right):
if left > right: # return -1 if search_list doesn't have a key in it
return -1
mid = (left+right) // 2 # get an index of middle element of the list
if key == search_list[mid]: # if the key matches the middle element, return the index
return mid
elif key > search_list[mid]: # if the key is bigger than the middle element
left = mid + 1 # The next search would be started from here
return binary_recursion(key, search_list, left, right) # invoke binary_recusion to search the rest
else:
right = mid - 1
return binary_recursion(key, search_list, left, right)
key = 36
li = [16, 18, 20, 36, 52]
print(binary_recursion(key, li, 0, 4)) # 결과: 3키 값이 중앙 값보다 작거나 클 때 다음 탐색의 시작점이 될 인덱스를 조정해 준 뒤 자기 자신(binary_recursion)을 다시 호출하여 나머지 부분을 탐색한다.
(2) 반복형태의 알고리즘
def binarySearch(key, search_list):
left = 0
right = len(search_list) -1
while left <= right: # search as long as the list has a key in it
mid = (left + right) // 2
if key == search_list[mid]:
return mid
elif key > search_list[mid]:
left = mid + 1
else:
right = mid - 1
return -1
key = 36
li = [16, 18, 20, 36, 52]
print(binarySearch(key, li)) # 결과: 3반복문을 돌며 중앙 값의 인덱스를 한 반복마다 구해준 뒤 중앙 값과 키 값이 같으면 키를 찾으며 탐색 종료한다. 키 값이 더 큰 경우 나머지 오른쪽 부분을 탐색, 더 작은 경우 왼쪽 부분을 탐색한다.
3. 알고리즘 문제 풀어보기
위에서 공부한 알고리즘을 문제에 적용해 보기 위해 백준 알고리즘 문제를 풀어보았다.
1920. 수 찾기
n = int(input())
search_list = list(map(int, input().split()))
search_list.sort()
m = int(input())
key_list = list(map(int, input().split()))
for key in key_list:
left = 0
right = len(search_list) - 1
is_key = 0
while left <= right: # 리스트 내에 키가 존재할 때만 실행
mid = (left + right) // 2 # 가운데 값의 인덱스
if key == search_list[mid]: # 키를 찾았다면
is_key = 1
break
elif key < search_list[mid]: # 키가 가운데 값보다 작다면
right = mid - 1 # 인덱스 right조정
else: # 키가 가운데 값보다 크다면
left = mid + 1 # 인덱스 left 조정
print(is_key) # 키 값 존재 여부 출력문제를 풀기 앞서 이진탐색을 공부했기 때문에 문제를 보자마자 파이썬으로 이진탐색을 구현했던 것 처럼 문제를 풀었다. 공부를 안하고 풀었으면 꽤 고민했었을 문제일 수도 있는데 꽤 수월하게 푼 것 같다.
문제를 보다보니 연산자 in을 이용해서도 풀 수 있을 것 같아서 그렇게도 시도해보았는데, 아무래도 n/2로 나누어 검색하는 이진탐색과는 달리 일일이 검색을 해서인지 시간 초과가 되었다.
한가지 궁금한 점은 내가 이것이 이진 탐색 문제인지 몰랐어도 이진탐색으로 풀 생각을 할 수 있었을까 이다.(ㅋㅋㅋ) 문제를 보고서 적절한 알고리즘을 떠올릴 수 있도록 하는게 앞으로의 숙제인것 같다.
다음에도 뺘샤!!🔥
참고:
이진탐색 알고리즘 개념이해 및 추가 예제
책 - 알고리즘 [이관용, 김진욱]
