문제가 처음에는 K개의 그룹으로 나눈다고 주어져있기 때문에 좀 막막해보인다. 근데 끝까지 읽으면, K가 최대 2라는 제한이 주어진다.. 이럴거면 그냥 처음부터 한개나 두개의 두룹으로 나눈다고 설명해주면 안되나..
K가 1일때는 그냥 저 식에 넣어서 계산만하면 되는 단순한 구현 문제가 된다.
K가 2일때만 생각해보자.
우선 문제에서 주어진 메져 펑션은 통계학이나 머신러닝에서 흔히 쓰이는 k-means clustering 에서 쓰이는 그것이다.
저렇게 나눌 때의 디시전 바운더리는 항상 리니어하다는 것을 알고 있다. 이 문제는 데이터가 3차원이고 클러스터가 2개이므로, 어떤 평면을 기준으로 점들을 두 그룹으로 나누는 경우중에 옵티멀이 존재하게 된다.
그럼 이제 단순하게 평면을 기준으로 점들을 나누는 모든 경우의 수를 다 처리해보는 것을 생각해볼수 있다. 이것은 점 3개를 잡아서 만들어지는 모든 평면들을 갖고 나눠보는 것만으로 충분하다.
-
그러면, 평면의 갯수는 nC3개이고, 평면을 하나 잡을때마다 n개의 점의 그룹을 찾아줘야 하므로, 총 O(n^4) 알고리즘이 만들어진다.
주의할 점은, 평면 위에 올라가 있는 3개의 점은 어느 그룹으로 보낼것인가이다. 단순한 방법은 2^3개의 경우의 수를 모두 따져보는 것인데. 더 효율적인 방법은 찾지 못했다. 시간복잡도 상으로는 차이가 없다.
분산을 계산할 때에는 주어진 공식으로 구하는 것 보다 조금 더 효율적인 방법이 있다. 주어진 공식에서는 먼저 평균을 구한 뒤에, 각 점과 평균과의 차이의 제곱을 더해서 구하게 되는데, 평균값은 실수형으로 나오기때문에 모두 실수 연산을 해줘햐 한다. 대신 V(X) = E(X^2) - E(X)^2 공식을 이용해서 계산하면, 마지막 과정을 제외하고는 정수 연산만으로 처리할수 있기 때문에 조금 더 효율적이다
이렇게 구현한 O(n^4) 알고리즘은 python3 에서는 제한시간 5초안에 돌아가지 않는다. 실질적으로 O(n) 작업을 nC3번 하는거라 (n^4)/6 정도이고 n<100 으로 작은 편이지만 안 돌아간다.. PyPy3을 사용해서 2200ms 정도에 통과했다. 코드를 좀더 최적화할 여지는 꽤 있긴 한데, 그렇다 하더라고 python3에서 통과시킬정도로 빠르게 만드는 것은 불가능할것이라고 생각된다.
아까는 PS적인 마인드로 기하학적인 접근을 시도해서 풀었었는데, 아예 다른 접근방식을 생각해보자.
처음 말했듯이, 이것은 ML에서의 기초 개념인 k-means clustering에 해당되고, 이것을 푸는 알고리즘도 매우 많이 연구되어있다.
다만 PS에서 이런 것들을 잘 다루지 않는 것은, 이들은 이터레이션을 돌면서 수렴시키는 방식으로 이루어지고, 그 과정에서 local optimum으로 빠질 가능성이 존재하기 때문이다. 이것을 방지하기 위해서 보통 시작점을 바꿔가면서 여러번 돌리는 방식으로 처리하는데, ML쪽에서는 이렇게 해서 어느정도 수준 이상의 답을 찾으면 그것으로 충분하지만, PS에서는 global optimum을 찾는 것을 목표로 하기 때문에 잘 어울리지 않는다.
하지만, 여기에서는 k와 n이 매우 작은 편이기 때문에, 시작점을 바꿔가면서 돌리는 것을 매우 많이 시도함으로써 global optimum을 찾을 수 있었다.
모든 O(n^2)가지의 포인트 페어에 대해서, 각각을 초기 센트로이드값으로 잡고 k-means clustering 을 돌려보았더니, 정답을 찾을수 있었다.
-
k-means clustering 을 한번 돌리는데에는 O(n*k) (k는 이터레이션 횟수)가 걸리고, 이것을 O(n^2)개의 시작점에 대해서 반복하므로, 총 시간복잡도는 O(n^3*k) 정도가 된다. 수렴할때까지의 이터레이션 횟수는 예측 불가이기 한데.. 제출해본 결과 PyPy3에서는 430ms 정도가 걸렸고, python3에서도 3600ms로 통과되었다!