BOJ 15310 아티스트

출처 : 경기과학고 나는 코더다 2017 송년대회 F번

난이도 : Solved AC 기준 Diamond II 

 

내가 왜 이걸 이렇게 풀었지...

이 모든게 해시코드 후유증이다. :blobcry:

1. 문제 설명

문제의 지문 자체는 별로 길지 않지만, 요약하면 다음과 같다.

• $(w_i, h_i)$ 의 정보를 갖는 '그림' 이 $n$ 개 주어진다.
• 이 '그림' 들 중 $k$ 개를 고를 것이다.
• 고른 그림들을 $1, 2, \dots k$ 번이라고 할 때, $$\left(\sum_{i = 1}^{k} w_i \right) \left(\sum_{i = 1}^{k} h_i \right)$$ 이 값을 최대한 Minimize하고 싶다.

2. 풀이

먼저, 생각해 보면 총 $\binom{n}{k}$ 개의 가능한 그림 조합들이 각각 $\sum w_i$ 와 $\sum h_i$ 값을 가진다고 생각할 수 있다. 이때, $\sum w_i$ 값을 $x$축에, $\sum h_i$ 값을 $y$축에 놓고 도시하면 다음과 같은 그림을 얻게 될 것이다.

(그림은 임의의 점을 아무렇게나 찍은 것이라, 그림 자체에는 아무런 의미가 없다)

위 그림에서 한 점은 $\binom{n}{k}$ 개의 가능한 조합 중 하나를 의미한다. 

이제, 우리가 원하는 것은 위 그림같은 상태 공간에서, $xy = k$ 그래프를 놓고, $k$ 가 최대한 작은 그래프 위에 올라간 점을 찾는 것이다. 눈으로 보기에는 (20, 6) 정도에 있는 점과 (10, 10) 근처에 있는 점, (4, 30) 근처에 있는 점들 중 어느 쪽이 최적인지 알기 어렵지만, 그래프를 그려놓고 보면 바로 알 수 있다.

이제, 수학적으로 뭔가 관찰을 해 보자. 

"어떤 기준" 으로 점을 Sorting 한 다음, 그 정렬된 기준으로 Greedy 하게 그림을 선택한다면 아무렇게나 택하는 것보다는 당연히 조금 이득일 것임을 알 수 있다. 예를 들어, "$h$ 는 무시하고 $w$ 가 작은 그림을 골라라!" 라고 한다면, 우리는 실제로는 저 그림에서 $x$축에 가까이 붙은 조합을 택하는 것이다. 

가중치를 둬서, $aw + bh$ 가 작은 순서대로 그림을 고르기로 했다고 생각해 보자. 이는 다시 말하자면, $ax+by$ 를 최적화하려는 시도이다. 예를 들어, $a = b = 1$ 을 골랐다면 실제로는 이 과정이 수행되고 있다고 보아도 좋다. 

이렇게 직선들을 잘 그려서 가장 안쪽 직선에 붙는 점을 고르는 과정이다. 직선의 가중치를 바꾼다면, 예를 들어 $b = 3$ 를 써서, $x + 2y$ 를 최적화하고 있다면,

최적점이 $(20, 7)$ 로 바뀌었음을 볼 수 있다.

사실 $ax + by$ 를 최적화하는 대신 $x + ky$ 를 최적화한다고 보아도 수학적으로 같으므로, 우리는 한개의 Parameter만 바꿔서 전체 결과를 다시 돌려볼 수 있다. 즉, 저 "최적화 대상 직선" 기울기 $k$ 를 바꾸면서 계속 돌리면, 가끔씩 최적 점이 바뀔 수도 있다는 얘기가 된다.

 

추가적인 관찰

이제, Simulated Annealing 을 돌려서 문제를 해결하려고 시도해 보자. 처음에는 $k = 1$, 즉 $x + y$ 를 최적화하다가, 적당히 $k$ 에 작은 변동 (나는 $1/1.05$ 이상, $1.05$ 이하의 작은 변동을 주었다) 을 주어 가면서, 새로운 직선을 놓고 최적화를 해 보는 방법이다.

 

