algorithm/Meet_in_the_Middle/

[utterances-bot]

[Algorithms] Meet in the middle - 1FeS Notes

Search technique which is used when the input is small but not as small that brute force can be used

https://wch18735.github.io/algorithm/Meet_in_the_Middle/

[bluejoyq]

좋은 글 감사합니다.

[wch18735]

@bluejoyq 도움이 되었다니 뿌듯합니다! 감사합니다~!

[SeongEon-Jo]

글 너무 잘봤습니다. 감사합니다! 질문이 하나 있는데, 이분탐색 부분에서 right_idx를 len(subset_a) - 1로 설정하고,

while left_idx <= right_idx: mid = floor((left_idx + right_idx) / 2) if element_b + subset_a[mid] > C: right_idx = mid - 1 else: left_idx = mid + 1

    # right_idx -> 개수
    answer += right_idx

이런식으로 진행했는데 오답으로 뜨더라구요. 여태까지 이분탐색 진행할 때 인덱스를 저런식으로 정의해서 해왔고, 별 문제가 없었는데 혹시 이 문제에서 인덱스를 꼭 저렇게 설정해줘야하는 이유가 있을까요?

[wch18735]

@SeongEon-Jo 님, 도움이 되었다니 다행입니다!

혹시 런타임 에러 (IndexError)는 발생하지 않았나요? Python3로 제출해보니 런타임 에러가 나오네요 ㅠㅠ PyPy3 에서는 틀렸습니다가 나옵니다!

아래와 같이 작성한 코드가 오답을 받으시는 것 같는데 맞을까요?

        while left_idx <= right_idx:
            mid = floor((left_idx + right_idx) / 2)
            if element_b + subset_a[mid] > C:
                right_idx = mid - 1
            else:
                left_idx = mid + 1

        # right_idx -> 개수
        answer += right_idx

위 코드에 대해 다음과 같은 경우를 가정했습니다.

• subset_a = [1, 2, 2, 2, 3]
• element_b = 2
• C = 4

이 경우 각 while turn 마다

• mid 는 2 → 3 → 4
• right_idx 는 4 → 4 → 3
• left_idx 는 0 → 3 → 4 이 됩니다.

이때, 정답에 answer += right_idx 를 해주는데 보시다시피 right_idx 는 실제 정답 4가 아닌 3이 되는데, 이 과정에서 오답이 발생하는 것 같습니다.

즉, while 의 종료 조건 결정과 answer 업데이트 방법 문제가 원인인 것 같습니다!

인덱스를 설정하는 방법은 각자 다르겠지만, 조건을 만족하는 가장 오른쪽을 구하기 위해 저렇게 설정했습니다. 자세한 사항은 이곳 에 정리해놓았습니다!

[SeongEon-Jo]

아.. 해결했습니다. 제가 바보 같은 실수를 했네요 ㅠㅠ 저 같은 경우는 right_idx를 len(subset_a)가 아니라 len(subset_a) - 1로 해주었습니다. 그렇다보니 최종적으로 element_b + subset_a[mid] <= c를 만족하는 subset_a의 갯수는 while문을 빠져나온 후 기록된 right_idx에 1을 추가한 값이 됩니다. while문을 빠져나오고 최종적으로 기록된 right_idx는 subset_a의 right_most값의 인덱스이기 때문이죠.

left_idx = 0
right_idx = len(subset_a) - 1

# 값을 만족하는 rightmost
while left_idx <= right_idx:
    mid = floor((left_idx + right_idx) / 2)
    if element_b + subset_a[mid] > C:
        right_idx = mid - 1
    else:
        left_idx = mid + 1

# right_idx + 1 -> 개수
answer += right_idx + 1

# Works well!

지금까지 이분탐색 시 left_idx와 right_idx를 각각 0과 len(arr) - 1로 설정하고 풀어왔었는데 이 문제에서 적용이 안돼서 지금까지 내가 뭘 잘못해왔나 생각했는데 해결이 돼서 다행이네요.

좋은 풀이 잘 보고 갑니다!!! 감사합니다~