[이코테] #5 이진 탐색

✏️ 순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

👉 리스트에 특정 값의 원소가 있는지, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때 등 자주 사용

👉 O(N)의 시간복잡도

순차 탐색 소스코드

def search(n, target, arr):
    #각 원소를 하나씩 확인
    for i in range(n):
        if arr[i] == target:
            return i + 1 #인덱스가 0부터 시작하니 +1
        
input_data = input().split()
n = int(input_data[0])
target = input_data[1]

arr = input().split()

print(search(n, target, arr))

✏️ 이진 탐색

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 방법

👉 정렬된 상태의 데이터에서만 사용

재귀 함수 이진 탐색 소스코드

def search(arr, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return search(arr, target, start, mid - 1)
    else:
        return search(arr, target, mid + 1, end)

n, target = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = search(arr, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

👉 중간 지점을 구하기 위해 (start + end) // 2
👉 몫만 구하기 위해 // 몫 연산자 사용

반복문 이진 탐색 소스코드

def search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

n, target = list(map(int, input().split()))
arr = list(map(int, input().split()))

result = search(arr, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

✏️ 실전 문제

부품 찾기

이 문제는 이진 탐색, 계수 정렬, 집합 자료형을 이용해 여러가지 방법으로 해결할 수 있다.

이 세 방법 모두 해결 아이디어는 target리스트를 반복문으로 돌리며 n리스트에 있는지 확인하면 된다.

📍 이진 탐색

해당 값이 없다면 결과값으로 return None을 하고 결과값이 None이라면 no를 출력하도록 한다. 이때 줄바꿈을 하지 않도록 end=' '코드를 사용한다.

📍 계수 정렬

arr이라는 리스트에 100001길이를 만들어 주고 부품 번호를 입력 받아 리스트에 기록한다. 그리고 arr에 손님의 부품 번호가 기록되어 있다면 yes를 출력한다.

📍 집합 자료형

arr을 입력 받을 때 set(map(int, input().split())) 를 사용해 특정 데이터가 존재하는지 검사한다. 이 소스코드가 셋 중 가장 간결함에서는 우수하다.

---

떡볶이 떡 만들기

처음에 가장 큰 데이터부터 -1을 하며 가장 카운트를 하고 큰 데이터가 중복일 경우 중복 데이터 모두 -1을 하는 방법으로 반복하며 카운트 수가 손님이 원하는 값과 일치할 때 리턴하는 함수를 만들어야 하나 고민했지만 매우 복잡해 보였고 이진 탐색을 이용하면 아래처럼 해결된다.

👉 절단기의 높이는 1부터 10억까지의 정수이다. 이처럼 큰 수를 보면 당연히 이진 탐색을 떠올려야 한다!!

중간점을 초기값으로 잡고 손님이 받을 값을 계산 -> 넘치거나 부족하면 상황에 따라 중간점 조절

이렇게 반복하며 손님이 원하는 값과 일치할 때의 중간점을 리턴한다.

이런 파라메트릭 서치 유형은 이진 탐색을 재귀보다 반복문을 이용해 구현하면 더 간결하게 풀 수 있다.

n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))
start = 0
end = max(arr)
result = 0

while start <= end:
    total = 0
    mid = (start + end) // 2
    for x in arr:
        if x > mid:
            total += x - mid
    if total < m:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

전체 소스코드 중 잘랐을 때 떡의 양을 계산하는

for x in arr:
        if x > mid:
            total += x - mid

의 결과를 m과 비교하며 결과에 따라 mid값을 조절한다.!