fashion_developer

분할 정복 배열을 하나 또는 둘 까지 반으로 계속 쪼갠 다음 합치는 방식으로 이해하면 됨 12345678910111213141516171819202122int arr[100000]; // 입력받은 배열int tmp[100000]; // 정렬에 필요한 임시 배열void merge(int a, int b) { if (b == a) return; if (b - a == 1) { if (arr[a] > arr[b]) swap(arr[a], arr[b]); return; } int left = a; int mid = (a + b) / 2; int right = mid + 1; merge(a, mid); merge(mid + 1, b); int i = a; while (left != mid + 1 && right ..

특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘. - 간선의 가중치가 음인 경우에도 사용가능 하다. - 음의 사이클이 있는지 확인 할 수 있다. V : 노드의 갯수D[i] : 출발점에서 K 정점 까지의 최소 비용 (D[출발] = 0, 나머지는 무한대로 초기화) 1. 모든 간선을 (V - 1)번 확인한다. D[now] != INF 이고 D[next] > D[now] + W (간선의 가중치) 이면 D[next] = D[now] + W 로 갱신한다. 2. V번째 간선을 확인했을 때 D가 갱신된다면 음의 사이클이 존재한다. 시간복잡도 : O(VE) 12345678910111213 D[1] = 0; // 출발점의 비용은 0 FOR(i, 1, V) { for (info edge : v) { /..