인생은 여행, 즐기며 살렵니다

#include #include #include #include #include #include #include #include #include // for atoi #include // for stringstream #include // for sqrt #include // for memset using namespace std; #define INF 987654321 int main(void) { int tc; scanf("%d", &tc); while(tc--) { } return 0; }

(앞의 (상) 에 해당하는 글을 보지 못하신 분은, 먼저 보고 오시면 좋겠습니다.) (다시 한 번 적습니다만, 이 책은 [알고리즘 문제 해결 전략] 의 책 내용을 정리한 것입니다,) 저번 글에서는, u에서 v까지 가는 경로 중에, S의 원소를 경유점으로 사용하는 최단 경로의 길이는 [1번 식] 로 나타나짐을 살펴보았다. 이제 이 식을 점화식 형태로 나타내기 위해서, 형태를 살짝 바꾸어 보자. 그래프의 노드의 개수가 V개라면, 각각의 노드들을 0부터 V-1 까지 번호를 붙일 수 있다. 인 원소 k에 대해서, 이라 하자. 다른 말로 하면, 는 0부터 k까지의 정수를 원소로 갖는 집합이다. 이렇게 표현하는 경우, 는 0부터 k까지의 노드의 집합이 되며, 우리가 구하고자 하는 u에서 v까지의 최단 거리는, '모..

플로이드의 모든 쌍 최단 거리 알고리즘 (이 내용은 '알고리즘 문제 해결 전략' 의 내용을 정리한 것입니다.) 1. 플로이드의 최단 쌍 알고리즘의 기본적인 개념 그래프 내의 어떤 두 점을 u와 v라고 할 때, u에서 v로 가는 경로가 있다고 하자. 이 두 점을 잇는 경로는, u와 v를 직접적으로 연결하는 하나의 간선일 수도 있고, 아니면 다른 점들을 거쳐서 가는 경로일 수도 있다. 후자의 경우, 예를 들면 u - a - b - c - v 와 같은 형태가 될 것이다. 이렇게 u에서 v로 가는 경로가 다른 점을 경유해서 가는 경우, 이 경유하는 점들을 경유점이라 하자. 즉, 위에 예로 든 경로에서는 a, b, c가 경유점이 된다. 정점 집합 S에 포함된 정점만을 경유점으로 사용해서, u에서 v로 가는 최단 ..

(http://stackoverflow.com/questions/164163/quicksort-choosing-the-pivot) 퀵 정렬에서의 피봇 선택에 따라서, 퀵 정렬의 실행 시간은 O(NlgN)에서 최대 O(N^2) 까지 걸릴 수 있다. 나쁜 (worst-case)의 경우의 예를 들면, - 이미 정렬이 되어 있는 배열 (또는 거의 정렬된 배열) - 반대로 정렬이 되어 있는 배열 을 정렬하고자 할 때, pivot을 가장 첫 번째 원소나 가장 마지막 원소로 지정하는 것이다. 이 경우, 각 단계마다 '원소 1개'와 '나머지 원소 전부' 로 쪼개지기 때문에, divide-and-conquer 방식의 이점을 살리지 못하게 된다. 효율적인 Quick Sort를 위해서는, pivot을 잘 선택할 필요가 있다..