구사과

일부 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 시간에 나온다. 짱짱 빠르다 ..