[목차] 1. 다익스트라 알고리즘이란? 알고리즘 알고리즘 원리 구현 O(n²) O(ElogE) 알고리즘 분석 의의 다익스트라는 일종의 그리디 이다. 왜? 매 순간 다음 정점을 선택할 때 가중치가 최소인 정점을 선택하기 때문이다. 하지만 그리디의 특성상 부분 최적해가 전체의 최적해를 보장해야 위의 선택이 합리적이라고 할 수 있다. 그렇다면 매 순간 최소 가중치를 가진 정점을 선택하면 항상 최소가 보장될까? 직관 이를 귀류법으로 증명해보자. 반례 [원시적인 다익스트라 알고리즘] #include #include #include #define F first #define S second using namespace std; typedef pair PII; int V, E, st, en; int d[10001];..

필수 선행 개념: 분할 정복, 이분 탐색 배열 arr = {1, 3, 5, 10, 2}이 있다고 해보자. 특정 구간의 최댓값, 최솟값, 구간합, 구간곱을 구한다고 할 때 질문이 하나라면 O(N)에 해결할 수 있다. 만약 질문이 10만개라면 어떨까? O(N²) = 약 11자리 이므로 1초안에 해결이 불가능하다. 이때 세그먼트 트리를 이용하면 O(log N)에 해결이 가능하다. 배열의 크기는 자료의 개수(N)에 대해 N보다 크거나 같은 2의 제곱수에 두배한 크기만큼 미리 할당해두어야 한다. 시뮬레이션 1. 세그먼트 트리 초기화하기 int init(int st, int en, int node){ if(st == en) return tree[node] = arr[st]; int mid = (st + en) / ..