순서가 있는 작업을 차례로 진행해야 할때 순서를 결정해 주기 위해 사용하는 알고리즘. 사이클이 없는 방향 그래프의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열한다. 동작 과정 1. 진입 차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐가 공백 상태가 될때 까지 반복 수행한다. 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. ( 연결된 노드의 진입 차수를 감소시킨다.) 2-2) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다. 3. 큐에서 꺼내지는 순서가 위상 정렬을 수행한 결과이다. 위상정렬 - Queue import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public cl..
Algorithm
최단 경로 구하기 하나의 시작 정점에서 끝 정점가지의 최단 경로를 구한다. 다익스트라 알고리즘은 음의 가중치를 허용하지 않는다. 탐욕 기법을 사용한 알고리즘. MST(Minimum spanning tree)의 프림 알고리즘과 유사. 동작 과정 1. 출발 노드를 설정. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정에서 3~4번을 반복한다. 다익스트라 - 우선순위 큐 import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Pri..
크루스칼이 간선을 선택했다면, 프림은 정점을 선택한다. 어떤 정점에서 시작하는지는 상관없다. 동일한 결과. 프림 알고리즘 과정 1. 시작 정점 r의 연결 비용을 0으로, 나머지 정점들의 연결 비용을 무한대로 초기화한다.2. 정점 r을 집합 S의 첫번째 원소로 포함시킨다. 그 후 r에 연결된 나머지 정점들을 살핀다. 그 정점들에 연결된 간선의 비용들을 배열에 저장한다.3. 최소 비용이 드는 정점을 새로 집합 S에 포함시킨다. 그 후 새로 포함된 정점에 연결된 다른 정점들의 비용도 업데이트 한다.4. 모든 정점이 S에 포함될 때까지 3을 반복한다 * 슈도 코드 MST_PRIM(G,r) // G: 그래프, r : 시작 정점 For u in G.V u.key 우선순위 큐를 이용한 프림 알고리즘..
신장 트리 : 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리. 신장 트리는 여러가지. 최소 신장 트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리. 최소 신장 트리도 여러가지 나올 수 있다. 특징 : 무방향 가중치 그래프, 사이클을 포함해서는 안된다. N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다. 크루스칼 알고리즘 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 1. 모든 간선을 가중치에 따라 오름차순 정렬 2. 가중치가 낮은 간선부터 선택하면서 트리를 증가시킨다. - 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다. 3. n-1개의 간선이 선택될때까지 2를 반복. * 슈도 코드 MST-KRUSKAL(G,w) A
상호 배타 집합에 대한 연산 // makeset(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산static void makeset(int i){ p[i] = i;}// findset(x) : x를 포함하는 집합을 찾는 연산static void findset(x){ if(x==p[x]) return x; return findset(p[x]);}// union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산static void union(x,y) { p[findset(y)] = findset(x);}문제점 : 편향 트리의 경우 대표 원소를 탐색하는데 시간이 오래 걸린다. 이를 해결하기 위해 rank와 path compression을 사용한다. 1. rank를 이용한 union..
BFS 알고리즘으로 트리 탐색 트리 : 사이클이 없는 부모와 자식관계가 있는 1: N의 관계 1. Queue 사용하기 * 슈도 코드 BFS(v){ Queue 생성; Queue.add(v); while(!Queue.isEmpty(){ curr = Queue.deq(); // 데이터를 뺀다. curr 방문 For w (curr의 모든자식) Queue.add(w) } } BFS 알고리즘으로 그래프 탐색 트리처럼 하면 stackoverflow 발생 => 방문했는지 안했는지를 check하는 것이 필요하다. 미리 방문처리를 해야한다. Queue에서 꺼내졌을때 방문처리를 하면 중복된 값이 들어가서 메모리 낭비가 발생한다. 최단거리를 구할때 BFS를 많이 쓴다. import java.util.LinkedList; im..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE&problemTitle=%EB%AF%B8%EB%A1%9C1&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Solution import java.io.BufferedReader; import java.io.IOExceptio..
DFS 알고리즘으로 트리 탐색 트리 : 사이클이 없는 부모와 자식관계가 있는 1: N의 관계 1. Stack 사용하기 * 슈도 코드 DFS(v){ // v: 루트노드 stack.push(v) while(not stack.isEmpty){ curr = stack.pop for w in (curr의 모든 자식) stack.push(w) } } 2. 재귀 사용하기 * 슈도 코드 DFS(v){ v방문; for(w in (v의 모든 자식) { DFS(v); } } DFS 알고리즘으로 그래프 탐색 트리처럼 재귀를 하면 stackoverflow 발생 => 방문했는지 안했는지를 check하는 것이 필요하다. 1. 재귀함수 * 슈도코드 // G: 그래프, visited : 방문 배열 DFS(v) { visited[v]
그래프 표현 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정해야 한다. 그래프를 표현하는 방법에는 3가지가 있다. 1) 인접행렬 2) 인접리스트 3) 간선의 배열1. 인접행렬 2차원 배열을 사용. 차수 계산에 용이. 장점: 구현이 간단하다. 조회가 쉽다. 단점 : o(n^2)의 시간복잡도, 공간 낭비. public class 그래프_인접행렬 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //정점의 개수(V)와 간선의 수(E)가 주어진다. int V = sc.nextInt(); int E = sc.nextInt(); //인접행렬 int[][] adjArr = new int..
