d252b   4년 전

이분 탐색 이므로 중간값으로 비교해서 

start = mid+1  혹은 end= mid -1 로 하는 것은 자명한데요.

궁금한 점은

집이

1 2 4 8 9 로 주어질 때

그 이분탐색하는 기준점(mid)가 왜 (1+9)/2 가 되어야 하나요?

현재 우리는 공유기가 설치되는 '거리' 의 최댓값을 찾고 있는 것인데

그 공유기간 거리의 최댓값과  주어진 집 사이의 거리에서의 중간값과 관련이 있나요? 


* 저는 아래 코드처럼 작성하였으나 시간초과가 떴습니다.

chogahui05   4년 전

중간값을 기준으로 반씩 나눠서 탐색하기 때문입니다.

예를 들어서

1 2 2 3 4 4 4 7 8 9 가 있다고 칩시다.

여기서 5보다 큰 최초의 위치를 찾는다고 해 볼까요?


mid는 4이므로

1 2 2 3 [4] 4 4 7 8 9 일 겁니다.

여기서 4는 5보다는 작잖아요.

그러니까 우측 구간에서 찾겠죠. 이렇게 이분탐색은 반씩 줄여가면서 찾습니다.

chogahui05   4년 전

여기서는 f(x)를 x의 간격으로 공유기를 놓았을 때

설치해야 하는 공유기의 갯수 정도로 보시면 되겠네요. 만약에 간격 x가 작아진다면 f(x)가 커지거나 같아질 게 자명하고요.

x가 커지면 f(x)가 작아지거나 같을 게 자명하네요.

d252b   4년 전


1 2 2 3 4 4 4 7 8 9 가 있다고 칩시다.

여기서 5보다 큰 최초의 위치를 찾는다고 해 볼까요?


이 부분에서 5, 즉 (1+9)/2 =5  이것이 공유기 간 거리를 나타내는 건가요?? 


chogahui05   4년 전

그렇게 이해하시면 더 헷갈리실 겁니다.

일단 f(x)를 요래 정해봅시다.


공유기간의 거리 중 최소 거리가 x 이상이여야 할 때 공유기 몇 개를 설치할 수 있을까?

1 2 4 8 9

에서 만약에 x가 4라면 이렇게 설치해야 합니다.

(1) 2 4 (8) 9


1 다음에 4에다가 설치하면 곤란하겠죠?


x가 3이라면 이렇게 설치할 수 있겠죠.

(1) 2 (4) (8) 9


x가 2라면 이렇게 설치 가능합니다.

(1) 2 (4) (8) 9


결국 이 f(x)가 감소, 또는 증가 함수네요. 이분 탐색 적용 가능하겠지요?


댓글을 작성하려면 로그인해야 합니다.