이것이 코딩 테스트다 :: 이진 탐색

순차 탐색

시간복잡도 : O(N)

• N개의 데이터를 차례대로 하나씩 확인하는 방법

이진 탐색

시간복잡도 : O(logN)

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• N개의 데이터를 절반씩 좁혀가며 데이터를 탐색하는 방법
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
• 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도는 O(logN)이다. 퀵 정렬과 공통점이다.
• 재귀함수 이용하는 방법과 반복문을 이용하는 방법
• 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보자.
• 시작점과 끝점은 모두 index를 의미한다. 
• // 기호나 int형변환은 모두 단방향(정수 부분  남김)으로 동작하기 때문에 경우를 나누지 않아도 된다.

 

• 파라메트릭 서치(Parametric Search)유형의 문제 

=> 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제를 결정 문제(예, 아니오)로 바꾸어 해결하는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 파라메트릭 서치를 사용한다. 

 

• Lower Bound & Upper Bound 

=> 일종의 이분 탐색에서 파생된 것으로, 이분 탐색이 원하는 값 k를 찾는 과정이라면

Lower Bound는 원하는 값 k 이상이 처음 나오는 위치를 찾는 과정

Upper Bound는 원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정

계수 정렬

시간복잡도 : O(N)

• 모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤에, 리스트의 인덱스에 직접 접근하여 특정한 번호의 값이 존재하는지 확인한다.

# 부품 수 입력
array = [0] * 100000

# 번호 입력받아서 기록
for i in itemNumber:
	array[int(i)] = 1