공부방

순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘 사이클이 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것 진입 차수 : 특정 노드로 들어오는 간선의 개수 진출 차수 : 특정 노드에서 나가는 간선의 개수 진입 차수가 있다는 것은 선행 조건이 있다는 뜻이므로 진입 차수가 더 중요! 위상 정렬 방법(Queue 사용) 진입 차수가 0인 모든 노드들 Queue에 삽입 Queue가 공백상태가 될 때까지 반복 수행 Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. (연결된 노드의 진입 차수를 감소시킨다.) 새롭게 진입 차수가 0이 된 노드를 Queue에 삽입한다. Queue에서 꺼내지는 순서(Queue 들어온 순..

프림 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1. ,2. 과정을 반복 반복문 package day0330_프림_다익스트라; import java.util.Arrays; import java.util.Scanner; public class 프림_반복문 { static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { //Scanner sc = new Scanner(System.in); Scanner sc = new Scanner(input..

서로소 집합 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호배타 집합을 표현하는 방법 연결 리스트 트리 상호 배타 집합 연산 Make-Set(x) : x라고 하는 원소를 대표자로 만든다. Find-Set(x) : x의 대표자 불러온다. Union(x,y) : 하나의 그룹으로 만든다. 상호 배타 집합 표현-트리 하나의 집합(a disjoint set)을 하나의 트리로 표현한다. 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연산의 효율을 높이는 방법 Rank를 이용한 Union 각 노드는 자신을 루트로 하는 subtree의 ..

트리(그래프, 2차원 배열) 순회(탐색)은 모든 자료(노드, 정점)을 빠짐 없이 탐색하는 것을 의미한다. 깊이 우선 탐색(Depth First Search, DFS) 루트 노트(시작 정점, 출발 위치)에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드(정점)로 되돌아와서 다른 방향의 노드(정점)으로 탐색을 계속 반복하여 결국 모든 노드(정점)을 방문하는 순회방법 가장 마지막에 만났던 갈림길의 노드(정점)로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 자료구조인 스택 사용 재귀 함수는 시스템 스택을 이용하므로 이를 이용하여 간단하게 구현할 수도 있음. 문제 유형 경로 탐색 : 두 정점 사이의 경로..

그래프 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계 표현 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 선형자료구조(1:1)나 트리자료구조(1:N)로 표현하기 어려운 M:N관계를 표현 가중치 그래프(Weighted Graph) : 간선에 값이 있는 그래프 순환 그래프(Cycle graph): 사이클이 있는 그래프 완전 그래프 정점에 대해 가능한 모든 간선들을 가진 그래프 간선 의 수 : N(N-1)/2개 부분 그래프 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 인접 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다. 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다. 경로 간선들을 순서대로 나열한 것 간선 : (0..