하기 내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬(저자: 나동빈님)'의 책을 정리한 내용입니다.

chap07. 이진 탐색

순차 탐색 : $O(N)$

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
  • 보통 정렬되지 않은 리스트에서 데이터를 찾아내야 할 때 사용

# 정렬 - 순차탐색
def sequence_search(n, target, arr):
  for i in range(n): # 각 원소를 하나씩 확인하며
    # 현재의 원소가 찾고자 하는 원소와 동일한 경우
    if arr[i] == target: 
      return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)
  
  print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요:")
  input_data = input().split()
  n = int(input_data[0])
  target = input_data[1]

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

  print(sequence_search(n, target, arr))

→ 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 함
: 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로, 최악의 경우 $O(N)$

이진 탐색 : 반으로 쪼개면서 탐색 - $O(logN)$

• 이진 탐색 : 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
  ↔ 순차탐색 : 데이터 정렬 여부와 상관 X
• 이진탐색 : 변수 3개 사용(시작점, 끝점, 중간점)
  → 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
  → 한 번 확인할 때마다 원소의 개수가 절반씩 줄어듦 : $O(logN)$

# 이진탐색 - 재귀 함수
def binary_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 binary_search(arr, target, start, mid - 1)
  
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
  else:
    return binary_search(arr, target, mid + 1, end)

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

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

# 이진탐색 - 반복문
def binary_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 = end + 1
  return None

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

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

• 이진탐색은 코딩 테스트에서 단골로 나오는 문제 → 꼭 외워둘 것
  • 높은 난이도의 문제 : 이진탐색 알고리즘이 다른 알고리즘과 함께 사용되기도 함
    → 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어갈 경우 이진탐색과 같은 $O(logN)$

트리 자료구조

이진탐색 - 전제 조건 : 데이터 정렬
→ 동작하는 프로그램에서 데이터를 정렬하는 경우가 많으므로, 이진탐색의 효과적 사용 가능

• 트리 자료구조 : 노드와 노드의 연결로 표현
  • 노드 : 정보의 단위로써 어떠한 정보를 가지고 있는 개체로 이해할 것
• 트리 자료구조의 특징
  • 트리는 부모 노드와 자식 노드의 관계로 표현됨
  • 트리의 최상단 노드: 루트 노드
  • 트리의 최하단 노드: 단말 노드
  • 트리에서 일부를 떼어내도 트리구조이며, 이를 서브 트리라고 함
  • 트리는 파일 시스템과 같이 계층적이고, 정렬된 데이터를 다루기에 적합

이진 탐색 트리

• 이진 탐색 트리 : 트리 자료구조 중 가장 간단한 형태
  → 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
  Q. 모든 트리가 다 이진 탐색 트리인가? Nope!

• 이진 탐색 트리의 특징

  • 부모 노드보다 왼쪽 자식 노드가 적음

  • 부모 노드보다 오른쪽 자식 노드가 큼

    → 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

문제 - 떡볶이 떡 만들기

전형적인 이진 탐색 문제, 파라메트릭 서치

• 파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
  : 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제
  → 범위 내에서 조건을 만족하는 가장 큰 값을 찾아라 : 최적화 문제
  → 이진 탐색으로 결정 문제를 해결하며 범위를 좁혀갈 수 있음
  

현재 이 높이로 자르면 조건을 만족할 수 있는가? → 예 / 아니오로 탐색범위를 좁힘
: 파라메트릭 서치 문제 유형 - 이진 탐색을 재귀적으로 구현하지 않고, 반복문을 이용해 구현하면 더 간결해짐

# 이진탐색 - 떡볶이 떡 만들기
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

start, end = 0, max(arr)

# 이진탐색
res = 0
while start <= end:
  total = 0
  mid = (start + end) // 2

  for i in arr: 
    if i > mid: # 잘랐을 때 떡 길이 계산
      total += i - mid
  
  if total < M: # 떡의 양이 부족한 경우 더 많이 자름(왼쪽 부분 탐색)
    end = mid - 1
  else: # 떡의 양이 충분한 경우 덜 자름(오른쪽 부분 탐색)
    res = mid # 최대한 덜 자를 경우를 정답으로
    start = mid + 1

print(res)