1. return값이 Left가 된다는 부분 자체는 사람들마다 구현이 다르기 떄문에.. 굳이 큰 의미를 둘 이유는 없다고 생각합니다.
저도 다른 분들의 이분탐색 코드를 읽을 때는 시간이 좀 걸리는 편입니다.
다만, "cnt >= k인 가장 작은 숫자"를 탐색하고 있다는 사실만 잘 염두에 두고 코딩하신다면 문제 없을 거라고 생각합니다.
2. 생각하신 것이 맞는 것 같습니다.
추가로 N*N을 기준으로 탐색하면 long long 변수를 써야하는 귀찮음도 있을 것 같습니다.
* 여기에 더해서 드리는 말씀인데, 위 코드에서 cnt 변수에 overflow가 발생할 가능성이 없을지는 한번 확인해보시는게 좋을 것 같습니다.
아마 발생하지 않을 것 같긴 한데, 명확하게 증명해 보는게 좋겠죠..
3. 이런 방법을 처음 볼 때는 아마 누구라도 생각하기 어려울 것 같습니다.
이 문제처럼 답을 정해놓고 그 답이 가능한지 이진탐색하는 종류의 문제들을 Parametric Search라고 합니다.
사람들이 이 문제를 잘 생각하는 건, 어떻게 보면 이런 종류의 문제가 수십개씩 있었기 때문이라고도 생각되네요.
다음에 이런 문제가 나왔을 때 이 아이디어를 떠올릴 수만 있으면, 그것만으로도 잘 배우신 것이 아닐까요?
결국 그런 지식들과 응용할 수 있는 능력들이 모여서 실력이 쌓이는 거라고 생각합니다.
kioio5 7년 전 8
너무 어려워서... 블로그 돌아다니면서 공부했습니다...
사실 아직도 정확히 이해가 안가네요...
의문점 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보다 작은 수의 갯수를 셀 수 있습니다.