5. 이진 탐색

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

5. 이진 탐색

 

범위를 반씩 좁혀가는 탐색

순차 탐색

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
• 장점 : 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있음.
• 시간 복잡도
• : 데이터의 개수가 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번만에 모든 경우의 수 고려 가능