5. 이진 탐색

문제풀이/이것이 코딩 테스트다 with 파이썬

5. 이진 탐색

딜레이레이 2022. 1. 25. 14:45

https://zero0205.notion.site/5-a29d6140501c44e6be887487bf7554fc

5. 이진 탐색

범위를 반씩 좁혀가는 탐색

zero0205.notion.site

범위를 반씩 좁혀가는 탐색

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
장점 : 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있음.
시간 복잡도
: 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요 ⇒ 최악의 경우 O(N)
구현 매우 간단. ⇒ 그냥 리스트의 데이터에 하나씩 방문하며 검사.

사용 예

리스트의 특정 값의 원소가 있는지 체크할 때
리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용 시에도 내부에서는 순차 탐색 수행

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i + 1    # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0])  # 원소의 개수
target = input_data[1]

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

결과

생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.
5 apple
앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.
banana melon apple lemon grape
3

순차 탐색 : 반으로 쪼개면서 탐색하기

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 탐색
배열 내부의 데이터가 정렬되어 있어야만 사용 가능
장점 : 이미 정렬되어 있는 데이터라면 매우 빠르게 탐색 가능
단점 : 데이터가 무작위일 때는 사용 불가
위치를 나타내는 변수 3개 사용 : 탐색하고자 하는 범위의 시작점, 끝점, 중간점
한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어듦 ⇒ 시간 복잡도 O(logN)
소스 코드 1 (재귀 함수 이용)

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

# 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)

소스 코드 2 (반복문 이용)

# 이진 탐색 소스코드 구현(반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        if 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)

코딩 테스트에서의 이진 탐색
- 참고할 소스코드가 없는 상태에서 이진 탐색의 소스코드를 구현하는 것은 상당히 어려울 수 있음
- 코드도 짧고 단골로 출제되는 문제이니 가급적 외우길 추천

트리 자료구조

그래프 자료구조의 일종.
노드와 노드의 연결로 표현.
- 노드 : 정보의 단위. 어떠한 정보를 가지고 있는 개체.
데이터베이스 시스템이나 파일 시스템 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용
특징
- 부모 노드와 자식 노드의 관계로 표현
- 최상단 노드 : 루트 노드
- 최하단 노드 : 단말 노드(리프 노드)
- 트리에서 일부를 떼어내도 트리 구조 ⇒ 서브 트리
- 파일 시스템과 같은 계층적이고 정렬된 데이터를 다루기에 적합

이진 탐색 트리

트리 자료구조 중 가장 간단한 형태
이진 탐색이 동작할 수 있도록 고란된, 효율적인 탐색이 가능한 자료구조
특징
: 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

빠르게 입력 받기

입력 데이터가 많은 문제의 경우 input() 함수 사용 시 동작 속도가 느려서 시간 초과될 수 있음
```
Hello World
Hello World
```
- readline() 함수 사용 시 한 줄 입력 후 rstrip() 함수 호출 필수
- ∵ 소스코드에 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수 사용 필요
import sys # 하나의 문자열 데이터 입력받기 input_data = sys.stdin.readline().rstrip() # 입력받은 문자열 그대로 출력 print(input_data)
⇒ sys 라이브러리의 readline() 함수를 이용해보자

부품 찾기

내가 작성한 코드

# N 입력받기
n = int(input())
# 매장에 있는 부품들 번호
a = list(map(int, input().split()))

# M 입력받기
m = int(input())
# 손님이 요청한 부품 번호
b = list(map(int, input().split()))

# 매장에 있는 부품들 번호 정렬
a.sort()

def binary_search(array, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    if array[mid] < target:
        return binary_search(array, target, mid + 1, end)
    if array[mid] > target:
        return binary_search(array, target, start, mid - 1)

for i in b:
    if binary_search(a, i, 0, len(a)) == None:
        print("no", end = ' ')
    else:
        print("yes", end=' ')

책의 해답 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
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        elif array[mid] < target:
            start = mid + 1
    return None

# N(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))
array.sort()    # 이진 탐색을 수행하기 위해 사전에 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int, input().split()))

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

책의 해답 2 (계수 정렬)

# 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=' ')

모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인.

책의 해답 3 (집합 자료형 이용)

# N(가게의 부품 개수)을 입력받기
n = int(input())
# 가게에 있는 전체 부품 번호를 입력받아서 집합(set) 자료형에 기록
array = set(map(int, input().split()))

# 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=' ')

단순히 특정한 수가 한 번이라도 등장했는지 검사하면 되므로 집합 자료형을 이용하여 문제 해결도 가능
집합 자료형
- set() 함수 : 집합 자료형을 초기화할 때 사용.
- 단순히 특정한 데이터가 존재하는지 검사할 때 매우 효과적.
- 중복 허용하지 X
- ⇒ 종종 중복을 제거하는 필터 역할로 쓰임.
- 순서가 없음(Unordered)
- ⇒ 인덱싱으로 값을 얻을 수 없음.

떡볶이 떡 만들기

내가 작성한 코드
```
# n : 떡의 개수, m : 손님이 요청한 떡의 길이
n, m = map(int, input().split())
ddeok = list(map(int, input().split()))

start = min(ddeok)
end = max(ddeok)

cnt = len(ddeok)

while start <= end:
    sum = 0
    mid = (start + end) // 2
    
    for i in ddeok:
        if i < mid:
            continue
        sum += (i - mid)
        
    if sum == m:
        print(mid)
        break
    # 원하는 양보다 적게 잘라짐 -> 높이 내려야지
    elif sum < m:
        end = mid - 1
    # 원하는 양보다 많이 잘라짐 -> 높이 올려야지
    else:
        start = mid + 1
```
- 잘 모르겠어서 문제 해설에 있는 그림 살짝 컨닝하고 풀었다ㅠㅠ그런데도 틀렸다...
- 내가 작성한 코드의 문제점
  - 시작점을 잘못 잡음. 시작점을 떡 중에 가장 짧은 떡의 길이로 잡았는데 생각해보니 설명할 가치도 없이 틀린 생각이었다. 시작점은 0으로 잡아야했다.
  - 높이는 정수이기에 정확히 손님이 원하는만큼의 떡이 잘라지지 않을 수도 있다. 따라서 높이의 최댓값을 구하려면 책의 해답과 같이 떡이 원하는 양보다 많이 잘라졌을 때의 결과를 저장하며 반복문을 돌려야 한다.

책의 해답

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

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

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

전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제.
- 파라메트릭 서치
  - 최적화 문제를 결정 문제로 바꾸어 해결하는 기법.
  - 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 주로 이용
  - 보통 이진 탐색을 이용하여 해결
  - 이진 탐색을 재귀적으로 하지 않고 반복문을 이용하여 구현하면 더 간결하게 해결 가능
절단기의 높이 범위가 1~10억까지로 매우 크므로 이진 탐색을 활용 ⇒ 대략 31번만에 모든 경우의 수 고려 가능