0. 힙(Heap)완전 이진 트리에 있는 노드에서 가장 큰 키 값이나 가장 작은 키 값을 찾기 위해서 만든 자료구조이다.중복 값도 가능하다.힙의 특징으로는 노드의 삽입 혹은 삭제 연산이 발생할 때만, 해당 노드가 옳바른 자리를 찾아간다.0-1. 최대 힙(Max Heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 >= 자식 노드의 키 값루트 노드: 키 값이 가장 큰 노드0-2. 최소 힙(Min Heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리부모 노드의 키 값 루트 노드: 키 값이 가장 작은 노드1. 힙 연산최대 힙을 기준으로 설명을 할 예정이며, 최소 힙의 경우도 동일하게 동작한다.노드 하나의 삽입 / 삭제 연산은 시간 복잡도가 O(lonN)이고 최대값/최소값을..

0. 최소 신장 트리(MST)신장 트리n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리 (MST, Minimum Spanning Tree)무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 최소 신장 트리를 구하는 대표적인 알고리즘인 Kruskal과 Prim에 대해 알아보자.1. Kruskal 알고리즘크루스칼 알고리즘은 간선 중심 그래프이며, 그리디 알고리즘이다.1-1. 알고리즘간선을 하나씩 선택해서 MST를 찾는 알고리즘모든 간선을 가중치에 따라 오름차순으로 정렬가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴사이클이 발생하면 MST에 포함시키지 않음사이클이 발생하지 않는 경우 MST에 포함n-1개의 간선이 선..

0. 서로소 집합서로소(상호배타) 집합은 서로 중복 포함된 원소가 없는 집합이다. 즉, 교집합이 없는 집합을 의미한다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분하며 이를 대표자(representative)라 한다.서로소 집합을 표현하는 방법연결 리스트트리 → 구현이 쉬움서로소 집합 연산Make-Set(x) - 유일한 멤버 x를 포함하는 새로운 집합을 생성 (서로소 집합 초기화 작업)Find-Set(x) - x를 포함하는 집합을 찾는 연산 (대표자 탐색)Union(x, y) - x와 y를 포함하는 두 집합을 통합하는 연산1. 서로소 집합 표현1-1. 연결 리스트같은 집합의 원소들은 하나의 연결 리스트로 관리한다.연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.각 원소는 집합의 대표원소..

0. 위상 정렬(Topological Sort)위상 정렬은 유향 그래프의 정점들을 나열하는 것을 의미한다.순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘으로 위상 정렬의 결과는 여러 개일 수 있다.가장 잘 설명되는 예시로는 선수과목(prerequisite) 구조이다. 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 수강 순서를 찾아낼 수 있다.위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않는 비순환 유향 그래프(directed acyclic pragh)여야 한다. 위상 정렬은 아래 2가지에 대한 판단이 가능하다.현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지위상 ..