[이것이 코딩테스트다] 이진 탐색

알고리즘에서 매우매우 중요한!!

출제빈도가 아주아주 높은!!

이진탐색을 다뤄보도록 하겠습니다. 

변수의 범위가 매우 넓을 경우 일단 무조건 생각해야하는게 바로 

이진 탐색이죠!

지금부터 다뤄보도록 하겠습니다. 

해당 내용은 '이것이 코딩테스트다'를 정리한 내용입니다.

---

1. 이진 탐색

이진 탐색 : 시작점, 끝점, 중간점으로 이루어진 알고리즘으로 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여  원하는 데이터를 찾는 탐색 과정

 

이진 탐색은 중간점과 비교하려는 target과의 대소를 비교하여 start, end를 수정해 나가는 과정이다.

시간복잡도

이진 탐색 알고리즘의 시간 복잡도는 O(㏒N)이다. 이는 직관적으로 이해가 가능한데, 이진탐색 알고리즘은 한 단계를 거칠 때마다 확인하는 원소가 평균적으로 절반으로 줄어들기 때문이다. 예를 들어 원소가 32개라 할 때 1 단계를 거치면 16개로, 2단계를 거치면 8개로 즉 2로 나누는 것과 같다. 이는 연산 횟수가 ㏒N에 비례한다는 것을 의미한다.

 

구현 코드

코드를 살펴보면 이해하기 더욱 편할 것이다. 이진 탐색은 재귀함수와 반복문으로 구현이 가능한데, 실전에서 아무것도 없는 상태로 구현하려는 매우 어렵다. 따라서 코드가 그리길지 않으니 외우는 것을 추천합니다.

 

재귀적 구현

#재귀적으로 구현
def binary_search(array,target,start,end):
    if start > end:
        return None
    
    mid = (start+end)//2

    if array[mid]==target:
        return mid
    
    elif array[mid] > target:
        return binary_search(array,target,start,mid-1)
    
    else:
        return binary_search(array,target,mid+1,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
    else:
        return None

 

2. 문제풀이

   1. 부품찾기

나의코드

#나의코드
n = int(input())
having = list(map(int, input().split()))
having.sort()
m = int(input())
want = list(map(int,input().split()))

# 재귀적으로 이진탐색 구현
def binary_search(array,target,start,end):
    if start > end:
        return False
    mid = (start+end)//2
    if array[mid]== target:
        return True
    elif array[mid] > target:
        return binary_search(array,target,start,mid-1)
    else:
        return binary_search(array, target, mid+1, end)
        
# 손님이 원하는 물품을 내가 갖고 있는지 확인
for w in want:
    if binary_search(having,w,0,n-1):
        print('yes',end=" ")
    else:
        print('no',end=" ")

이진탐색 문제로 접근하여 손님이 원하는 물품을 각각 target으로 설정하여 해당 물품이 나에게 있는지 없는 확인하는 방식으로 알고리즘을 작성하였습니다.

 

정답코드(계수정렬)

#정답코드(계수정렬)
n = int(input())
array = [0]*1000001

# 가계에 있는 물품을 계수정렬로 표시
for i in input.split():
    array[int(i)] = 1

m = int(input())
x = list(map(int, input().split()))

for i in x:
    if array[i]==1:
       print('yes',end=" ")
    else:
        print('no',end=" ")

물론 이진탐색을 이용한 답도 있지만 색다른 방법으로 푼 방법을 소개하려고 합니다. 

해당 코드는 앞서 배운 계수 정렬을 이용한 방법으로 N,M이 모두 1000000이하이므로 계수정렬 사용이 가능합니다. 이렇게 주어진 input의 범위를 통해 문제방법을 추론할 수 있다는 사실을 다시금 알게 되었습니다.

 

정답코드(집합 자료형 이용)

# 정답코드(집합 자료형 이용)
n = int(input())
array = set(map(int, input().split()))

m = int(input())
x = list(map(int, input().split()))

for i in x:
    if i in array:
       print('yes',end=" ")
    else:
        print('no',end=" ")

이렇게 집합자료형을 이용할 수도 있습니다. 집합자료형은 다른 포스트에서 정리하도록 하겠습니다.

 

   2. 떡볶이 떡 만들기*

해당 문제는 전형적인 파라메트릭 서치 문제이다. 이는 최적화 문제를 결정문제로 바꾸는 해결 기법으로, 원하는 조건을 만족하면 'yes' 아니면 'no'로 대답하며 탐색 범위를 좁혀 나가는 것이다.

 

정답코드

n, m = map(int, input().split())
array = list(map(int, input().split()))

start = 0
end = max(array)

result = 0
while start<=end:
    mid = (start+end)//2

    total=0

    for x in array:
        if x > mid:
            total += x-mid
    # 최대한 덜 잘랐을 때가 정답이므로
    if total >= m:
        result = mid
        start = mid + 1
    else:
        end = mid -1

print(result)

 

 

사진출처

이진탐색 - https://t1.daumcdn.net/cfile/tistory/233C703B577E34840E