[코딩 테스트] - 이진 탐색

Jeonghwan Kim·2022년 10월 11일
이진 탐색코딩테스트
0

코딩 테스트

목록 보기
9/21

이진 탐색 개요

  • 이진 탐색 알고리즘: 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 알고리즘

  • 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (단순히 데이터를 하나씩 확인하는 것)

  • 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (리스트가 정렬되어 있을 때 사용 가능), 로그 시간의 시간복잡도를 가질 수 있음

    • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함

  • 이진 탐색 동작 예시

    • 시작점, 중간점, 끝점: 인덱스

    • 찾으려는 값과 중간점 값을 비교 (중간점 값이 더 크면 중간점 오른쪽 값은 확인할 필요 없음)

    • 끝점을 중간점의 왼쪽으로 옮김

    • 다시 중간점을 찾고, 중간점 값보다 찾으려는 값이 더 크기에 중간점 왼쪽 데이터는 버림

    • 시작점 위치를 중간점 오른쪽으로 옮겨줌

    • 중간점위치의 값이 찾고자하는 값과 동일하기에 탐색을 마침

  • 이진 탐색의 시간 복잡도

    • 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례함
    • 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장함

  • 코드: 재귀적 구현

    # 이진 탐색 소스코드 구현 (재귀 함수)
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)
	# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
	elif array[mid] < target:
		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) #인덱스값에 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(원소의 개수)과 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) #인덱스값에 1을 더해 몇번째인지 프린트함

  • 파이썬 이진 탐색 라이브러리

    • bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

    • bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

  • 값이 특정 범위에 속하는 데이터 개수 구하기

    • bisect right을 통해 구한 값과 bisect left를 통해 구한 값을 빼주면 해당 값의 범위에 포함되어 있는 데이터의 개수를 구할 수 있음

      from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
	left_index = bisect_left(a, left_value)
	return right_index - left_index

# 배열 선언
a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))

# 실행 결과: 2, 6

  • 파라메트릭 서치 (Parametric Search)

    • 이진탐색을 활용하는 문제의 경우 파라메트릭 서치 유형으로 자주 나옴
    • 파라메트릭 서치: 최적화 문제(어떠한 함수값을 가능한 낮추거나 높이는 문제)를 결정 문제(’예' 혹은 ‘아니오')로 바꾸어 해결하는 기법
      • 최적화 문제를 바로 풀기 어려우면 여러 번의 결정문제를 해결하는거로 방법을 바꾸어서 해결함
      • ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
        • 탐색범위를 좁혀가며 현재 범위에서는 이 조건을 만족하는지 체크를 해서 그 여부에 따라 탐색범위를 좁혀가며 가장 알맞은 값을 찾을 수 있음
    • 코테에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결함

이진 탐색 기초 문제 풀이

<문제> 떡볶이 떡 만들기

  • 문제 해결 아이디어

    • 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복적으로 조절
    • ‘현재 이 높이로 자르면 조건을 만족할 수 있는가?’를 확인한 뒤에 조건의 만족 여부(’예’ 혹은 ‘아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있음
    • 절단기의 높이는 0부터 10억까지의 정수 중 하나
      • 큰 탐색범위는 선형탐색하면 시간초과 판정을 받을 수 있기에 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함

    • 탐색범위: 0 ~ 19, 중간점: 현재 우리가 자르고자하는 높이
    • 조건 만족 → 높이 높여보기 (시작점을 중간점의 오른쪽으로 옮김)

    • 조건 만족 → 높이 높여보기 (시작점을 중간점 보다 1큰값으로 설정)

    • 조건에 만족하지 않으므로 결과 저장하지 않음 → 중간점을 왼쪽으로 옮겨야 하므로 끝점을 중간점의 왼쪽으로 이동함

    • 조건을 만족하므로 현재의 높이값 기록(저장)

    • 이와 같이 이진탐색을 수행해서 더이상 탐색범위를 줄어들지 못하게 할 때까지 시작점과 끝점의 위치를 바꾸어 가면서 높이값을 매번 바꾸어보며 현재의 높이로 잘랐을 때 조건을 만족할 수 있는지를 체크하는 방식으로 답을 구함

    • 현재의 높이에서 잘랐을 때 필요한 떡의 크기 이상의 떡을 얻을 수 있다면 그때마다 결과를 기록해서 최종적으로 이진탐색을 더이상 수행할 수 없을때까지 반복했을 때 기록되어 있는 그 결과값을 출력하게 만듦 → 그 결과값이 최적의 높이값

    • 이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있음

    • 중간점의 값은 시간이 지날수록 ‘최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 됨

    • 코드

      # 떡의 개수(N)와 요청한 떡의 길이(M)를 입력
n, m = list(map(int, input().split()))
# 각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복적)
result = 0
while(start <= end):
	total = 0
	mid = (start+end) // 2
	for x in array:
		# 잘랐을 때의 떡의 양 계산
		if x > mid:
			total += x - mid
		# 떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 부분 탐색)
	if total < m:
		end = mid -1
	# 떡의 양이 충분한 경우 덜 자르기 (오른쪽 부분 탐색)
	else:
		result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
		start = mid + 1

# 정답 출력
print(result)

<문제> 정렬된 배열에서 특정 수의 개수 구하기

  • 문제 해결 아이디어

    • 시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있기에

      • 일반적인 선형 탐색(Linear Search)로는 시간 초과 판정을 받음
      • 하지만 데이터가 정렬되어 있기에 이진 탐색 수행 가능

    • 특정 값이 등장하는 첫번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제 해결

    • 처음 전체 탐색 범위에 대해서 이진 탐색을 두번 수행하여 하나는 첫 위치를, 다른 하나는 마지막 위치를 찾도록 만들어서 문제 해결

    • 이진탐색을 직접 구현하거나 표준 라이브러리(bisect_left, bisect_right)이용

  • 코드

    from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
	left_index = bisect_left(a, left_value)
	return right_index - left_index

n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력받기
array = list(map(int, input().split())) # 전체 데이터 입력받기

# 값이 [x,x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
	print(-1)
# 값이 x인 원소가 존재한다면
else:
	print(count)

참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상

profile
Jeonghwan Kim
이전 포스트

[코딩 테스트] - 정렬

다음 포스트

[코딩 테스트] - 다이나믹 프로그래밍

0개의 댓글