인프런 커뮤니티 질문&답변

안녕하세요 선용님 ㅎㅎ

문제의 조건에 충족 -> ret 설정이라고 보시면 됩니다.

bool check(ll mid){
    temp = m; 
    for(ll i = 0; i < m; i++)temp += mid / a[i];
    return temp >= n;  
}

이게 이 문제의 조건을 충족하는 if - bool check 문이죠?

이걸 충족했을 때

답이 될 수 있는 값이 나옵니다.

저기 보면 "이상"이라고 되어있고 우리가 찾아야 할 직사각형을 생각하시면 됩니다.

지금 보시는 그림처럼 n이상인 것 중에서 축소해서 저 초록색 직사각형을 찾는게 우리의 과제입니다.

이상일 때 -> 축소해서 딱 저기에 맞는 ret을 찾는다. 는 것이고 코드로 나타내면

    } 
    while(lo <= hi){
        mid = (lo + hi)  / 2; 
        if(check(mid)){
            ret = mid; hi = mid - 1; 
        } else lo = mid + 1; 
    } 

이렇게 되는 셈이죠.

hi = mid - 1하면서 범위를 왼쪽으로 축소해나가죠?

right에서 mid값을 가지고오나 left를 체크할떄 가지고오나 결과는 같을거라고

>>

조건 충족되는 것 + 그 때 범위를 축소? 또는 확대할까를 생각하시면 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 이선용 님, 인프런 AI 인턴이에요.

주신 링크는 소스 코드로 이루어진 페이지인데, 문제의 구체적인 내용을 알려주시면 더 정확한 답변을 드릴 수 있을 것 같습니다. 이분 탐색에서 left와 right를 체크하는 부분에서 mid 값을 걸러내는 이해에 도움을 드리겠습니다.

이분 탐색에서 mid 값을 걸러내는 부분은 주로 탐색 대상의 범위를 좁혀나가는 과정입니다. 예를 들어, 탐색 대상이 오름차순으로 정렬된 배열이라고 가정해보겠습니다. 이분 탐색은 배열의 가운데(mid) 값을 찾아서 탐색 대상을 두 개로 분할하고, 탐색 범위를 좁혀나갑니다.

이때, left와 right는 각각 탐색 범위의 시작과 끝 인덱스를 가리킵니다. 만약 mid 값을 기준으로 찾으려는 값보다 작다면, 왼쪽 범위를 탐색해야 하므로 right 값을 mid - 1로 업데이트합니다. 반대로, mid 값을 기준으로 찾으려는 값보다 크다면, 오른쪽 범위를 탐색해야 하므로 left 값을 mid + 1로 업데이트합니다. 탐색 범위는 이렇게 하나의 경우에 따라 좁혀지는 것이며, 최종적으로 찾으려는 값을 찾거나 탐색 범위가 모두 소진될 때까지 이 과정을 반복합니다.

하지만, 정확한 답변을 드리기 위해서는 문제의 세부적인 내용이 필요합니다. 혹시 이분 탐색과 관련된 코드나 문제 내용을 공유해주실 수 있을까요? 그렇게 되면 더 정확하고 구체적인 답변을 드릴 수 있을 것 같습니다. 감사합니다!