일단 간단하게 문제 설명을 하겠습니다.etaa

n(10~100)개의 점들 사이에 e(=n*2~n*5)개의 엣지를 복잡한 방법에 따라(설명이 주어져 있지만 문제 푸는데 큰 상관은 없습니다) 연결한다. 엣지들은 점들을 일직선으로 연결해야 한다고 할 때, 주어진 n개의 점을 평면상에 적절히 배치하여 엣지끼리 겹치는 수를 줄여라!

제 경우에는 문제를 보고 바로 생각했던 해법이 결국 제출한 답안이 되었습니다. 점들의 위치를 바꿔가면서 SA를 돌리는데, 엣지가 겹치는 정도에 따라서 가중치를 줄 수도 있도록 하자... 이 가중치는 실제로는 쓰이지 않았지만 말이죠. 실제 프로그래밍은 끝나기 10일쯤 전에 시작하긴 했지만, 다른 방법도 그닥 없어보였습니다.
서밋 1(76점)에서 일단 로컬 미니멈을 찾아보고, SA를 적용하자 서밋 2에서 점수가 바로 92점으로 뛰었습니다. 그 이후에는 SA의 iteration 수를 늘리기 위한 최적화 작업과, 랜덤한 점을 선택하는 데 있어서 약간의 확률 변화를 주는 정도의 작업만 계속했던 것 같군요.
이 문제는 제가 20위를 차지했던 MM26과 문제 설명/풀이 방법이 아주 유사하였습니다. 당시의 경험이 큰 도움이 되어서, 당시에 1주일 걸려서 했던 일을 이틀 정도만에 다 끝냈습니다. 이 범주에 들어가는 일은...

• 테스트 환경 만들기와 비쥬얼라이져 체크입니다. MM을 여러번 하다보니 시간이 그리 많이 걸리지 않습니다.
• SA의 온도 조정은 빠른 수렴에 좀 못미칠 정도로 느리게 떨어지게 하는 것이 좋습니다. SA에서 가장 중요한 것은 로컬 미니마를 탈출하는 것입니다.
• 작은 n에 대해서는 시간을 최대한 사용해 한번의 SA를 돌리는 것보다는 여러 번의 SA를 돌려서 그 중에서 가장 좋은 값을 찾는 것이 좋습니다. 이를 위해서 n 크기별 SA iteration 횟수와 해답의 좋은 정도의 관계를 실험을 통해서 알아보아야 할 것입니다.
• 같은 데이터에 대해 SA를 여러번 돌려 보았는데 결과가 크게 다르다면, iteration을 많이 늘리고 온도를 느리게 떨어지게 해 보세요. 결과가 좋아지는 것은 당연한데, 편차가 작아진다면 그냥 iteration 수를 늘려야 하고, 편차가 커진다면 여러 번의 SA를 돌리는 것이 더 좋을 수 있습니다. 또한, 다른 종류의 흔들기 방법을 찾아내서 로컬 미니마에 좀 덜 빠지게 만드는 것도 생각해야 합니다.
• SA의 특성상, iteration 수를 최대한 늘릴 수 있는 방법을 고려해야 합니다. 여러 개의 점을 동시에 움직여본다면 로컬 미니마를 탈출할 수 있는 확률은 높아지겠지만, 점 하나만 움직이면 O(E^2/V) ~= O(E) 정도의 시간을 들여서 다음 값을 계산할 수 있으므로, 일단 그렇게 했습니다. 점 두 개까지 움직이는 것도 시도해 보았습니다.
• L2 cache(탑코더 서버의 경우 512K~1M으로 추정됨)의 크기를 고려하여야 합니다. precomputing으로 퍼포먼스 증가를 얻을 수 있다고 해도 메모리를 많이 써서 캐쉬 범위를 벗어난다면 오히려 손해입니다.

MM26에도 했고 이번에도 비슷하게 수행하였거나 좀 더 잘 수행했다고 생각하는 것들입니다.

• 중요 함수의 시간 단축을 해 보았습니다. 크로스 체크를 위해서 각 엣지는 시작점+벡터 식으로 저장합니다. 이렇게 저장해놓아야, 크로스 체크시 오퍼레이션 수가 크게 줄어듭니다.
한 점의 위치를 바꾸는 방법을 여러 가지로 수행해보았습니다. 시간이 지나면서 점이 움직이는 범위를 줄여나간다거나, 연결된 다른 점들의 무게중심을 고려한다거나... 뭐 이런 것들을 해 보았습니다. (탑 랭커들 사이에 가장 효율이 좋은 방법이어썯ㄴ 연결된 다른 점들 중 하나를 골라서 그 쪽으로 이동해본다... 는 아쉽게도 해 보지 못했습니다.)

