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가지에 대한 판단이 가능하다.현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지위상 ..
0. 병합 정렬병합 정렬은 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘이다.가장 일반적인 O(N^2)인 삽입, 선택, 버블 정렬보다 빠르며,많이 쓰이는 퀵 소트보다 높은 안정성을 보여준다.퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이기 때문이다.(이 이유때문에 알고리즘 문제에선 절대 퀵소트를 써선 안된다...)자세한 건, 퀵 소트를 찾아보면 이해가 될 것이다.1. 알고리즘n의 길이를 가진 배열을 절반(m) 크기의 배열로 쪼갠다.쪼개진 배열의 길이가 2가 될 때까지 1번을 반복한다.쪼개진 두 배열을 [그림 1]과 같이 정렬한다.m 길이의 정렬된 배열을 통해 2 * m 길이의 배열도 정렬한다.2 * m이 n이 될때까지 4번을 반복한다. 2. 코드3. 참고https://www.yo..
0. 그래프그래프는 아이템과 이들 사이의 연결 관계를 표현하는 자료구조이다.그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조이다.정점(Vertex): 그래프의 구성요소로 하나의 연결점간선(Edge): 두 정점을 연결하는 선차수(Degree): 정점에 연결된 간선의 수인접(Adjacency): 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.경로(Path): 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 나열한 것싸이클(Cycle): 경로의 시작 정점과 끝 정점이 같음(시작한 정점에서 끝나는 경로)V개의 정점을 가지는 무향 그래프는 최대 V * (V-1) / 2개의 간선이 가능하다.선형 자료구조나 트리..
