Computer Science/Data Structure and Algorithm
-
Shortest Path AlgorithmComputer Science/Data Structure and Algorithm 2020. 5. 20. 13:21
✔️ 최단 경로 문제(Shortest Path Problem) ◾️ 가중치 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제 ◾️ 가중치가 없는 그래프에서의 최단 경로는 BFS로 찾을 수 있다. ✔️ 다익스트라(Dijkstra)의 최단 경로 알고리즘 ◾ 단일 시작점 최단 경로 알고리즘이다. ◾ 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. ◾ 다익스트라 알고리즘은 BFS처럼 시작점에서 가까운 순서대로 정점을 방문한다. 1️⃣ 다익스트라 알고리즘 : 우선순위 큐를 사용하는 BFS 📋 우선순위 큐 ◾ 우선순위 큐에 정점의 번호와 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다. ◾ 우선순위 큐는 정점까지의 최단 거리를 기준으로 정점을 배열함으로써, 아직 방문..
-
Sieve of EratosthenesComputer Science/Data Structure and Algorithm 2020. 4. 28. 23:46
✔️ 에라토스테네스의 체 ◾ 숫자들을 순차적으로 접근하면서, 각 숫자의 배수에 해당하는 숫자들을 걸러냄으로서 소수를 찾아내는 방법이다. ◾ 참고로 에라토스 테네스의 체 시간복잡도는 O(n log log n) 이다. (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 💾 소스 #include #include using namespace std; const int MAX = 1000; int main() { vector prime; bool isPrime[MAX + 1]; memset(isPrime, true, sizeof(isPrime)); for (int i = 2; i
-
Minimum Spanning Tree (Kruskal, Prim)Computer Science/Data Structure and Algorithm 2020. 4. 26. 22:04
✔️ Spanning Tree ◾️ 스패닝 트리는 원본 그래프의 정점 전부와 간선의 부분 집합으로 이루어진 부분 그래프이다. ◾️ 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. ◾️ 트리 형태란 간선들이 사이클을 이루지 않는다는 것을 의미한다. ✔️ Minimum Spanning Tree Problem ◾️ 최소 스패닝 트리 문제란, 가중치 그래프의 스패닝 트리 중 가중치의 합이 가장 작은 트리를 찾는 문제를 말한다. ◾️ 즉, 그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제이다. ✔️ Kruskal's Algorithm ◾️ 크루스칼의 최소 스패닝 트리 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 나간다. ..
-
Union Find, Disjoint SetComputer Science/Data Structure and Algorithm 2020. 4. 24. 17:02
✔️ Union Find ◾️ Union Find는 Disjoint Set(상호 배타적 집합)을 표현할 때 쓰는 트리 자료 구조이다. ◾️ 상호 배타적 집합이란 공통 원소가 없는 배타적 집합을 뜻한다. ◾️ Union 연산 : 두 원소 A, B가 주어질 때, 이들이 속한 두 집합을 하나로 합친다. ◾️ Find 연산 : 어떤 원소 A가 주어질 때 이 원소가 속한 집합을 반환한다. 트리를 이용한 상호 배타적 집합의 표현 ◾️ 두 원소가 같은 집합(트리)에 포함되어 있는지 확인하는 방법은 각 원소가 포함된 트리의 루트가 같은지 확인하는 것이다. 이렇게 하기 위해서는 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야한다. 루트는 부모가 없으므로, 대개 자기 자신을 가리키도록 구현한다. ◾️ 두 트리를 합칠..
-
GraphComputer Science/Data Structure and Algorithm 2020. 4. 2. 10:25
✔️ 그래프 ◾그래프는 정점과 간선으로 이루어진 자료구조이다. ◾ 연결되어 있는 정점 간의 관계를 표현할 수 있다. ◾ 무방향 그래프 : 연결 관계에 있어서 방향성이 없는 그래프 ◾ 방향 그래프 : 간선에 방향정보가 포함된 그래프 ◾ 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프 ◾ 가중치 그래프 : 간선에 가중치 정보가 있는 그래프 ✔️ 그래프를 구현하는 두 가지 방법 ◾ 인접 행렬(adjacent matrix) 기반 그래프 : 정방 행렬을 활용 ◾ 인접 리스트(adjacent list) 기반 그래프 : 연결 리스트를 활용 ✔️ 그래프의 탐색 1️⃣ 깊이 우선 탐색(Depts First Search, DFS) ◾ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' ..
-
Priority Queue, heap ( 우선순위큐, 힙 )Computer Science/Data Structure and Algorithm 2020. 4. 2. 10:24
✔️ Priority Queue(우선순위 큐) ◾ 우선순위 큐는 큐와 비슷하다. ◾ 큐는 연산의 결과로 "먼저 들어간 데이터가 먼저 나온다." 하지만 우선순위 큐의 연산 결과는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다." ◾ 우선순위 큐는 배열, 연결리스트, 힙을 이용하여 구현할 수 있다. ◾ 배열기반으로 우선순위 큐를 구현하면, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시키면 된다. ◾ 하지만 삽입&삭제 연산에서의 shift 연산 오버헤드가 발생한다. 또한 적절한 삽입 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야할 수도 있다. ◾ 연결리스트 기반으로 우선순위 큐를 구현하면, 배열과 같이 shift 오버헤드는 발생하지 않지만 우선순위에 따른 ..
-
Tree, Binary Search Tree, AVL TreeComputer Science/Data Structure and Algorithm 2020. 4. 2. 10:23
✔️ Tree(트리) ◾ 트리는 계층적 관계를 표현하는 자료구조이다. ◾ 트리는 부모 노드와 자식 노드의 관계로 재귀적으로 구성된다. 부모 노드가 없는 노드를 루트노드라고 정의한다. ◾ 노드(node) : 트리의 구성요소 ◾ 간선(edge) : 노드와 노드를 연결하는 연결선 ◾ 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드 ◾ 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 ◾ 단말 노드(leaf node) : 아래로 또 다른 노드가 연결되어 있지 않는 노드 ◾ 노드 간에는 부모, 자식, 형제 관계가 성립된다. ✔️ Binary Tree(이진 트리) ◾ 이진트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리이다. ◾ 전위 순회(Pre oder trave..