다락방

Union-Find Disjoint Set을 표현할 때 사용하는 알고리즘 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 집합을 구현하는데 비트벡터, 배열, 연결리스트를 이용할 수 있으나 그 중 효율적인 트리구조를 이용하여 구현 연산 make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x,y) 합하기 x가 속한 집합과 y가 속한 집합을 합친다. find(x) 찾기 x가 속한 집합의 대표값(루트노드값)을 반환한다. x가 어떤 집합에 속해있는지 찾는 연산 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할 하는데 자주 사용 최악의 상황 트리 구조가 완전 비대칭인 경우 연결리스트 형태 트리의 높이가 최대가 된다. 원소의 개수가 N일..

크루스칼(Kruskal) 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 탐욕적인 방법 결정을 할 때마다 그 순간 가장 좋다고 생각 되는것을 선택함으로서 최종적인 해답에 도달하는 것 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야한다. Kruscal 알고리즘은 최적의 해답을 주는 것으로 증명되었다. 동작 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 즉 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST의 집합에 추가한다. 특징 간선선택을..

신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프다. 최소연결 : 간선의 수가 가장 적다 n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다. 그래프에서 일부 간선을 선택해서 만든 트리 특징 BFS,DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에서 많은 신장 트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. Spanning tree는 그래프에 있는 n개의 정점을 정확히 ..

플로이드 워셜 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘 단계마다 ‘거쳐가는 노드’를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾을 필요가 없다. 2차원 테이블에 최단 거리 정보를 저장한다. DP알고리즘에 속한다 노드 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다. 시간복잡도 O(N^3)

다익스트라 그래프의 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점뿐만 아니라 모든 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 동작과정 출발노드와 도착노드를 설정한다 ‘최단 거리 테이블’을 초기화 한다. 현재 위치한 노드의 인접노드 중 방문하지않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 짧은 노드를 선택한다. 그 노드를 방문처리한다. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)를 계산해 ‘최단 거리 테이블’ 을 업데이트 한다. 3-4 과정을 반복한다. ‘최단거리 테이블’ 은 1차원 배열로, N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개..

B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다. 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다. 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다. 노드의 키가 x라면 자식의 수는 x+1개 이다. 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다. Key 검색과정 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고..

위상정렬(Topological Sorting) 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정 큐를 이용해 구현한다. 진입차수가 0 인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다. 위상정렬의 특징 위상정렬은 사..

DFS(Depth-First Search) 깊이 우선 탐색 알고리즘 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.) 동작과정 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다. 2를 수행할 수 없을때까지 반복한다. def DFS(graph,v,visit): visited[v] = True print(v) for i in graph[v]: if not visited[i]: DFS(graph,i,vi..

병합정렬(Merge Sort) 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. 동작과정 Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다 Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다. def merge_sort(arr): def sort(low, high): if high - low < 2: return mid= (low + high) // 2 sort(low, mid) sort(mid, high) me..

분할정복(Divide and Conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식 대표적인 예 퀵정렬 합병정렬 이진탐색 선택문제 고속 푸리에 변환 분할정복의 설계 Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다. Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다. 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복..