동전 뒤집기 2탄!

BOJ 2582 - 동전 뒤집기 2 링크
(2022.10.27 기준 P1)
(치팅하려는 마음 Fliiiiip!)

문제

N행 N열을 이루는 동전들이 있고 각 동전은 H(앞면)나 T(뒷면)이 위로 향하고 있다.
한 행이나 한 열을 모두 뒤집는 작업을 수행할 수 있다면, 뒷면이 위로 향하는 동전의 최소 개수 출력

알고리즘

문제 자체는 동전 뒤집기 문제와 동일. N의 최대가 커지고 시간 제한 대폭 줄었다...!

그래서 임의로 뒤집으면서 결과에 따라 확률적으로 뒤집는 값을 조정해나가는 담금질 기법을 사용하여 최대한 정답을 구하는 휴리스틱.

풀이

동전과 비트마스킹에 대한 관계와 쓰는 방법은 동전 뒤집기 풀이에 모두 있다.

난 담금질 기법 부분만 풀이를 쓸 것이다.

이 블로그와 이 블로그에서 공부를 하고 이 블로그에서 참고하여 풀었다.

담금질이란 무엇인가? 쇳덩어리를 원하는 모양으로 만들기 위해 열을 줘서 두드리는 것이다.
이와 비슷한 원리를 사용하여 최대한 답을 도출하는 방법이기 때문에 담금질 기법이라고 한다.

핵심은 p라는 확률이다. 적합도를 뒷면의 개수, 온도랑 볼츠만 상수는 0보다 크다면
p는 exp((이전 적합도 - 현재 적합도) / (온도 * 볼츠만 상수))로 구한다. (이 문제에선 적합도가 낮을수록 좋은 것이므로 저렇게 빼준다.)

그렇다면 만약 이전보다 현재가 더 좋다면?
p는 무조건 1보다 같거나 크다. 그러므로 무조건 현재 상태로 바꿔야 한다.

만약 그렇지 않다면?
여기서 중요하다. p는 0~1 사이의 실수가 되는데, 0~1 사이의 실수를 랜덤으로 하나 뽑아서 p랑 비교해보는 것이다.

무조건 현재가 더 좋을 때만 현재로 바꾸는 것이 아니라, 이전이 더 좋았더라도 일정 확률로 현재로 바꿔보는 것이다. 물론 온도를 점점 낮추면서 확률을 낮추는 것이다. 이게 바로 담금질 기법의 핵심.

쉽게 요약해서 산봉우리가 여럿 있는 산의 최정상 높이를 찾고 싶어서 무작위로 아무 방향이나 등산을 해보는 것이라고 생각하면 쉽다.
한번씩 미끄러져보기도 하고 말이다.

보통 담금질 기법에선 온도는 1로 잡는다고 하지만 문제마다 다르다고 한다. 볼츠만 상수도 임의로 적당한 값을 잡는 거라고 한다. 이 부분이 제일 모호하고 이해가 가지 않는다. 일단 난 1.0과 2.5로 잡았다. 그리고 어차피 t*k를 쓰게 되고 온도에다가 감률을 곱할 것이기 때문에 tk = 2.5 한 변수로 합쳐도 무방하다.

코드

import sys; input = sys.stdin.readline
from math import exp
from random import random, randint

def solve():
    N = int(input())
    coins = [0] * N # 앞면은 0, 뒷면은 1로 나타나는 비트로 동전 상태 저장
    for i in range(N):
        for j, c in zip(range(N - 1, -1, -1), input().strip()):
            if c == 'H':
                coins[i] += (1 << j)

    answer = N * N # 정답
    a = b = 0 # 뒤집은 열의 비트. a는 이전 유전자, b는 현재 유전자
    prev = answer # 이전 적합도
    # t = 1.0; k = 2.5
    tk = 2.5 # 온도와 볼츠만 상수의 곱

    for _ in range(5000):
        b = a ^ (1 << randint(0, N - 1)) # 어떤 열을 뒤집을지 랜덤으로 정하기
        now = 0 # 현재 적합도
        for i in range(N):
            T = bin(coins[i] ^ b).count('1') # 뒤집었을 때의 뒷면 수
            now += min(T, N - T) # 앞면이나 뒷면이나 상관없이 적은 쪽

        # 현재 유전자를 쓸 확률을 구해야 한다.
        p = exp((prev - now) / tk)
        # 이전 적합도보다 더 좋아졌으면 (현재 적합도가 더 낮아졌으면)
        # 무조건 쓰게 되고
        # 아니면 확률적으로 쓸지 말지 결정하게 된다.

        if p > random(): # 랜덤으로 0~1을 뽑아 현재 유전자를 쓸지 결정
            a = b
            prev = now

        answer = min(answer, now)
        tk *= 0.9999 # 온도 감률

    print(answer)

solve()

여담

휴리스틱은 어렵지만 꽤 재밌는 것 같다.
특히 담금질 기법은 엄청 흥미롭다. 백준에 담금질 기법 문제가 적은게 슬프다.. ㅠ