구사과

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를 나눠서 살펴보도록 하..

뭐... 세 알고리즘 모두 최단 경로를 찾는 데 사용되는 알고리즘입니다.그래프 관련해서 상당히 유용한 알고리즘이기도 하고 실제로도 쓸 일이 굉장히 많은 알고리즘입니다. (아마) 편의상 말은 짧게 하겠습니다. 어느 온라인 저지를 가도 비슷한 문제가 몇개씩 있겠지만.. 나한텐 가장 익숙한 koistudy.net을 두고 설명하겠다. 문제는 뭐.. 1번 정점에서 n번 정점을 가는데 걸리는 최소 거리를 출력하는 거다. R&E가는길 (Tiny) (n shortest[i] + adj[i][j])3-1. 만약 빠르면. 최단 경로와 함께 parents 역시 갱신. }그런데, 방문하지 않은 점을 조금 더 빠르게 검색할 수 있다.힙을 쓰면 된다. 힙을 쓰면 가장 가까운 점 (최소값) 이 lgn 시간에 나온다. 짱짱 빠르다 ..