동전뒤집기 ('06 KOI)와 Simulated Annealing (담금질 기법)

(koistudy.net / acmicpc.net (Small / Large))

koistudy.net에 N<=25라고 나와있는데 실제로는 N<=32입니다. 그리고 96년 기출도 오타로 추정됩니다.

2006년 KOI 지역본선 문제로 나왔던 문제라고 합니다.
전 아직도 무슨 약을 빨고 이런 문제를 냈는지 상상도 못하겠지만

일단 풀어 봅시다.

1. brute force

제일 먼저 생각해볼 수 있는 방법은. 가로로 한번 뒤집어보고 세로로 한번 뒤집어보는 경우를 모두 다 해보는 겁니다. (가로 상태) * (세로 상태) * 개수 세기(n^2) = 이겠네요.

참 보기만 해도 기분나쁜 시간복잡도입니다.

그런데 조금만 생각해도 금방 고칠 수 있는 시간복잡도입니다.

가로를 쫙 뒤집고 난 후에 세로를 뒤집을때 굳이 2^n씩이나 되는 시간을 쓸 필요가 없습니다.

그냥 한 줄에 뒷면 개수를 샌 후, 뒤집었을때 뒷면 수 (n-뒷면수)가 작은지 뒷면의 수가 작은지를 그냥 greedy하게 고르면 돼요. 그러면 O(1)의 시간에 세로 뒤집기를 할 수 있죠.

시간 복잡도에 향상이 있었습니다. 에 문제를 풀수 있고, 이걸로 acmicpc.net에 있는 Small을 풀 수 있습니다. (소스는 생략하겠습니다. 왜냐면 애초부터 휴리스틱으로 풀어서 그런 소스가 없거든요 ㄲㄲ)

.. 하지만 32라는 정신나간 input을 처리하기엔 느리디 느린 시간복잡도라는 것을 알 수 있죠. 32는 O(2^n)으로 줄여도 절대 풀수 없는 정도의 크기입니다. 그리디나 네트워크 플로우 등을 쓰는 것도 실현가능성이 적어 보입니다. (그리디는 몰라도 네트워크 플로우는 될거 같기도 한데.. 당장 생각나는 건 없습니다. 한번 생각해보세요..)

2. Simulated Annealing

보통 휴리스틱을 쓰는 건 일반적으로 알고리즘 문제를 풀때는 "실전에서 뭐가 됐든 점수를 높일 때 쓰는 최후 수단"인데, 알고리즘 대회에서 이런 문제를 냈다니 도대체 무슨 약을 했는지를 의심할 수 밖에 없어집니다 (...) 뭐 다른 풀이가 있을 수도 있으니 약쟁이로 속단하는 건 무리가 있겠다만. 암튼 한번쯤 배워둬야 하긴 할 거 같으니 일단 한번 배워봅시다.

마치 금속을 담금질하는 것과 비슷한 원리라고 해서 Simulated Annealing(모의 담금질) 이라는 이름이 붙은 이 기법은 다음과 같은 공식에 의해 움직입니다.

엔트로피에 관련된 물리학 식을 변형한 것으로, 인자들을 설명하면

p = 확률 (새로운 상태로 바꿨을 때 이득을 볼 확률) / e = 자연상수 / E2 = 새로운 상태의 에너지 / E1 = 기존 상태의 에너지 / k = 볼츠만 상수 / T = 온도 (k>0. T>0)

이때. 상태의 에너지는 그 상태가 가지는 값을 뜻합니다. 쉽게 말해 우리가 구하고자 하는 답이죠. 이 문제에서는 뒷면인 동전의 수가 상태의 에너지가 되겠습니다.

담금질 방법은 다음과 같이 작동합니다. (rand()는 0~1 사이의 임의의 난수입니다.)

while ( k > 임계 온도 ){

E1 = 현재 상태의 에너지

E2 = 랜덤하게 생성한 새로운 상태의 에너지

p = exp((E1-E2)/(k*T));

if(p > rand()) 현재 상태를 새로운 상태로 바꿈

k *= 온도 감률 (보통 0.95 ~ 0.9999 정도)

}

과연 이런 식으로 해를 구하는 것이 왜 유효한지 case를 나눠서 살펴보도록 하죠.

A. 새로운 상태가 기존 상태보다 값이 작거나 같음 (E1 >= E2)

이 경우에는 E1 - E2 >= 0입니다. 또한 k와 T 역시 양수이므로, p는 항상 1보다 같거나 큼을 알 수 있습니다. (x>=0일경우 e^x>=1이죠.) 

새로운 상태로 바꿨을 때 무조건 이득을 본다는 것을 알 수 있습니다. 

B. 새로운 상태가 기존 상태보다 값이 큼 (E1 < E2)

담금질 기법의 핵심이라고 할 수 있습니다. 그냥 greedy한 접근법을 썼을 때는 새로운 상태가 기존 상태보다 값이 크면 무시할 가능성이 높습니다. 하지만 이러한 접근법을 사용하면 탐색 공간이 원래 해 근처로 좁혀지게 될 것입니다. 큰 값을 거쳐가야지만 최솟값이 나올 수도 있습니다. 그 때문에 담금질 기법은 큰 값에게도 변화의 가능성을 일정 확률로 줍니다. 그 확률을 계산하는 것이 위의 식이고요.

p는 온도와 볼츠만 상수에 비례하며, 새로운 상태의 에너지의 크기에 반비례합니다. 쉽게 말해서 새로운 해의 크기가 크면 클수록 확률은 낮아지고 (당연하죠. 최솟값을 구하니까) 시간이 지나면 지날수록 온도가 줄어들기 때문에 시간이 지날수록 (= 온도가 낮을수록) 변화할 확률이 낮아집니다. 볼츠만 상수는 일종의 비례상수 같은 건데 확률을 적절하게 변화시켜서 해의 정확성을 높여주는 역할을 합니다. (노가다 하셔서 적당한 값을 구하셔야 합니다.) 볼츠만 상수를 크게 잡을수록 해가 변화할 확률이 높아집니다.

상태를 어떻게 저장하는지, 랜덤한 상태는 어떻게 만드는지.. 특별히 언급해드릴 건 없지만 팁 몇가지를 드리자면

 * 이것도 역시 가로 줄만 변형을 가하고 세로 줄은 그대로 놔두는 게 좋습니다.

 * 비트 필드를 쓰면 속도 향상이 있을겁니다. 저는 해봤는데 속도향상이 없어서 안 썼지만.. 취향껏 하세요

 * 새로운 상태는 완전히 랜덤하게 섞기보다는 한줄 한줄씩 뒤집어나가는 것이 좋습니다. 랜덤 함수를 써서 뒤집을 줄을 선택한 후 그 줄을 뒤집는 방식으로요.

simulated anneling에서 중요한 것은 상수를 어떻게 정하느냐입니다. 보통 초기온도는 1로 잡는데, 그게 끝이 아니죠. 임계온도. 볼츠만 상수. 온도 감률. simulated anneling에서 필요한 인자들은 크게 다음과 같습니다.

저 중에서 임계온도는 작으면 작을수록 정확한 값이 나오지만 실행 시간이 길어집니다. 때문에, 문제의 time limit에 딱 맞는 값을 잡아주면 됩니다. clock() 함수를 쓰는 것이 가장 직관적인 방법이겠지만. clock() 함수의 동작 속도가 상당히 느린 편이며, 여러 대회에서 사용이 금지되어 있는 함수이기도 하기에, for문을 여러 번 돌리는 방식으로 대체하시는 편이 좋습니다. for(i=0;i<1000000;i++) 이런 식으로요. time limit에 안 걸리게 "잘" 돌리시는 게 중요하지만..

또한, 온도 감률이 작을 수록 온도를 빠르게 낮추므로, 변화할 확률이 빠르게 낮아집니다. 볼츠만 상수와 함께 변화할 확률을 조절하는 데 쓰실 수 있는 인자입니다.

비록 이 문제는 SA로 풀었지만, 보통은 실전이 아닌 이상 문제 풀이 모른다고 휴리스틱 때려박진 마시고. 풀이를 알아가려고 하는게 좋겠죠.. 글은 이만 마치겠습니다.