kd-tree

친구의 블로그에서 글을 읽다가 문제 하나를 봤습니다.
x와 y좌표를 가진 N개의 점들이 있는데, 원점에 가까운 10개의 점을 무려 O(n) 시간으로 찾으라는 무지막지한 문제. 해결 자체는 kd-tree로 가능하지만, O(n) 이라면 kd-tree가 답은 아니겠군요. kd-tree 생성에만 O(n*log(n))이 걸린다던데. 설마 넌센스인가?
근데 시간 복잡도를 제외하면, 예전에 자료구조 혹은 알고리즘 시간에 교수님이 냈던 과제랑 같은거 같네요. 그 땐 무식하게 푼 기억이 어렴풋이 납니다.

kd-tree

컴퓨터 과학에서 kd-tree는 k-차원 공간에 있는 점들을 조직하기 위한 공간-분할 데이터 구조입니다. kd-tree는 다차원 공간 탐색 키를 사용하는 탐색과 같은 응용에 유용한 데이터 구조입니다.(예를 들어, 범위 검색과 근접 검색). kd-tree는 BSP tree의 특별한 경우입니다.

kd-tree는 모든 노드(Node)가 k-차원의 점인 이진 트리(Binary tree)입니다. 리프(Leaf)가 아닌 모든 노드는 공간을 두 개의 작은 공간들(Subspaces)로 나눈 분리 경계면(초평면, Hyperplane)을 만듭니다. 분리 경계면 왼쪽의 점들은 노드의 왼쪽 서브 트리(Sub-tree)를 나타내고, 오른쪽의 점들은 오른쪽 서브 트리를 나타냅니다. 분리 경계면의 방향은 다음의 방법에 의해 선택됩니다. 서브 트리에 의해 쪼개진 모든 노드는 k-차원들 중 하나와 연관 됩니다. 분리 경계면은 방향 벡터에 수직입니다. 예를 들면, 선택된 x축으로 나뉘어진다면, x값보다 작은 서브 트리의 모든 점들은 오른쪽에 나타나고, x값 보다 큰 값들은 오른쪽 서브 트리에 나타납니다.

출처: http://en.wikipedia.org/wiki/Kd_tree

100 - The 3n+1 problem

아무리 4만명 가까운 사람들이 풀었다고 해도 이건 너무 하잖아. -_-; 업데이트한 날짜라도 좀 적어주던가. 마음대로 바꾸고 쳇. 일단 Accepted 는 받았으니, 다음 문제로~! (재도전하고 싶은데 12시가 넘어 버렸다.)

"The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line)."

결론은 입력 순서를 지켜서 출력하라는 거다. 예를 들어, 10 1 이라고 입력이 들어오면, 10 1 20 으로 출력해달라는 이야기. 문제 좀 읽읍시다!

그나저나 XCode 로도 컴파일 할만 한데, 이쁜 맥뿌기, 부기부밥 맥뿌기밥~!