파이썬을 이용한 검색 알고리즘(선형, 이진)

파이썬을 이용한 알고리즘 2탄이 왔다!!

이번에 소개할 알고리즘은 검색 알고리즘! 모두들 따라 해 보자.

검색 알고리즘

1. 선형 검색(Linear Search)

• 가장 단순하고 간단한 탐색 알고리즘으로 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘.

# 0(n)
def findIndexLinear(array, cond):
    for i in range(len(array)):
        if(array[i] == cond):
            return i 

print(findIndexLinear([2,4,5,1,6],2))
print(findIndexLinear([2,4,5,1,6],6))

 

0
4

---

2. 이진 검색(binary Search)

• 중간 위치 선택 : (첫번째 인덱스 + 마지막 인덱스) / 2
• 만약 짝수일 경우 소숫점 자리를 올릴 것인지 내릴 것인지 결정
• 중간 위치가 찾는 값인지 비교
• 아닐경우 중간을 기준으로 왼쪽 또는 오른쪽을 선택해 다시 인덱스(첫번째, 마지막)조정하여 비교해 나간다.
  • 왼쪽일 경우 : 마지막 인덱스 = 중간위치 - 1
  • 오른쪽일 경우 : 첫번째 인덱스 = 중간위치 + 1

import math # ceil(), floor(), round()

# 0(log n)
def binary_search(array, cond):
    head = 0
    tail = len(array)-1
    
    mid = math.floor((head + tail) / 2)
    
#    if(array[mid ]==cond):
#        return "{}번째 요소가 일치합니다.".format(mid)
#    
#    while(array[mid] != cond):
#        if(head > tail):
#            return "결과를 찾을 수 없다."
#        
#        if(array[mid] < cond):
#            head = mid + 1
#            mid = math.floor((head + tail) / 2)
#        else:
#            tail = mid - 1
#            mid = math.floor((head + tail) / 2)
           
    while(head <= tail):
        mid = math.floor((head + tail) / 2)
        if(array[mid] == cond):
            return mid
        elif array[mid] < cond:
            head = mid + 1
        else:
            tail = mid - 1
            
#    return "{}번째 요소가 일치합니다.".format(mid)      
# --------------------------------------------------------
print(binary_search([1, 2, 4, 5, 6, 7, 9, 28, 49, 70],6))
print(binary_search([1, 2, 4, 5, 6, 7, 9, 28, 49, 70],50))

 

4
None

---

3. 부품 찾기

부품 매장에서 손님이 원하는 부품을 검색하려고 한다.

####### 매장에 부품 수급하고자 한다.

# 매장에 들여올 부품의 갯수 : 10
n = int(input("부품 갯수 : "))

# 부품번호 입력 : 111, 112, 113, 114, 115, 211, 212, 213, 214, 215
shop = list(map(int, input("부품 번호입력 : ").split()))
shop.sort()

# 손님이 필요한 부품의 갯수 : 3
gn = int(input("필요한 부품 갯수 : "))

# 어떤 부품이 필요한지를 공백을 기준으로 여러 개 입력받기 : 113 115 120
guest = list(map(int, input("필요한 부품 번호입력 : ").split()))

# 손님이 필요한 부품을 하나씩 확인
for i in guest:
    # 해당 부품이 존재하는지 확인
    result = binary_search(shop, i)
    
    if result != -1:
        print("yes", end=" ")
    else:
        print("no", end=" ")

 

부품 갯수 : 10
부품 번호입력 : 111 112 113 114 115 211 212 213 214 215
필요한 부품 갯수 : 3
필요한 부품 번호입력 : 113 115 120
yes yes yes 

---

 

from PIL import Image

4. 떡볶이 떡 만들기

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총길이는 절단기로 잘라서 맞춰준다 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다 손님이 왔을 때 요청한 총길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하세요.

# 떡의 갯수(n)와 요청한 떡의 길이(m)를 입력 : 4 6
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:
        end = mid - 1
    else:
        result = mid
        start = mid + 1
        
print(result)

 

떡의 갯수와 요청한 떡의 길이 입력 : 4 6
각 떡의 길이 입력 : 19 15 10 17
15

---

 

import math
n=int(input("\n떡의 갯수를 입력하세요.\n"))
if n < 0 or n > 1000000 :
    print("떡의 갯수가 잘못되었습니다.")
    
m=int(input("\n요청할 떡의 길이를 입력하세요.\n"))
if m < 0 or m >2000000000 :
    print("요청한 떡의 길이가 잘못되었습니다")


d = list(map(int, input("\n떡의 개별 높이를 입력하세요 : \n").split()))
if len(d) != n:
    print("개별 높이의 갯수가 잘못되었습니다.")
    
def binary_search(d, m):        
    head = 0 
    tail = max(d) 
    
    while (head <= tail):
        guest = 0
        mid = math.floor((head + tail) / 2)
        for i in range(len(d)):
            if d[i-1] - mid > 0:
                guest += d[i-1] - mid
            else :
                guest += 0
        if guest > m :
            head = mid + 1
        elif guest < m : 
            tail = mid -1
        elif guest == m :
            return "\n높이의 최대값 : {}, 떡의 갯수 : {}\n".format(mid, guest)            
    return "\n높이의 최대값 : {}, 떡의 갯수 : {}\n".format(mid, guest)

print(binary_search(d, m))

 

떡의 갯수를 입력하세요.
2

요청할 떡의 길이를 입력하세요.
4 6

간단한 검색 알고리즘에 대해서 알아보았다.

2가지의 예시 문제도 풀어보았는데 어떠한가??

알고리즘은 풀 때마다 어려운 것 같다...

모두들 마스터하는 그날까지 안녕~~