전공/알고리즘

Disjoint-set- 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.- 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.- 서로소 집합을 표현하는 방법 : 연결리스트, 트리- 서로소 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y) 연결 리스트- 같은 집합의 원소들은 하나의 연결리스트로 관리한다.- 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.- 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 트리- 같은 집합의 원소들을 하나의 트리로 표현한다.- 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.  트리의 배열을 이용하면 아래와 같다.  자바로 나타내보기public class DisjoinSetTest {..

그래프란그래프는 아이템들과 이들 사이의 연결 관계를 표현한다.- vertex: 연결점, edge: 연결된 간선 의 수 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조- V개의 정점을 가지는 무향 그래프는 최대 V*(V-1)/2 간선이 가능 ex) 5개 정점이 있는 무향 그래프의 최대 간선 수는 10 (5*4/2)개이다. 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N관계를 가지는 원소들을 표현하기에 용이하다. 그래프 유형무향 그래프, 유향 그래프, 가중치 그래프, 사이클 없는 방향 그래프(DAG) 완전 그래프- 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프- 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 트리도 그래프이다- 각 노드는 최대 하나의 ..