이진 탐색 _ Python

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

• 정렬된 데이터에서 사용 가능
• 시작점, 끝점, 중간점 3가지 변수 사용
• 찾으려는 데이터와 중간점을 반복적으로 비교하여 원하는 데이터를 찾음

※ 시작점, 끝점, 중간점은 배열의 인덱스!!

배열의 크기가 n일 경우 처음 탐색을 시작할 때 시작점은 0, 끝점은 n-1이 된다. 

 

 

 

시간 복잡도

: O(logN)

한번 확인 할 때마다 원소 개수가 절반으로 줄어들기 때문에

 

 

코딩 테스트에서의 이진 탐색

간단해보이지만 실전에서 제대로 짜기 어려움

단골 문제니까 꼭 외우기 0.<

탐색 범위가 큰 상황에서 탐색을 가정하는 문제가 많다!

>> 탐색 범위가 2000,0000이 넘어가면 이진 탐색 고려

 

※ 데이터 단위가 천만이 넘어갈 경우 시간 복잡도 O(logN)정도가 되어야 한다.

 

구현 방법

1) 재귀 함수 사용

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)

 

2) 반복문 사용

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

 

---

 

~ 문제 풀이 ~

 

1. 부품 찾기(p.197)

메모리 제한: 128MB

시간 제한: 1초

탐색 범위: 최대 1,000,000 (N의 개수)

 

코드

import sys

# 이진 탐색 함수
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)


# 입력받기
N = int(input())
NList = sys.stdin.readline().rstrip().split()
M = int(input())
MList = sys.stdin.readline().rstrip().split()

NList.sort()
result = 0

for i in MList:

    if binary_search(NList, i, 0, N-1):
        print("yes", end=' ')
    else:
        print("no", end=' ')

 

시간 복잡도 

NList를 정렬할 때 : O(N * logN)

MList 값을 찾을 때: O(M*logN)

-> O((N+M) * logN)

 

---

2. 떡볶이 떡 만들기(p.201)

메모리제한: 128MB
시간 제한: 1초
탐색 범위: 10억

문제를 읽고 생각하기

문제:  떡을 한번에 잘라서 남는 길이의 합이 주어졌을 때, 떡을 얼마로 잘라야할까??

구해야 할 것: 떡을 자를 길이(H) (남은 길이의 합 계산 먼저가 아니라, 떡의 길이(H)에 따른 합으로 생각하기)

 

알고리즘 생각해보기

1. 여러 개의 떡이 있을 때, 0~가장 긴 떡의 길이 사이의 어떤 값(H)을 찾아야함.

- 시작점: 0, 끝점: 가장 긴 떡의 길이, 중간점: H

2. 이진 탐색으로 중간값으로 잘랐을 때 남은 떡의 합과 원하는 떡의 합을 비교

- 설정값으로 잘랐을 때 더 크면, 자르는 길이(H)를 늘리면 됨. 

- 반대로 더 작으면, 자르는 길이(H)를 줄이면 남는 양이 늘어남.

 

풀이 실수

1) 남는 길이 계산할 때 실수

#전체 합에서 mid*N만큼 빼주는거 ->  떡이 mid보다 짧을 때 안잘리니깐 안됨.
#total = sum(MList) - (N * mid)
total = 0
    for x in MList:
        if x > mid:
            total += x - mid

2) 가장 긴 떡 구할 때

# 내코드: 정렬해서 마지막 인덱스  --> max()함수 사용
# MList.sort()
# end = int(MList[-1])
end = max(MList)

 

코드

N, M = list(map(int, input().split(' ')))
MList = list(map(int, input().split()))

end = max(MList)
start = 0
result = 0
while(start <= end):
    mid = (start + end) // 2
    total = 0
    for x in MList:
        if x > mid:
            total += x - mid
    # 원하는 값 M 보다 남은 값(total)이 작을 경우, middle을 줄여서 total을 늘리기
    if M > total:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)