minqw5   1년 전


9

-999 -500 -200 7 33 76 455 500 800

테스트 케이스가 이럴 경우 이진탐색 & 절대값 이용해서 -500, 500을 찾아 낼 수 있습니다.

하지만 만약

9

-999 -500 -200 7 33 76 455 510 800

이렇게 될 경우 어떻게 -500과 510을 찾아내야 하나요?   이부분에서 for 문을 두 개 돌리는데 시간초과가 나는것 같습니다.

(51줄 ~ 59줄) Python3 코드.

이 경우도 이진탐색을 적용할 수 있나요?

이런 예외를 어떻게 처리해야 할지 궁금합니다



yukariko   1년 전

이진 탐색의 원리를 이용하시면 됩니다.

이진탐색은 정렬된 배열에서 범위를 반으로 좁혀가며 원하는 숫자를 찾는 알고리즘입니다.

그러면 탐색과정에서 최종적으로 숫자를 찾지 못하더라도, 끝나기 직전의 범위는 우리가 원하는 숫자가 있을 수 있는 가장 유력한 범위일 것입니다.

그러면 그 범위안에 있는 숫자가 찾는 숫자와 가장 비슷한 숫자라고 할 수 있겠죠.

그걸 이용하면 합이 0인 숫자 뿐만아니라 합이 0과 가장 가까운 숫자를 찾을 수 있습니다.

minqw5   1년 전

답변 잘 들었습니다.


다만 처음에 어떤것을 기준으로 찾아가야 하는건가요? 제 질문 2번째 케이스 예를 들어 주실 수 있으신가요? 

yukariko   1년 전

배열의 각 숫자에 대해 반복하면서 그 반대가 되는 (합이 0이 되는) 숫자를 찾으면 될 것입니다.

예를들어 -999에 대해서 999를 찾으면 되고

-500이라면 500을 찾으면 되겠죠.

하지만 999도 500도 존재하지 않습니다. 따라서 앞서말한 가까운 숫자를 찾는 과정을 통해 이를 해결하실 수 있습니다.


minqw5   1년 전

9

-999 -500 -200 7 33 76 455 507 800

이럴 경우 대략 순서가  -999에 대해 999찾아보고  -500에 대해 500 찾아보고  -200에 대해서 200 찾아보고

이런식으로 가다가  양수에서는 어떻게 판단해야하나요?  설명해주신 부분 "끝나기 직전의 범위"는  위에 있는 테스트케이스에서

어디쯤 해당하는건지 알려주시면 안될까요?

naong606   1년 전

-500에 대해 500을 이진검색으로 찾을 때 범위를 좁혀나가다 보면 
아마 [455, 507] 범위에서 500을 찾지 못하고 종료할텐데, 
이 때 455랑 507이 입력된 값들 중에 500과 제일 가까운 값들이기 때문에
-500과 더했을 때 0과 가장 가깝게 되는 두 후보가 될 것입니다.
아마 yukariko님이 말씀하신 "끝나기 직전의 범위"는 위의 [455, 507]과 같은 범위를 말하신 게 아닌가 싶네용

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