Computer Science/자료구조&알고리즘
-
크루스칼 알고리즘 (Kruskal Algorithm) with Union-Find 알고리즘Computer Science/자료구조&알고리즘 2021. 2. 26. 18:26
크루스칼 알고리즘 (Kruskal Algorithm)이란, 그래프의 최소 비용 신장 트리(Minimal Spanning Tree : MST)를 구하는 그리디 알고리즘이다. 그리디 알고리즘으로써 최적의 해답을 얻을 수 있다는 사실이 증명되어 있다. 기본 과정은 다음과 같다. 1. 그래프의 간선들을 가중치 오름차순으로 정렬한다. 2. 첫번째 간선부터(즉, 가중치가 가장 낮은 간선부터) 선택한다. 3. 선택했을 때, 현재의 MST 집합에 사이클을 형성하는지 여부를 판단한다. 4. 사이클을 형성하면 배제하고, 그렇지 않으면 MST 집합에 추가한다. 이 때, 사이클 형성 여부는 Union-Find 알고리즘을 이용한다. Disjoint Set : 서로 중복되지 않는, 상호 배타적인 부분 집합들로 나눠진 원소들을 저..
-
퀵 정렬 (Quick Sort) 알고리즘Computer Science/자료구조&알고리즘 2021. 2. 17. 16:56
분할 정복에 기반한 알고리즘. 리스트에서 피봇을 고른 뒤, 피봇을 기준으로 왼쪽에는 피봇보다 작은 수, 오른쪽에는 피봇보다 큰 수들을 모은 뒤, 비균등하게 리스트를 나눠가며 정렬한다. 리스트를 모두 쪼갰을 때 모두 정렬이 되어 있다. 따라서 마지막에는 정렬된 것을 합치기만 하면 된다. 리스트의 첫째 원소를 피봇으로 삼고, 나머지 리스트에서 왼쪽에서 시작하는 인덱스 low와 오른쪽에서 시작하는 인덱스가 high가 있다. low는 피봇보다 값이 크거나 같은 원소를 만날 때까지 계속 오른쪽으로 이동한다. 즉, low보다 작은 인덱스의 원소들은 모두 값이 low가 가리키는 원소보다 작다. high는 피봇보다 값이 작거나 같은 원소를 만날 때까지 계속 왼쪽으로 이동한다. 즉, high보다 큰 인덱스의 원소들은 모..
-
합병 정렬 (Merge Sort) 알고리즘Computer Science/자료구조&알고리즘 2021. 2. 17. 15:28
분할정복에 기반한 정렬 알고리즘. 배열을 모조리 분할한 다음에, 도로 합치면서 정렬이 이루어진다. 분할 단계와 합병 단계로 나뉜다. 수도코드 merge_sort(int a[], int len){ if(len == 1){ return; } // 분할 단계 merge_sort(a, len/2); merge_sort(a + len/2, len - len/2); // 합병 단계 int b[len]; int i = 0, j = len/2, k; for(k = 0; k
-
힙(heap)의 삽입과 삭제Computer Science/자료구조&알고리즘 2021. 2. 16. 17:27
힙(heap)의 삽입과 삭제 최대 힙을 기준으로 설명한다. 힙의 삽입 힙은 배열로 구현된 완전 이진 트리이다. 배열의 끝 인덱스부터 시작하여, 그 부모 노드와 비교하며 해당 노드보다 키 값이 더 크면 부모 노드의 인덱스를 증가시키는(트리에서 밑으로 끌어내리는) 과정을 키 값이 더 큰 부모 노드를 만날 때까지만 반복한다. 반복이 끝나면 현재 인덱스의 원소에 삽입할 키 값을 대입하고 힙의 삽입 과정이 종료된다. 수도코드 insert_max_heap(heap h, int item){ int i = ++(h.size); while(i > 0 && h[i/2]
-
BFS (Breadth First Search) : 너비 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:12
BFS, 너비 우선 탐색이란, 그래프 상에 존재하는 정점을 방문할 때마다 그 다음으로 주변의 인접한 정점들을 우선적으로 탐색해나가는 탐색 방법을 말한다. 반복문과 큐를 이용하여 구현할 수 있다. 수도코드 bfs(int i){ queue q; q.push(i); visited[i] = true; while(!q.empty()){ int v = q.pop(); for(i in adjacent vertices of v){ if(!visited[i]){ q.push(i); visited[i] = true; } } } } 노드를 방문할 때마다 방문하지 않은 주변 노드들이 큐에 들어간다. 큐에 한번 들어가는 순간 방문이 예정되어 있으므로 방문 표시를 한다. (그래야 중복 방문이 제대로 방지된다.) 큐에 들어간 순서..
-
DFS (Depth First Search) : 깊이 우선 탐색Computer Science/자료구조&알고리즘 2021. 2. 15. 23:01
DFS, 깊이 우선 탐색이란, 그래프 상에 존재하는 정점에서 인접한 정점 중에 방문하지 않은 정점이 없을 때까지 계속 인접한 다른 임의의 정점으로 이동하며 탐색한다. 인접한 정점 중에 방문하지 않은 정점이 없으면 이전 정점으로 이동한 뒤 다른 정점으로 이동하는 과정을 반복한다. 구현 방법은 재귀함수를 이용한 것과, 반복문과 스택을 이용한 것으로 2가지가 있다. 수도코드 - 재귀함수로 구현 dfs(int v){ visited[v] = true; for(u in adjacent vertices of v){ if(!visited[u]){ dfs(u); } } } 인접한 노드를 하나씩 연이어서 계속 방문한다. 그러다가 방문할 노드가 없으면 이전 노드의 인접 노드를 탐색하게 된다. 수도코드 - 반복문과 스택으로 ..
-
그래프Computer Science/자료구조&알고리즘 2021. 2. 13. 21:41
그래프 : 정점(Vertex)과 간선(Edge)의 집합. 트리는 사이클이 허용되지 않는 일종의 그래프이다. Undirected Graph : 간선이 방향을 갖지 않는 그래프. 무향 그래프. Directed Graph (Digraph) : 간선이 방향을 갖는 그래프. 유향 그래프. Degree (차수) : 각 정점에 연결된 간선의 개수 Outdegree : 유향 그래프에서 정점으로부터 밖으로 나가는 간선의 개수 Indegree : 유향 그래프에서 정점으로 들어가는 간선의 개수 가중치 그래프(Weight Graph) : 간선에 가중치 정보를 둔 그래프. 부분 그래프(Sub Graph) : 어떤 그래프의 부분집합에 해당하는 그래프 (해당 그래프의 정점과 간선들 중 일부만 가지고 있는 그래프) 그래프의 구현 방..
-
자료구조 기초 정리 (시간 복잡도, 추상 데이터 타입, 선형 자료구조, 트리)Computer Science/자료구조&알고리즘 2021. 2. 13. 16:13
시간 복잡도 : 인스턴스에 따른 실행 시간 변화 추이를 나타내는 척도 추상 데이터 타입 (ADT) : 자료구조의 명세서, 사용 설명서 같은 것. 데이터가 저장되는 방식과 데이터의 인터페이스 역할을 하는 메소드들의 정의로 이루어져 있다. 배열(Array) : 탐색 시간이 O(1)이지만, 삽입과 삭제가 worst case의 경우 O(n)이다. 링크드 리스트(Linked List) : 삽입과 삭제 시간이 O(1)이지만, 탐색 시간이 worst case의 경우 O(n)이다. 스택과 큐 : 둘 다 선형 자료구조이다. 스택(Stack) : LIFO(Last In First Out) 방식의 자료구조. 큐(Queue) : FIFO(First In First Out) 방식의 자료구조. 트리(Tree) : 비선형 자료구조..