Simulated Annealing 을 쓰는 이유는, 단순한 최적화 방법을 쓰면 Local minimum에 빠지기 쉽기 때문이다. 예를 들어, 위 그림에서 사실 최적으로 $(1, 70)$ 같은 점이 있었다고 생각해 보자. 이때, 처음에 기울기를 줄이기로 작정했다면 일반적인 최적화로는 계속 기울기가 줄어드는, 오른쪽 아래 구간에서 더 나은 점을 찾을 수는 있지만 기울기가 매우 큰 부분에 있는 최적해를 찾아내지 못한다. 그림으로 도시해 본다면 이런 경우에 해를 찾기 어렵다는 의미이다.

(역시 그림은 실제 데이터로부터 뽑아낸 것이 아니라, 마음대로 점을 찍고 도시한 것이다)

 

이를 보조하기 위해, 나는 직접 조금더 이것저것 때려넣었는데, 여러 번 내 보기 어려워서 실제로는 이 모든 내용을 확인하기는 어렵다. (로컬에서는 랜덤 데이터를 찍어서 확인도 해봤지만, 문제를 누가 만들었는지를 생각해보면 일단 데이터는 엄청 강할것 같았다) 감으로 찍어서 몇번 해보고 맞은 다음 손절했다.

 

먼저, Iteration 한번에 1.05배까지 밖에 못 가고, 그러면 엄청 큰 값 (INF) 가 최적인 경우 충분히 빠르게 도착하지 못할 수 있다. 이를 해결하기 위해 가끔씩은 멀리 (10배씩) 뛰어주는 것도 도움이 될 수 있겠다고 생각했다. 

 

두 번째 문제는, $x$축에 가까이 붙은 점 하나와 $y$ 축에 가까이 붙은 점 하나의 점수를 둘 다 내보고 최적을 찾아야 하는데, 그러지 않고 한쪽 길만 계속 왔다갔다하는 문제이다. 수백~수천의 $k$값을 이용하는 경우, 몇배 정도 조작을 하더라도 아예 다른쪽 길로 가지는 않고 오히려 그냥 후퇴만 하는 결과를 가져올 수 있다. 이를 방지하기 위해, 전체 담금질 과정에서 적어도 몇번은 반대쪽 길을 확인해 볼 필요가 있다.

 

한번 점수를 내는데 $O(n \log n)$ 시간이 걸리고, 이는 $n = 3000$ 에서 대략 5만번 정도 연산을 의미힌다. 즉, 우리는 적어도 수천번 단위로 담금질할 시간이 있다. 따라서, 천번에 한번 정도는 $k$를 아예 $1/k$ 로 바꿔서 확인해 보면,

- 지난 천번 동안 작은 / 큰 값 (충분히 축에 가까운 값) 을 확인했었다면 이제 반대쪽 축도 확인해 보는 계기가 되고, 

- 지난 천번 동안 1 근처에서만 돌아다녔다면 어차피 $k := 1/k$ 도 정상적인 연산과 크게 다르지 않으므로 상관 없다. 

단, 초반에 $1/k$ 를 쓰면 최적화에 방해되므로, 0.7초가 지난 시점부터 (...) 1000번에 한번 정도 이 행동을 하도록 했다. 

 

이 모든 연산들을 집어넣고, 정확히 얼마나 담금질해야할지 알수 없으므로 제한시간 1초에 맞게 추하지만 0.95초동안 담금질하도록 하면 알뜰하게 시간을 전부 쓸 수 있다. 

 

 

3. 코드 

나는 Data Science 나 Machine Learning, Genetic Algorithm 등을 심도깊게 공부한 적이 없고, 이번에 구글 해시코드를 준비하면서 아 이런게 있구나 + PS에서 가끔 모르겠는 문제를 뚫을 수 있겠구나 (?) 정도만 알고 있어서, 정확하게 Simulated Annealing 의 동작이나 이런 부분들을 이해하고 있는 것 같지 않다.

그래서 평소와는 달리 블로그에 직접 코드를 공개하지는 않을 계획이다. 사실 데이터 추가하면 어떻게 될지 모르는 코드이기도 하고...