탐색-이진탐색

탐색은 주어진 데이터에서 원하는 데이터를 찾아내는 알고리즘을 말한다.
DFS , BFS , 이진탐색이 있다.

이론

📖 이진탐색

• 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘.
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교하여 데이터의 크기를 절반씩 줄여나가면서 대상을 찾는다.
• 시간복잡도 : O(logN) -----> 구현 및 원리가 비교적 간단.

💬 이진탐색 과정 (오름차순으로 데이터가 정렬되어있을경우)
1) 현재 데이터 값들 중 중앙값을 선택한다.
2) 중앙값 > 타깃 데이터 일 경우 중앙값 기준으로 왼쪽 데이터셋을 선택한다.
3) 중앙값 < 타깃 데이터 일 경우 중앙값 기준으로 오른쪽 데이터셋을 선택한다.
4) 위와 같은 과정을 반복해 중앙값==타깃데이터일 때 탐색을 종료한다.

문제풀이

📖 백준 1300 (🔗백준 1300 문제)

✏ 이진탐색 사용.
k의 범위때문에 시간복잡도가 n^2인 알고리즘은 시간초과가 발생.

✏ 2차원 리스트의 경우 n행이 n의 배수로 되어있기 때문에, 2차원 리스트에서의 k번째 수는 k를 넘지않는다.
따라서 이진탐색의 start=1, end=k로 설정한다.

✏ 중앙값을 기준으로 각 행에서 중앙값보다 작거나 같은 수의 개수는, 중앙값을 각 행의 첫번째 값으로 나눈 값이 된다. 단, 나눈 값이 n보다 클 경우 n으로 정한다.

✏ 따라서, 중앙값보다 작은 수의 개수가 k보다 작으면 시작인덱스=중앙값+1

✏ 중앙값보다 작은 수의 개수가 k보다 크거나 같으면 종료인덱스=중앙값-1

✏ 정답=중앙값 으로, start가 end보다 커질때까지 위의 과정을 반복한다.

# 이진탐색
# 2차원배열은 n행이 n의 배수로 되어있으므로, 2차원 배열에서의 k번째 수는 k를 넘지 않는다.
# start=1 end=k 로 설정.

# 중앙값 크기보다 작은 수가 k보다 작으면 시작인덱스=중앙값+1
# 중앙값 크기보다 작은 수가 k보다 크거나 같으면 종료인덱스=중앙값-1 , 정답=중앙값
 
import sys
input=sys.stdin.readline

n=int(input())
k=int(input())
start=1
end=k
result=0

while start<=end:
	mid=int((start+end)//2)
	count=0
	for i in range(1,n+1):
		count+=min(int(mid/i),n)
	if (count<k):
		start=mid+1
	else:
		result=mid
		end=mid-1

print(result)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준