kioio5   4년 전

너무 어려워서... 블로그 돌아다니면서 공부했습니다...

사실 아직도 정확히 이해가 안가네요...

의문점 1.. return값이 왜 left일까요...

cnt >= k 같을 경우 mid를 임시로 저장해서 끝까지 탐색한 다음 임시로 저장한 값을 출력하는 건 이해가 가는데

left가 결국 결과값이 되는 부분은 이해가 안가네요.


의문점 2.. 어째서 right에 n^2이 아닌 k를 넣는건지 잘모르겠습니다..

음.. 당연히?? k가 내가 찾는 수 보다 크기 때문에 불필요한 탐색을 줄이기 위함일까요????


세번째 의문... 이 방법을 어떻게 사람들은 생각한걸까요.. 천재일까요 T__T..머리가 너무 부럽네요..

처음에 if(cnt == k) return mid;가 왜 아닌가에 대해서 고민했는데...

i*j로 표현할 수 없는 수가 있을 수 있다고 하는데... 이것 또한 어떻게 ..생각하는 걸까요..후..

아참... 이분탐색에서 for문을 돌리는 이유는 mid값보다 작거나 같은 수를 체크하기 위함입니다.

mid / i와 n의 크기를 비교해서 작은 값을 쓰는 이유는 예를들어 n이 4라면 테이블이 아래처럼 만들어질 것입니다.

 1  2  3  4

 2  4  6  8

 3  6  9 12

 4  8 12 16

mid가 만약 6이라면 i == 1일 때 n = 4와 6 / 1 을 비교하게 됩니다.

하지만 1의 배수 중에 가장 큰 수는 4이므로 6개가 될수 없습니다.

그렇기 때문에 1의 배수 중에서 6보다 작은 수는 4개가 되겠죠.

마찬가지로 i == 2일 때 2의 배수에서도 6보다 작거나 같은 수를 찾습니다.

6/2를 하면 2, 4, 6이 포함되는 3이되겠죠.. 그렇게해서 3개

i == 3일 땐 같은 방법으로 3, 6을 포함한 2개

i == 4일 때는 4를 포함한 1개입니다.

총 카운트는 4 + 3 + 2 + 1 = 10 입니다.

이렇게 함으로써 mid보다 작은 수의 갯수를 셀 수 있습니다.

dotorya   4년 전

1. return값이 Left가 된다는 부분 자체는 사람들마다 구현이 다르기 떄문에.. 굳이 큰 의미를 둘 이유는 없다고 생각합니다.

저도 다른 분들의 이분탐색 코드를 읽을 때는 시간이 좀 걸리는 편입니다.

다만, "cnt >= k인 가장 작은 숫자"를 탐색하고 있다는 사실만 잘 염두에 두고 코딩하신다면 문제 없을 거라고 생각합니다.


2. 생각하신 것이 맞는 것 같습니다.

추가로 N*N을 기준으로 탐색하면 long long 변수를 써야하는 귀찮음도 있을 것 같습니다.

* 여기에 더해서 드리는 말씀인데, 위 코드에서 cnt 변수에 overflow가 발생할 가능성이 없을지는 한번 확인해보시는게 좋을 것 같습니다.

아마 발생하지 않을 것 같긴 한데, 명확하게 증명해 보는게 좋겠죠..


3. 이런 방법을 처음 볼 때는 아마 누구라도 생각하기 어려울 것 같습니다.

이 문제처럼 답을 정해놓고 그 답이 가능한지 이진탐색하는 종류의 문제들을 Parametric Search라고 합니다.

사람들이 이 문제를 잘 생각하는 건, 어떻게 보면 이런 종류의 문제가 수십개씩 있었기 때문이라고도 생각되네요.

다음에 이런 문제가 나왔을 때 이 아이디어를 떠올릴 수만 있으면, 그것만으로도 잘 배우신 것이 아닐까요?

결국 그런 지식들과 응용할 수 있는 능력들이 모여서 실력이 쌓이는 거라고 생각합니다.

kioio5   4년 전

@dotorya

아.. 고수분께 또 한수 배웠습니다!!!

감사합니다 !!!!!!!! 열심히 공부하겠습니다.!

chogahui05   4년 전

전 (10^5)log(10^10)의 복잡도로 풀었습니다.

도무지 (10만)log(10만)의 아이디어가 안 떠올라서요.


보통 이분 탐색 문제는..

대놓고 이분탐색으로 푸세요~ 라고 주어지는 경우도 있는데요.

이 문제처럼 몇 번 꼬아서 내거나. 자기가 이분탐색이다~ 라는 걸 숨기는 경우도 있더라고요.


이분탐색이 간단한 알고리즘이지만요. 극단적으로 어려워지면 이런 식으로 나오더라고요.

https://www.acmicpc.net/proble...


저는 이렇게 풉니다.

(1) 함수를 만들어 봅니다.

(2) 이것이 항상 증가, 혹은 항상 감소하는 것인지 따져봅니다.

(3) 만약 그렇다면 반씩 쪼개서 풀어봅니다.


(1)이 가장 어려운 거 같아요.

kioio5   4년 전

chogahui05 


@chogahui05 아!!!감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!! 단어검색도 꼭 풀어보겠습니다!!! 진짜 감사합니다 !><

sevity   1년 전

리턴값이 left인것은 아마도 중복되는 숫자들이 있을 경우 가장 왼쪽의 lower_bound가 답이기 때문일것 같습니다.

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