• iteration 수를 많이 늘리는 방법으로 선수조사를 실시해보았습니다. 각 iteration에 대해서 O(E)개의 엣지 크로스를 조사해보아야 하는데, 일부분만 조사해서 엣지 크로스 수가 SA 범위를 벗어나게 늘어나는 경향이면 바로 다음 iteration을 실행하도록 했습니다. 이 방법으로 2~3배 이상의 iteration 증가를 맛보았다능... 2배의 iteration 증가에 대략 +0.7점 정도가 되었던 듯 합니다.
• 프로파일링을 해 보았습니다. 이 문제는 결국 엣지 두개의 cross check에서 대부분의 시간을 소모합니다. 어느 정도 최적화를 하여 95점대로 올라선 이후 프로파일링을 해 보았는데, cross check에서 40%, 선수조사(cross check 제외 loop)에서 30%, 선수조사 뒤 실제 계산 (cross check 제외 loop)에서 30%의 시간을 소모하였습니다. 선수조사 loop 안에서의 계속적인 랜덤함수 호출이 문제인 것으로 밝혀져, 이 부분을 랜덤함수를 훨씬 덜 사용하게 바꾸자 이 부분에서의 시간 소모가 1/3 미만으로 줄었습니다. 나이스~~~ 대략 0.3점 정도 올랐습니다.
• 중요 함수의 성능 개선 시, CPU가 branch를 처리하는 구조를 고려합니다. if-branch가 발생할 경우 둘 다 따라가보고 branch의 평가 결과에 따라 한 쪽을 따라가는 것으로 알고 있습니다... 만 어쨌든 branch가 있는 경우에는 연속된 operation을 동시에 수행하지 못합니다. 따라서 branch의 사용은 최소화하였습니다.
• SA 평가함수 자체를 이리저리 바꿔보았습니다. 원래는 엣지-엣지가 겹치는 갯수가 평가함수 자체인데, degree가 큰 점들 사이에 연결된 엣지에는 가중치를 좀 더 준다거나, 거리가 먼 엣지가 겹치는 데에도 가중치를 더 준다거나, 이런 식으로 해 보았습니다. 아쉽게도 계산의 overhead를 극복하는 정도의 해법은 없었습니다.
  

가능한 방법으로 조사했으나 실제로 구현해보지는 못한 방법입니다.

• SSE2 사용입니다. Psyho의 SRM 코드라거나 검색한 문서를 보고 구현해보려고 노력했으나 시간이 그렇게까지 많지는 않았습니다. 적어도 R3에서 Onsite로 진출하려면 반드시 필요한 것이 아닌가 생각합니다.

몰라서 사용하지 못한 방법입니다.

• gsais(였나...)의 cross check function은 branch가 없습니다. 이것이 현대 cpu 아키텍쳐에서는 초고효율을 발휘한다고 하던데, 정말 그런지 모르겠네요. 한번 조사해봐야 할 것 같습니다. gsais가 맞다면 맞는거죠 뭐...
• alegro가 L1 cache(16K? 32K?)만 사용하기 위해 데이터를 bitmap으로 저장해서 몰아버렸다고 하는데, trade-off를 감안하면 정말 좋은 건지 모르겠습니다. alegro가 맞다면 맞는거죠 뭐...

다음은 반성할 점입니다.

• 최적화를 너무 일찍 시작했습니다. 대략 6일쯤 전에 시작했는데, 2-3일간 더 방법을 연구해보고 나서 최적화를 시작했어야 합니다. 최적화 방법은 솔루션과 밀접하게 연관되어 있기 때문에, 일단 최적화를 빡세게 하게 되면 방법을 바꾸기란 쉬운 일이 아닙니다.
• SSE2를 적용하려면 branch가 적어야 합니다. 코어 코드는 최대한 짧게 짜야 합니다. edge-cross check에서 branch를 두개 정도 사용했는데, 아예 사용하지 않거나 하나 정도만 있는 방법을 찾아냈으면 어떨까 합니다.
• 관련된 문제인 MM26/TCO08 R1 포럼을 찾아보는 것이 너무 늦었습니다. 좀 더 빨리 찾아봤으면 iteration을 늘리거나 점을 움직이는 방법에 대한 아이디어들을 적용해볼 수 있었을 것 같습니다.

R2에 무슨 문제가 나올지 모르지만, R1보다는 복잡한 문제가 나옵니다. 다음은 R1에서의 교훈과 R2에 대한 대비책입니다.

• 일단 첫 구현이 중요합니다. 구현했으면 일단 제출해봅시다. 고민만 하는 것보다 낮은 점수의 솔루션 제출이 훨씬 미래를 위해 도움이 됩니다.
• 최적화로 점수를 올리는 데는 한계가 있습니다. 수행 시간과 점수와의 관계를 대략 파악해보고, 10배 속도 개선을 해도 목표에 미치지 못하는 정도라면, 완전히 다른 방법을 찾아봅시다.
• SA는 메인 방법으로도 쓰일 수 있지만 적절히만 끼얹는 것이 좋을 수도 있습니다. 예를 들어서 뻔히 보이는 어느 정도 좋은 해법이 있다면, 완전한 랜덤 SA는 좋지 않을 수도 있습니다. 사용처를 잘 파악해봅시다.
• 데이터 생성 방법에는 큰 미련을 갖지 맙시다. 최적해를 찾아내려고 하는 것은 대부분의 MM에서는 좋은 방법이 아닙니다.
• 문제 설명이 복잡한 문제의 경우, 특정 파라미터에 따라서 방법을 달리 적용해야 하는 문제가 있습니다. 데이터의 양쪽 극단을 동시에 처리할 수 있는 방법이 있다면 좋겠지만, 없다면 적절히 하이브리드 형태로 풀어야 하겠습니다.
• R3 이후를 위해 SSE2를 공부하고 한 군데라도 실제로 적용해봅시다.

R2가 시작되면 문제에 대한 풀이 방법은 공유하지 못하기 때문에, 서로의 도움을 받을 수가 없습니다. 이러한 일반적인 내용이라도 읽어보시 고 도움이 되시길 바라며, 오늘 밤부터 시작되는 R2에서 좋은 성적을 거두시기를 바랍니다!

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

14년 전