파이썬 이진 탐색 다양한 예제 코드

파이썬 알고리즘을 차근차근 알아가고 있는데요, 벌써 이진 탐색 부분입니다! 

파이썬 이진 탐색

우선 이진 탐색은 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘입니다. 

이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때 사용 가능한 알고리즘이고, 

이미 정렬된 상황이라면 O(logN) 시간으로 빠르게 데이터를 찾을 수 있는 장점이 있습니다. 

 

탐색 범위가 2000만을 넘어가는 경우 이진 탐색으로 문제에 접근하는 것이 좋습니다. 

코딩 문제에서 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 이하의 알고리즘을 생각해야 문제를 풀 수 있습니다. 

 

python

파이썬 swap, 정렬

우선 이진 탐색을 하기 전에 필요한 sort 함수를 아래 코드를 통하여 알아보겠습니다. 

첫 줄에서 map(int, input(). split())로 필요한 원소 값을 받습니다. 

그리고 a_array에 대해서는 a_array.sort()로 오름차순 정렬하였고, b_array에 대해서는 sorted()를 이용해서 정렬했습니다. sort()와 sorted()의 다른 점은 sort()는 배열을 반환하지 않고, 원래 배열을 바꾸고, sorted는 원래 배열은 그대로 유지한 상태에서 정렬된 배열을 반환한다는 점입니다. 

그리고 파이썬에서는 temp없이도 간단하게 swap가 가능한데요, 

교체하고 싶은 변수를 서로 다르게 대입해주면 swap가 가능합니다. C언어에서는 temp를 만들어서 해주었던 작업이

(temp = a; a=b; b=temp)작업을 한 줄로 간단하게 (a, b=b, a) 쓸 수 있습니다. 

#두 배열의 원소 교체 
n, k = map(int, input().split())
a_array=list(map(int,input().split()))
b_array=list(map(int,input().split()))

a_array.sort()
b_array=sorted(b_array,reverse=True)
for i in range(k):
    if a_array[i] < b_array[i]:
        a_array[i], b_array[i]=b_array[i], a_array[i]
    else:
        break

print(sum(a_array))

 

파이썬 재귀 함수 이진 탐색 코드

이진 탐색 예제 코드입니다. 

array[mid]와 target 값을 비교하면서 start와 end 값을 바꾸어 원하는 값을 찾을 수 있습니다. 

#재귀 함수로 구현한 이진 탐색 코드

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid =(start+end)//2 #파이썬에서 /를 사용할 경우 실수 값이 나오기 때문에 몫을 출력하는 //사용
    #찾은 경우 중간점 인덱스 반환
    if array[mid]==target:
        return mid
    #중간점의 값보다 target 값이 작은 경우 왼쪽 확인
    elif array[mid] >target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)

#n원소의 개수와 target 찾고자 하는 문자열 입력 받기
#10 7
n, target = list(map(int, input().split()))
#전체 원소 입력 받기
#1 3 5 7 9 11 13 15 17 19
array = list(map(int, input().split()))

#이진 탐색 수행 결과 출력
result=binary_search(array, target, 0, n-1)
if result ==None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)
#결과 4
#10 7
# 1 3 5 7 9 11 13 15 17 19
# 4

파이썬 이진 탐색 while문 사용 

이진 탐색은 재귀 함수를 사용하는 방법도 있지만, while문을 사용해서도 구현할 수 있습니다. 

#이진 탐색 while문 사용 
def binary_search(array, target, start, end):
    while start <=end:
        mid = (start+end)//2
        #찾은 경우 mid 인덱스 반환 
        if array[mid]==target:
            return mid
        #중간점 값보다 target 값이 작은 경우 왼쪽 확인 
        elif array[mid] >target:
            end = mid-1
        #중간점 값보다 target 값이 큰 경우 오른쪽 확인 
        else:
            start= mid+1
    return None

 

파이썬 sys 입력 받는 방법 

sys 라이브러리의 readline() 함수를 사용하면 시간 초과를 피할 수 있습니다. 

rstrip()는 줄 바꿈 기호를 없애주는 역할을 합니다. 

#sys 라이브러리로 입력 받는 방법
import sys
#문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()

#입력 받은 문자 출력
print(input_data)
#출력
# Hello, world!
# Hello, world!

 

파이썬 부품 찾기 문제 예제

#부품 찾기 문제 
#입력
# 5
# 8 3 7 9 2
# 3
# 5 7 9

#부품의 개수 n
n=int(input())
#부품 고유 번호 list
array =list(map(int, input().split()))
#확인 개수 m
m=int(input())
#확인 부품 번호 list
check_array=list(map(int, input().split()))

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)

#이진 탐색 전 정렬
array.sort()
for i in check_array:
    if binary_search(array, i, 0, n-1) == None:
        print("no",end=" ")
    else:
        print("yes", end=" ")
# #출력
# no yes yes

 

파이썬 이진 탐색 문제 풀이 예제 

떡을 잘라서 특정 값 이상의 떡이 나오도록 자르는 문제였습니다. 

책에서는 따로 함수 선언 없이 풀었는데, 저는 함수를 선언해서 깔끔하게 푸는 것을 좋아하기 때문에 cut_cal, binary_search 함수를 만들어서 풀었습니다. 

#잘랐을 때 떡의 양 계산 
def cut_cal(array, target):
    ans=0
    for i in array:
        if i > target:
            ans+= i-target
    return ans

def binary_search(target, start, end):
    while start <=end:
        mid = (start+end)//2
        #떡의 길이 계산 
        tem_cut_cal=cut_cal(data_list, mid)
        # 알맞은 길이를 찾았을 때 길이 반환
        if tem_cut_cal ==target:
            return mid
        #떡의 양이 많은 경우 start 지점을 중간으로 바꾸기
        elif tem_cut_cal >target:
            start= mid+1
        #떡의 양이 적은 경우, 더 많이 자르기 
        else:
            end = mid - 1
    return None

#떡의 개수(n)와 요청한 떡의 길이(m)을 입력받기 
n, m= map(int,input().split())
#각 떡의 개별 높이 정보를 입력 받기 
data_list = list(map(int, input().split()))
max_data=0
#max값을 찾는 과정 max_data= max(data_list)로 치환 가능 
for i in data_list:
    if max_data < i:
        max_data=i
#이진 탐색을 이용하여 알맞은 길이 찾기 
answer =binary_search(m,0, max_data)
#정답 출력 
print(answer)

다음 챕터는 벌써 다이나믹 프로그램이네요 ~

아자아자!!