전자 코드의 문제점은 분석하신 바가 맞습니다. 후자 코드의 경우 문법적인 부분을 제외하고서라도 방법상에 많은 문제점이 보이는데요, 의도된 것인지 아닌지는 별개로 우려되는 부분들을 써봅니다.
1. 114째줄과 115째줄의 재귀호출하는 범위가 하나는 [start, mid+1) 이고 하나는 [mid, last)인데 두 범위가 mid에서 겹칩니다.
2. check함수에서 기존 인자로 받은 iterator의 대상이 되는 배열과 재귀호출로 넘기는 iterator의 대상이 되는 배열이 다릅니다.
보통은 모든 호출의 iterator의 대상을 p로 하면서, 각 check함수에서 따로 p의 해당 [s, l) 점들을 임시 배열에 복사하여 이 배열을 가지고 탐색합니다.
3. head부터 tail까지 2중 for문으로 후보 거리를 찾는데 탐색 시간을 줄이기 위해 119~121째줄에서 lower_bound를 사용한 것으로 보이나
의미를 잘 모르겠습니다. dm은 거리의 개념인데 위치를 담은 배열에서 거리를 이분탐색? 거리가 x좌표로 해석될것같은데, 음 뭔가 이상한것같습니다.
4. 결정적으로 125~132째줄에서 2중 for문을 이용하여 하나하나 다 찾아보는데에는 호출된 check의 구간 길이를 l이라 했을 때 최악의 경우 O(l^2)이 걸립니다.
(모든 점들의 x좌표가 같은 경우, 모든 점들의 y좌표가 같은 경우 등등을 고려해봤을 때.)
분할정복의 호출 횟수는 logn번이라고 하면 최종 시간복잡도가 O(n^2 logn)이 되어 시간초과가 납니다. 해당 구간의 모든 점들을 y좌표의 오름차순
(y좌표가 같으면 x의 오름차순) 으로 정렬했을 때, 자신 이후의 약 6~8개의 점까지의 거리만 보는것으로 충분하다는 것이 알려져 있습니다. 한번 찾아보시면 좋을 것 같습니다.
4hn6 3년 전 1
먼저 브루트포스로 다음과 같은 반례를 찾았습니다.
7
35 43
44 44
9 48
40 70
39 84
79 14
82 82
위 인풋의 정해는 82이고, 제 코드는 197를 출력합니다. 정해의 경우 (35, 43), (44, 44)를 선택한 것 같고, 제 코드의 경우 (39, 84), (40, 70)을 선택한 것 같습니다.
아마 제 코드는 분할정복을 하는 과정에서 중심좌표를 기준으로 왼쪽, 오른쪽 구역으로 나누었을 때 가장 가까운 두 점이 왼쪽 구역에 하나, 오른쪽 구역에 하나 있을 때 잘못된 답이 출력되는 것 같습니다.
이유는 모르겠지만 38번째 줄을 sort(point+head, point+tail, compare);에서 sort(point+head, point+tail+1, compare);로 바꾸면 위 반례 한정 정해가 나옵니다...(다른 반례들에서는 안먹히기도 함)
제가 생각한 문제원인은 함수가 재귀적으로 호출되는 과정에서 가장 가까운 두 점이 왼쪽 구역에 하나, 오른쪽 구역에 하나 있을 때를 체크하기 위해 y좌표 기준으로 정렬할때 문제가 생기는 것 같습니다.
예를들어서 1, 2, 3, 4, 5, 6이라는 배열이 존재할 때 {3, 4, 5}라는 부분을 y좌표 기준으로 정렬해야하는데 재귀호출로 인해 수행된 함수에서 이 과정을 진행하면서 배열의 자리가 바뀌어 {2, 4, 7}이런식으로 되어버려 다른 결과가 나오지 않을까 하는 생각을 했습니다.
그래서 코드를 73번째 줄 아래와 같이, 함수가 호출되면 새로운 vector pair를 만들어 그 곳에 값들을 복사하여 원본 값을 바꾸지 않도록 바꾸었습니다.
그런데 이렇게 바꿔도 여전히 위 테스트 케이스를 입력하면 오답인 197을 출력하고 있습니다...
이게 문제가 아니라면 무엇이 문제일까요?