책 이야기

이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 P_n을 생성하자:
S₀=290797
S_n+1=S_n² mod 50515093

P_n=(S_2n,S_2n+1)

P₀,⋯,P_k-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.

소숫점 9자리까지 나오도록 반올림하여  d(2000000)을 구하시오.

--------------------------------------------------------------------------

번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.

초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.

다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.

하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n²)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.

몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.

전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.

−1000≤x,y≤1000인 좌표평면 위에 임의의 점을 3개 찍으면 삼각형을 만들 수 있다.

다음 두 삼각형을 생각해 보자:

A(−340,495), B(−153,−910), C(835,−947)

X(−175,41), Y(−421,−714), Z(574,−645)

삼각형 ABC에는 원점이 포함되지만, 삼각형 XYZ에는 원점이 포함되지 않는다.

27K 크기의 triangles.txt (우클릭하고 다른 이름으로 저장)에는 1,000개의 임의의 삼각형 좌표가 있다. 원점이 삼각형 안에 엤는 경우는 몇 개인가?

--------------------------------------------------------------------------

해결할 아이디어가 떠오르지 않아 찾아보니 고1 정도의 수학 지식을 필요로하는 문제였다. 벡터를 이용, 삼각형 면적 이용, 도형(삼각형)과 교차하는 점의 갯수, 무게중심좌표 등 해결하는 방법은 몇 가지가 있는데 개념은 알겠는데 실제 어떤 형태로 구현할 것인지는 쉽지 않았다.

이 중 무게중심좌표(Barycentric Coordinate System)를 이용한 해법으로 답을 구했다. 삼각형 세 꼭지점의 좌표를 (x1,y1), (x2, y2), (x3, y3)라 하고, 원점을(xp, yp)라 할 때, 다음과 같이 세 좌표를 계산해서 모두 0보다 크면 삼각형 내부에 있다고 한다.

alpha=((y2-y3)*(xp-x3)+(x3-x2)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))

beta=((y3-y1)*(xp-x3)+(x1-x3)*(yp-y3)) / ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3))

gamma=1.0-alpha-beta

왜 그렇게 되는지는 이해 못했지만 위 내용대로 구현하니 답을 구할 수 있었다.

그리고, 왜 이렇게 난이도가 올라갈까 싶었는데, 게임을 할 때 특정 좌표가 도형 내에 있는지 밖에 있는지 판단하는 방법으로 이 코드를 사용할 수 있다고 한다. 좌표가 보호막 내에 있는지 판단하거나, 게임 내의 비행체와 총알의 충돌을 판단하는 등에 사용할 것을 생각하면 이해가 필요한 것 같다.