[이코테 # 탐색1] 이진 탐색/이진 탐색 트리 알고리즘, 부품찾기(이진탐색), 떡볶이 떡 만들기(이진탐색)

* 이진 탐색

• 이미 정렬되어 있는 경우에 사용할 수 있는 알고리즘.
• 한 번 확일할 때마다 확인하는 원소의 개수가 절반씩 줄어들기에 시간 복잡도가 O(logN)이다.
• 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)을 적용하자.
• 코딩테스트 단골 문제이니 소스코드 외울 것.

# 이진 탐색 소스코드 구현 (재귀 함수)
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
    return None

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

 

*이진 탐색 트리

• '왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드'을 만족하는 트리.
• 데이터를 넣고 빼는 방법은 자료구조에 가깝고, 구현을 요구하는 문제는 출제 빈도가 낮다.
• 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 고려할 것.
• 입력 데이터가 많은 문제는 sys라이브러리의 readline() 함수를 이용하면 좋다.

import sys

# 하나의 문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()
# 입력 받은 문자열 그대로 출력하기
print(input_data)

rstrip() : readline()으로 입력하면 입력 후 줄 바꿈 기호가 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용한다.

 

 

* 부품 찾기(p.197 이진탐색)

 N개의 부품 종류에서 M개의 부품 찾기.

# 오답 풀이 -> 비슷한 구현 구조인 집합 자료형을 이용하면 시간복잡도가 해결됨.
N = int(input())
n = list(map(int, input().split()))

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


# 순차탐색, 시간복잡도 O(n^2)
# M*N = 최악의 경우 100,000,000,000으로 시간초과할 가능성이 크다.
for i in range(M):
    if m[i] in n:
        print("yes", end = ' ')
    else:
        print("no", end = ' ')

재귀함수를 이용한 풀이

# 제공 답변 (약간 변형)
N = int(input())
n = list(map(int, input().split()))
n.sort()

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


# 이진탐색(재귀함수)
# 전체 시간복잡도 : 정렬함수 + 이진탐색 함수 
# 전체 시간복잡도 = NlogN+MlogN = O((N+M)logN)
def bi_search(n, target, start, end):
    if start > end:
        return False
    middle = (start + end) // 2
    if n[middle] == target:
        return True
    elif n[middle] < target:
        return bi_search(n, target, middle + 1, end)
    elif n[middle] > target:
        return bi_search(n, target, start, middle - 1)


for i in M:
    if bi_search(n, i, 0, N - 1):
        print("yes")
    else:
        print("no")

 

계수행렬을 이용한 풀이

# 계수행렬을 이용한 제공답변
# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001

# 가게에 있는 전체 부품 번호를 입력 받아서 기록
for i in input().split():
    array[int(i)] = 1

# M(손님이 확인 요청한 부품 개수) 입력
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(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 입력 받아서 집합(Set) 자료형에 기록
array = set(map(int, input().split()))	# set()함수는 집합 자료형을 초기화할 때 사용

# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

30분 시간초과

오답노트

시간복잡도 생각할 것.

 

* 떡볶이 떡 만들기(이진탐색)

# 제공답
# 떡의 개수(N)와 요청한 떡의 길이(M)을 입력
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때의 떡볶이 양 계산
        if x > mid:
            total += x - mid
    # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)
    if total < m:
        end = mid - 1
    # 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)
    else:
        result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
        start = mid + 1

# 정답 출력
print(result)

오답노트 : 

이진 탐색 적용 어렵.

 

* 참고

https://github.com/ndb796/python-for-coding-test