데이터 분석 기술 블로그

1. 최단 경로최단 경로 정의간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(dijkstra) 알고리즘 : 음의 가중치를 허용하지 않습니다.벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워샬(Floyd-Warshall) 알고리즘2. Dijkstra 알고리즘시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식입니다.시작정점(s)에서 끝정점(t)까지의 최단 경로에 정점 x가 존재합니다.이때, 최단경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로로 구성됩니다.탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사합니다.

1. 최소 신장 트리(MST)그래프에서 최소 비용 문제1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리2) 두 정점 사이의 최소 비용의 경로 찾기신장 트리n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리(Minimum Spanning Tree)무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리2. Prim 알고리즘하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식1) 임의 정점을 하나 선택해서 시작2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택3) 모든 정점이 선택될 때까지 1), 2) 과정을 반복서로소인 2개의 집합(2 disjoi..

1. 서로소 집합(Disjoint-sets)서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들입니다. 다시 말해 교집합이 없습니다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분합니다. 이를 대표자(representative)라 합니다.상호배타 집합을 표현하는 방법연결 리스트트리상호배타 집합 연산Make-Set( x )Find-Set( x )Union( x, y )2. 상호 배타 집합 표현  - 연결리스트3. 상호 배타 집합 표현 - 트리4. 상호 배타 집합에 대한 연산

1. BFS(Breadth First Search)너비우선탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식입니다.인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용합니다.2. 큐큐(Queue)의 특성스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제됩니다.선입선출구조(FIFO : First In First Out)3. 큐의 구조 및 기본 연산4. 큐의 구현5. BFS(Breadth First Sea..

1. 문제 제시 : 친구관계2. 그래프 순회(탐색)그래프 순회는 비선형구조인 그래프로 표현된 모든 자료 (정점)를 빠짐없이 탐색하는 것을 의미합니다.두 가지 방법깊이 우선 탐색(Depth First Search, DFS)너비 우선 탐색(Breadth First Search, BFS)3. DFS(깊이 우선 탐색)시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법입니다.가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용합니다.4. 스택스택(stack)..

1. 문제 제시 : 친구 관계2. 그래프그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현합니다.그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조|V| : 정점의 개수, |E| : 그래프에 포함된 간선의 개수|V| 개의 정점을 가지는 그래프는 최대 |V| ( |V| - 1) / 2 간선이 가능합니다. 예를 들어, 5개 정점이 있는 그래프의 최대 간선 수는 10(= 5 * 4 / 2) 개입니다.선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이합니다.3. 인접 정점4. 그래프 경로5. 그래프 표현6. 인접 행렬7. 인접 리스트

1. 힙(heap)완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조입니다.최대 힙(max heap)키 값이 가장 큰 노드를 찾기 위한 완전 이진트리부모 노드의 키 값 > 자식 노드의 키 값루트 노드 : 키 값이 가장 큰 노드최소 힙(min heap)키 값이 가장 작은 노드를 찾기 위한 완전 이진트리부모 노드의 키 값 루트 노드 : 키 값이 가장 작은 노드2. 힙 연산 - 삽입3. 힙 연산 - 삭제힙에서는 루트 노드의 원소만을 삭제할 수 있습니다.루트 노드의 원소를 삭제하여 반환합니다.힙의 종류에 따라 최댓값 또는 최솟값을 구할 수 있습니다.우선순위 큐와 비교4. 힙의 활용

1. 이진 탐색 트리2. 이진 탐색 트리의 연산3. 이진 탐색 트리 - 성능