[이것이 코딩테스트다] 이진탐색

오늘은 이진탐색에 대한 주제의 포스팅이다. 이진탐색 알고리즘은 리스트 내에서 데이터를 매우 빠르게 탐색한다. 일단 이진탐색을 알아보기 이전에 순차 탐색부터 알아보겠다.

 

 

 

1. 범위를 반씩 좁혀가는 탐색

---

- 순차탐색(Sequential Search)

• 리스트 안에 있는 특정한 데이터를 찾기위해 앞에서 데이터를 하나씩 차례대로 확인하는 알고리즘
• 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용
• 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있음.
• 시간 복잡도 O(N)

 

- 순차탐색 활용

 

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

 

- 이진 탐색 : 반으로 쪼개면서 탐색하기

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
• 데이터가 무작위일 때 사용불가 But 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있음
• 변수 3개 사용. 시작점(start), 끝점(end), 중간점(mid = start + end // 2)
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것
• 시간 복잡도 O(logN)

 

- 트리자료구조

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

트리 자료 구조

 

 

- 이진 탐색 트리

• 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조
• 부모 노드보다 왼쪽 자식 노드가 작음
• 보무 노드보다 오른쪽 자식 노드가 큼
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 => 17 < 30 < 48

이진 탐색 트리

 

 

- 문제 파악법

• 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편
• 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘 문제를 의심해보기

 

 

- 빠르게 입력 받기

• 위 상황처럼 1,000만개 넘는 데이터처럼 입력 데이터의 개수가 너무 많으면 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답판정을 받을 수 있음.
• sys 라이브러리의 readline() 함수를 이용해 시간 초과를 피하자!

import sys

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

# 입력받은 문자열 그대로 출력
print(input_data)​

 

 

 

 

2. 이진 탐색 유형의 알고리즘 문제

---

- 실전문제 부품 찾기

- 실전문제 떡볶이 떡 만들기

- Q 27 정렬된 배열에서 특정 수의 개수 구하기

- Q 28 고정점 찾기

- Q 29 공유기 설치

- Q 30 가사 검색