[알고리즘] 이코테 - 이진탐색

이진탐색

• 리스트 내에서 데이터를 빠르게 탐색하는 알고리즘
• 순차탐색: N개의 데이터가 있을 때, 그 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해 준 경우, 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법.시간이 충분하다면 항상 원하는 데이터를 찾을 수 있다. e.g, 리스트 자료형에서 특정 값을 가지는 원소의 개수를 세는 count() 메서드
  • 데이터의 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 함. 데이터의 개수가 N개일 때 순차탐색의 최악의 경우 시간복잡도는 O(N)이다.
• 이진탐색: 반으로 쪼개면서 탐색하기
  • 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다
  • 시작점, 끝점, 중간점 관련 변수 사용
  • 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다
    • 원하는 데이터보다 중간점이 더 크다면 중간점 이후의 값은 확인할 필요가 없어서 끝점을 지금의 중간점으로 옮긴다.
    • 원하는 데이터가 더 크다면 중간점 이하인 데이터는 더 이상 확인할 필요가 없어서 중간점을 다음의 시작점으로 한다.
  • 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다 -> 시간 복잡도가 O(logN),단계마다 2로 나누는 것과 동일하므로 연산 횟수는 log2(N)에 비례한다

 

#재귀함수 이진탐색
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=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
  retun None
  
############################################################

# 입력받기
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)

 

• 코딩 테스트에서의 이진 탐색
  • 트리 자료구조: 노드와 노드의 연결로 표현됨, 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체이다. 그래프 자료구조 일종으로 DB 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적
  • 이진 탐색 트리: 트리 자료구조 중 가장 간단한 형태이다. 이진 탐색이 동작할 수 있도록 고안된, 효율적 탐색이 가능한 자료구조.
    • 부모 노드보다 왼쪽 자식노드가 작다. 부모노드보다 오르쪽 자식 노드가 크다.
    • 루트 노드부터 방문한 후, 원하는 데이터가 더 크다면, 왼쪽 노드 tree는 확인할 필요가 없기에 오른쪽 노드 방문. 반대의 경우 왼쪽 노드 방문하는 식으로 공식에 따라 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식노드로 이동하며 반복적 방문.
      • 자식노드가 없을 때까지 원소가 없다면 이진 탐색 트리에 원소가 없는 것
• 빠르게 입력받기: 이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 넓은 경우에 나오기 때문에 입력 데이터의 개수가 많은 문제 input()함수를 사용하면 동작 속도가 느려서 시간 초과
  • 입력 데이터가 많은 문제는 sys의 readline()함수 사용하기
  • rstrip(): 소스코드에 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력됨 -> 줄 바꿈 기호, 공백 문자를 제거하려면 rstrip()함수 사용

 

 

** 코딩테스트 시 입력받는 시간을 줄이는 코드

import sys
#하나의 문자열 데이터 입력받기
input = sys.stdin.readline().rstrip()