Algorithm & DS

Hash Table 또는 Hash Map은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다. Hash Tabel 의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1) 이라는 것이다.덕분에 데이터 양

유튜브 동빈나 채널의 (이코테 2021 강의 몰아보기) 3. DFS & BFS 를 보면서 정리한 내용입니다.DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작

그래프 내의 모든 정점을 포함하는 트리Spanning Tree == 신장 트리 == 스패닝 트리Spanning Tree는 그래프의 최소 연결 부분 그래프 이다. 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고,

이번 포스팅에서는 그래프 알고리즘 종류 중 하나라고 할 수 있는 서로소 집합 자료구조를 활용한 알고리즘에 대해 알아보려고 한다. 그래프 알고리즘 종류로는 그리디 알고리즘이라고도 할 수 있는 크루스칼 알고리즘과 스택과 큐를 활용해야 하는 위상 정렬 알고리즘이 있다. 이러

대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류된다.구체저인 동작 과정은 다음과 같다. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.간선을 하나씩 확인하며 현재의 가선이 사이클을 발생시키는지 확인한다. 1) 사이클이 발생하지 않는 경우 최소 신장 트

시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택해가며 최소 신장 트리를 확장해가는 방식임의의 정점을 선택하여 '연결된 노드 집합'에 삽입선택된 정점에 연결된 간선들을 간