구사과

일부 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에 N<=25라고 나와있는데 실제로는 N<=32입니다. 그리고 96년 기출도 오타로 추정됩니다.2006년 KOI 지역본선 문제로 나왔던 문제라고 합니다.전 아직도 무슨 약을 빨고 이런 문제를 냈는지 상상도 못하겠지만일단 풀어 봅시다.1. brute force제일 먼저 생각해볼 수 있는 방법은. 가로로 한번 뒤집어보고 세로로 한번 뒤집어보는 경우를 모두 다 해보는 겁니다. (가로 상태) * (세로 상태) * 개수 세기(n^2) = 이겠네요.참 보기만 해도 기분나쁜 시간복잡도입니다.그런데 조금만 생각해도 금방 고칠 수 있는 시간복잡도입니다.가로를 쫙 뒤집고 난 후에 세로를 뒤집을때 굳이 2^n씩이나 되는 시간..

뭐... 세 알고리즘 모두 최단 경로를 찾는 데 사용되는 알고리즘입니다.그래프 관련해서 상당히 유용한 알고리즘이기도 하고 실제로도 쓸 일이 굉장히 많은 알고리즘입니다. (아마)편의상 말은 짧게 하겠습니다.어느 온라인 저지를 가도 비슷한 문제가 몇개씩 있겠지만.. 나한텐 가장 익숙한 koistudy.net을 두고 설명하겠다. 문제는 뭐.. 1번 정점에서 n번 정점을 가는데 걸리는 최소 거리를 출력하는 거다.R&E가는길 (Tiny) (n<10. 간선 < 30)R&E가는길 (Small) (n<500. 간선 < 4000)R&E가는길 (Large) (n<10000. 간선 < 100000)보통 이러한 입력의 데이터는 인접행렬을 잡아서 푼다. (사실 std::vector를 이용해 인접 리스트 형식으로 저장하는 게 훨..