NEMOSTAR5

다이나믹 프로그래밍은 줄여서 DP라고도 하고, 동적 계획법이라고도 불린다. 다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘'이다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다. (다만 분할 정복 기법은 '정렬'과 같은 몇몇 요소에 대해서는 동일한 문제를 다시 풀게 되는 단점이 없습니다. 그 예시로 퀵 정렬이나 병합 정렬은 매우 빠릅니다.) 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있다. 피보나치 수열의 점화식: D[i] = D[i - 1] + D[i - 2] 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다. 1번 가정. 큰 문제를 작은 문제를 나눌 수 있다. 2번 가정. 작은 문제에서 구한 ..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘. 예를 들어, 여러개의 도시가 있을 경우 가장 적은 가중치를 가지는 도시를 먼저 연결한다. 이걸 계속 반복해 나아가며 결국에는 모든 노드를 연결해 그래프를 완성해 나가는 것이다. 최종적으로 완성되는 그래프의 간선 숫자는 노드 숫자 == 노드 숫자 - 1 "간선을 거리가 짧은 순서대로 그래프에 포함시킨다." 1. 노드들의 가중치를 오름차순으로 정렬을 수행한다. 2. 정렬된 순서에 맞게 그래프에 포함시킨다. 3. 하지만, 사이클이 형성되는지 확인하고 발생하지 않는 경우에만 간선에 포함시킨다. (사이클 테이블) 사이클이란? 코드 추가 예정.

Union-find는 대표적인 그래프 알고리즘이다. 바로 '합집합 찾기'라는 의미를 가진 알고리즘. 서로소 집합(Disjoint-set) 알고리즘 이라고도 불린다. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 처음에는 자기 자신이 부모 노드로 되어있는 상태이다. 만일 1과 2과 연결되었다고 생각해보자. 그렇게 되면 2의 부모 인덱스에는 1이 들어간다. 부모를 합칠 때에는 일반적으로 더 작은 값 쪽으로 합친다. 1 2 3 4 5 6 7 1 1 3 4 5 6 7 이번에는 2와 3이 연결되었다고 가정해보자. 1 2 3 4 5 6 7 1 1 2 4 5 6 7 그렇다면 1과 3이 연결되었는지를 어떻게 파악하냐가 문제이다. 1과 3은 부모가 각각 1과 2로 다르기 때문에 '부모 노드'만 보고는 한번에 파악 할..

힙 정렬의 시간 복잡도는 nlog n이다. 힙을 생성하는 알고리즘의 시간 복잡도는 log n이다. 그 이유는 완전 이진트리 구조를 사용하기 때문이다. 상향식 구현방법 #include using namespace std; int number = 9; int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6}; int main() { // 힙을 구성 for(int i = 1; i < number; i++) { int c = i; do { int root = (c - 1) / 2; if(heap[root] < heap[c]) { int temp = heap[root]; heap[root] = heap[c]; heap[c] = temp; } c = root; }while (c != 0); } /..