순차 탐색

  • 데이터를 앞에서부터 하나씩 확인, 탐색의 기본
  • count() 함수 등에 사용되며 많이 쓰임
  • O(N) )


이진 탐색 특징

  • 리스트 내에서 데이터를 매우 빠르게 탐색할 수 있음
  • 이진 탐색은 배열 내부 데이터가 정렬되어 있어야만 사용 가능
  • 탐색 범위를 절반씩 좁혀감
  • 시작점 s, 끝점 e, 중간점 mid 세 변수 사용
  • 찾으려는 데이터와 mid 데이터를 비교하여 원하는 데이터를 찾는 과정
  • 범위 좁힐 때 mid 자리는 포함하지 않도록 짜자!
  • O(logN)
  • 2 가지 방법 구현 가능
    • 재귀
    • 반복문
  • 간단한 원리지만 코테에서 이진 탐색을 구현할 수 있는 사람은 10% 내외임. 무조건 여러 차례 직접 구현하면서 외울것

  • 일반적으로 코테에서 이진 탐색 문제는 탐색 범위 크게 주는 경우가 많음, 데이터 개수가 1,000만을 넘거나, 검색 값 범위가 1,000억 이상이면 이진 탐색을 고려할 것

    → 이럴 때 입력 값은 반드시 sys.stdin.readline().rstrip() 해야 입력 시간 초과 안걸림

이진 탐색 트리

  • 자료구조
  • 이진 탐색을 지원해줌
  • 두 자식을 가지며 왼쪽은 부모보다 작고, 오른쪽은 부모보다 큼
  • 보통 이진 탐색 트리 자료구조를 구현하는 문제는 안나옴

부품 찾기 문제

N (1 ≤ N ≤ 10^6) 개의 부품의 정수 번호가 담긴 리스트에서 M (1 ≤ M ≤ 10^5) 개 원소를 찾는 문제. M 개 원소를 순차적으로 보며 찾는 부품이 있으면 ‘yes’ 를 출력하고, 없으면 ‘no’ 를 출력하라.

N = 5, [8, 3, 7, 9, 2]

M = 3, [5, 7, 9]

⇒ no yes yes

솔루션

  1. 이진 탐색
  2. 계수 정렬
    백만짜리 리스트를 만들어서 카운트 세고, 0 이 아니면 yes 출력.
  3. set 사용
    부품 리스트를 set 에 넣어서 중복 제거 → 찾는 부품을 순차적으로 돌며 순차 탐색

파라메트릭 서치

  • 최적화 문제 (최댓값 or 최솟값 찾기) 를 결정 문제 (O or X) 로 바꾸는 해결 기법
  • 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 나옴
  • 나는 시작점을 min 으로 잡았는데, 문제는 0 으로 잡음. 나처럼 하면 안되는건가? ⇒ m 이 클 경우 height가 원소들보다 작아질 수도 있기 때문에 0 으로 잡는게 맞음
  • 파라메트릭 서치 문제는 반복문으로 해결
  • 백준 나무자르기 문제 볼 것!



참조


  • part2, 이것이 취업을 위한 코딩테스트다 with 파이썬