5일차 - 이진 탐색

순차 탐색(Sequential Search)

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

 

프로그래밍언어를 배우는데 많이 실습 해봤을 탐색이다.

 

 

이진 탐색(Binary Search)

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

시간 복잡도 : 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)
    
    # 원소의 개수와 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)

 

반복문으로 구현한 방법이다.

# 반복문으로 구현한 이진 탐색 소스코드
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
        
    # 원소의 개수와 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. 부모 노드보다 왼쪽 자식 노드가 작다.

2. 부모 노드보다 오른쪽 자식 노드가 크다.

한마디로 하자면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

 

코딩테스트 문제 유형 중 이진탐색 문제가 나오면 거의 접근도 못했던 기억이난다.

 

 

실습문제 1. 부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

위 문제를 평범한 메소드를 이용해서 구현할 수도 있지만, 이진탐색으로 구현해보자.

핵심알고리즘은 아래의 이진탐색이다.

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

 

 

실습문제 2. 떡볶이 떡 만들기

떡집일을 하는데, 떡볶이떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm이고, 절단기 높이를 15cm라고하면 떡의 높이는 15, 14, 10, 15cm가 되고 손님은 6cm만큼의 길이를 가져간다.

 

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

 

위 문제는 전형적인 이진 탐색 문제이자, 파라매트릭 서치의 유형이다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

 

문제의 해결 과정

1. 시작점은 0, 끝점은 가장 긴 떡의 길이로 설정한다. 시작점과 끝점의 중간숫자를 절단기 높으로 설정하면 얻을 수 있는 떡의 합이 나온다. 필요한 떡의 길이보다 크다면 시작점을 증가시킨다.

2. 시작점을 증가 시켰다면 중간점이 증가하는데, 또 필요한 떡의 길이보다 크다면 시작점을 증가시킨다.

3. 시작점을 또 증가 시켰다면 중간점이 또 증가하는데, 필요한 떡의 길이보다 작으면 끝점을 감소시킨다.

4. 위 과정을 반복한다.

 

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)