과제 2

[문제]

  좌표평면에 있는 유한 개의 점들 중 최단거리인 쌍 구하기

 

→ 유한 개의 점 P0, P1, P2, ..., Pn-1이 있을 때, 이들 중 가장 거리가 가까운 두 점 Pi와 Pj를 찾아서 그 두 점의 거리를 반환하는 함수 구현 (단, 0 <= i < j < n )

 

→ 좌표 정보를 저장하는 클래스가 이미 구현되어 있는 상태. (by. 교수님)

 

[해결]

  모든 점의 쌍들의 거리를 일일히 구해서 구하는 방법도 있지만 비효율적. 과제 설명 당시 교수님께서 주신 힌트를 그대로 구현하여 해결하였다.

 

교수님의 설명은 대충 이러함. (나중에 그림으로 정리함...)

→ 분할 정복을 사용하되, 일반적인 분할 정복을 사용하여 풀면 안 됨.

→ 좌표평면 상의 점들을 두 부분으로 분할해나가며 각 부분 속의 점들 사이 거리를 구한다. 이 때, 분할된 각 부분마다 각자의 최단거리가 나올 것.

→ 부분 최단거리를 구하였다면, 이 최단거리를 d라고 하였을 때 중앙으로부터 양쪽으로 각각 d만큼 떨어진 거리 사이에 있는 점들의 거리를 구하여 d와 비교한다.

 

  말이 어렵지 그림으로 그려서 보면 간단한데... 일단 교수님이 설명한 건 저 정도. 딱 저 정도로 설명하셔서 나머지 구현에 대해선 내맘대로 진행했다.

 

→ 분할 : 유한 개의 점 쌍은 무작위로 주어지므로, 분할을 하기 위해서는 주어진 점들을 정렬할 필요성이 있음. 따라서 점들의 x좌표를 기준으로 정렬을 진행하고 Merge sort를 사용함. 분할은 정렬이 끝나고 진행.

→ 정렬 후 최단거리 구하기는 위의 설명대로 진행. 저 중앙의 인덱스 값을 어떻게 정할지 고민했었는데 (별 설명 없어서...) 그냥 내맘대로 left와 right의 절반값으로 했음. (그리고 별문제 없었음.)

 

코드는 내일 올리기...