[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 2582 동전 뒤집기 2

https://www.acmicpc.net/problem/2582

2582번: 동전 뒤집기 2

 

2582 동전 뒤집기 2

알고리즘 : 휴리스틱(시뮬레이티드 어닐링)

시뮬레이티드 어닐링을 처음 공부할 때 풀었던 문제입니다. 첫 공부 시 다른 사람의 소스를 분석하여 풀이하느라 유사한 점이 많습니다. 밑 코드에서 주석으로 표기하였으니 이해하시는데 도움이 되었으면 좋겠습니다.

핵심 풀이 시 이해하여야 하는 것은 해당 줄에 앞면이 많은지 뒷면이 많은지는 중요한 것이 아니라 앞뒷면 수의 차이가 중요합니다

(최저 행동 수를 구하는 문제가 아니기 때문)

이를 이해하면 코드를 쉽게 이해할 수 있습니다.

 

 

 

< CODE >

#include <iostream>
#include <random>
#include <stdlib.h>
#include <ctime>
#include <cmath>

using namespace std;

typedef long long ll;

int n;
ll arr[33]; // long long형의 입력받는 배열

int main() {
    random_device rd; // seed값
    mt19937 mt(rd()); // 랜덤을 쓰겠다는 것

    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    uniform_int_distribution<int> ran(0, n - 1); // uniform_int_distribution (int중에서 뽑는 데이터 타입, 종류 여러가지)

    // 여기까지 준비과정

    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            char c; cin >> c;
            arr[i] <<= 1;

            if (c == 'H') 
                arr[i] |= 1;

            // 한칸씩 밀면서 처음 넣는걸 가장 왼쪽 비트에 저장하는 방법
        }
    }

    int ans = n * n;  
    int a = 0, b = 0; // a,b는 유전자, a는 이전 계산 유전자, b는 이번 계산 유전자
    int prv = n * n; // prev, now 랑 set, 둘 다 적합도 함수, prev는 이전 적합도 now는 지금 적합도
    double t = 1.0, k = 2.5; // t - 온도(무적권 1.0) , k - 볼트만 상수(하면서 조절, 높을수록 )

    for (int i = 0; i < 10101; i++) 
    { // 시간초과 안 날 정도로 반복 설정
        b = a ^ (1 << ran(mt)); // ran(mt) - ran에서 지정한 범위에서 뽑느거 (가로를 뒤집는 다는 것)

        int now = 0; // b의 적합도 함수

        for (int j = 0; j < n; j++) 
        {
            int h;
#if defined(_MSC_VER)
            h = __popcnt(arr[j] ^ b); // __builtin_popcount(gcc에서 사용하는 것, msvc에서는 __popcnt를 사용해야함) 해당 arr[j]의 앞면 수 세기(뒤집히거나 유지한 후) ,b는 i번째 비트를 가지고있을때 i번째 가로줄을 뒤집는다는 뜻
#else
            h = __builtin_popcount(arr[j] ^ b);
#endif

            now += min(h, n - h); // 가로줄들의 뒷면 수의 합 (앞면이여도 상관이 없는게 그 줄을 뒤집으면 그만임)
        }
        double nowP = exp((prv - now) / (k * t)); // b랑 now를 쓸 확률, prev-now 현재상태가 더 호전됐으면(높은경우는 반대로)
        // exp^0보다 크면 1보다 크게 나옴, 그래서 확률이 1이되서 무적권 쓴다. 반대일 경우는 0~1사이이므로 확률적으로 쓴다

        if (nowP > (double)ran(mt) / (n - 1)) // 0~1사이 수를 뽑아서 nowP가 저번보다 상태가 안 좋을 경우 확률적으로 뽑는다.
        {
            a = b; 
            prv = now;
        }

        ans = min(ans, prv);

        t *= 0.9999; // 온도를 줄이면서 점점 변화의 크기를 줄여감 (온도감률 0.95~0.9999)
    }

    cout << ans << '\n';

    return 0;
}

시간 : 4ms

 

태그 : #백준 2582 #백준 동전 뒤집기 2 #boj 동전 뒤집기 2 #동전 뒤집기 2 휴리스틱 #휴리스틱 알고리즘 #시뮬레이티드어닐링