jamescsi   7년 전

이분법으로 푸는건 알겠고 어떤식으로 임의의 숫자 이하의 숫자를 세는지도 알겠는데 여전히 이분탐색하는 부분이 잘 이해가 안가네요.

왜 종료조건이 left<=right 이며 k랑 cnt가 같을때도 왼쪽반을 또 보는지 모르겠어요. 카운트랑 k랑 같아지면 바로 종료해도 되는거 아닌가요? mid이하의 숫자가 총 k 개 있다는데... 배열에 k개 이하의 숫자가 있으면서 k번째 숫자가 아닐수가 있나요? ㅠㅠ 읽어주셔서 감사합니다.

DryType   7년 전

이분탐색은 개인마다 코드가 조금씩 차이가 있더라구요... 본인 방식대로 하시면 됩니다.

K랑 같아도 왼쪽편으로 다시 가는 이유는 N에 따라 나올수 없는 수가 있는데 이 수를 제외시키기 위해서 인것 같습니다

예를들어 N = 3, K = 8일때 mid가 7인 경우 cnt는 8이됩니다.  이때 답을 출력하면 7은 나올수가 없는 경우이기 때문에 오답이 됩니다.

jamescsi   7년 전

감사합니다~

sevity   4년 전

while(left <= right) 이거랑, right=mid-1, left=mid+1; 이거는 정수에 대한 이진탐색을 할때 일반적으로 코드가 깔끔하게 나오기 때문에 공식처럼 쓰시는 분들이 많습니다.

해당형태로 공식처럼 외워서 쓰는게 아니면, 인티저의 특수성 때문에 무한루프에 빠지는 곤란한경우가 자주 생기거든요.

그래서 일단 공식처럼 틀에 맞춰서 이진탐색을 구현하고, 나머지는 문제에 맞게 변형해서 풀다보니 저런 코드가 많은거라 생각해봅니다.

저도 저런식으로 항상 짜기때문에 같은형태가 나와서 말씀드려봤어요 :)

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