구사과

http://koistudy.net/?mid=prob_page&NO=521 알고리즘 문제해결 전략에 나온거랑 되게 비슷한 문제다. 그래서 베끼다시피해서 제출했다 문제에 사족이 참 많은데 요약하자면 모든 단어을 사용해서 끝말잇기를 하라 라는 내용이다. 단, 한 단어는 00 ~ 99 낱말 5개 로 구성되었으며, 출력시 사전순으로 가장 앞서는 것을 출력해야 한다. 단어를 꼭지점 (vertex)로 두고 생각하면 백트래킹을 해야 하기 때문에 500000개는 택도 없다. 거기다 지금 이 글의 주제가 한붓그리기이므로, 단어를 방향이 있는 모서리 (edge) 로 두고 한붓그리기를 하는 것이 좋겠다. 즉 단어가 0001020304 이런 식이라면, 00 -> 04로 가는 간선인 것이다. 그러면 V = 100, E 2 ->..

일부 dp문제에서 시간복잡도를 획기적으로 줄여주는 걸로 유명한 테크닉입니다. 이번에 koi 2014 전국본선 3번으로 나왔으니 인지도가 더 올라갈 거 같네요. 개략적으로 설명하자면 문제를 풀다가 이런 형태의 점화식이 나올 때는 보통 n^2 말고는 희망이 없는데 이걸 이런 식으로 해석하면 기울기와 절편이 j에 따라 결정되는 형태의 일차함수들로 해석할수 있게 됩니다.이러면 저러한 dp식을 구할때(dp[0] = 0) 1. 0번 선분을 넣는다 (기울기 = b[0]. 절편 = dp[0]) 2. 현재 들어간 선분 중 최솟값을 찾는다 (dp[1])3. 1번 선분을 넣는다 (기울기 = b[1]. 절편 = dp[1])4. 현재 들어간 선분 중 최솟값을 찾는다 (dp[2])...... 즉, * dp[i]를 구하고 * 선분..

(koistudy.net / acmicpc.net (Small / Large)) koistudy.net에 N0) 이때. 상태의 에너지는 그 상태가 가지는 값을 뜻합니다. 쉽게 말해 우리가 구하고자 하는 답이죠. 이 문제에서는 뒷면인 동전의 수가 상태의 에너지가 되겠습니다. 담금질 방법은 다음과 같이 작동합니다. (rand()는 0~1 사이의 임의의 난수입니다.) while ( k > 임계 온도 ){E1 = 현재 상태의 에너지 E2 = 랜덤하게 생성한 새로운 상태의 에너지p = exp((E1-E2)/(k*T));if(p > rand()) 현재 상태를 새로운 상태로 바꿈k *= 온도 감률 (보통 0.95 ~ 0.9999 정도) }과연 이런 식으로 해를 구하는 것이 왜 유효한지 case를 나눠서 살펴보도록 하..