1. SCC (Stronlgy Connected Components) 1) SCC SCC는 연결되어 있는 그래프들 끼리 나누는 알고리즘이다. 무방향 그래프로 표현한다면 다음과 같이 정의할 수 있다. 하지만 다음과 같은 방향성 그래프에서는 1에서 10으로 이동이 가능하나, 10에서 1로 갈 수 없기 때문에 무방향 그래프처럼 그룹을 나눌 수 없다. 따라서 방향성 그래프를 그룹별로 나누기 위해서는, 그룹 내의 노드가 서로 양방향으로 도달할 수 있는 길이 있어야 한다. 예를 들어 '1 - 2 - 3'에서 1과 2를 본다면, 1은 2로 이동이 가능하고, 2도 3을 거쳐 1로 이동이 가능한 구조여야 하나의 그룹으로 지정할 수 있다는 뜻이다. 즉, 하나의 그룹 내에 특정 두 개의 노드 x, y는 x에서 y로, y에서..

1. 최소 스패닝 트리 1) 최소 스패닝 트리 우선 최소 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 한 가지 그래프가 있을 때, 여러가지 스패닝 트리가 존재할 수 있으며, 한 가지 스패닝 트리에서 선택된 간선의 가중치의 합이 해당 스패닝트리의 가중치를 정의할 수 있다. 이 과정에서 모든 스패닝 트리중에서 가중치가 가장 작은 스패닝 트리를 물어보는것이 최소 신장 트리, 최소 스패닝 트리라고 한다. 즉, 그래프의 모든 노드를 포함하는 트리중 간선의 가중치의 합이 최소인 트리를 뜻한다. 2) Cut Property Cut Property는 최소 스패닝 트리에서 정리하는 과정을 뜻한다. 그래프를 잘라, 노드를 두 그룹으로 나누고(Cut), 두 개의 트리를 잇는 간선 중, 가중치가 가장 작은 것을 기..

1. 기초 그래프 알고리즘 최단경로 알고리즘 Strongly Connected Component 최소 신장 트리 2. 최단경로 1) 최단경로 A에서 B까지 가는 최단경로를, 간선의 가중치(Weight)를 이용하여 구하는 알고리즘이다. 최단경로 알고리즘을 해결하는 대표적인 3가지 알고리즘은 다음과 같다. 다익스트라 알고리즘 : 하나의 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 단, 간선의 가중치가 양수일 때만 사용한다. 플로이드 알고리즘 : 모든 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 벨만포드 알고리즘 : 하나의 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. 단, 간선의 가중치가 양수, 음수 모두 가능하다. ※ 정점 x까지 최단거리로 가기 위해서는 그 직전까지의 ..

1. 깊이 우선 탐색 (DFS) 1) 깊이 우선 탐색 깊이 우선 탐색은 스택을 이용하여 그래프를 순회하는 방법이다. '나'를 먼저 방문하고 그 다음으로 인접한 노드를 차례로 방문하는 방법이다. (단, 방문했던 노드를 방문하지 않는다.) 예를 들어, 다음과 같은 그림에서 인접한 노드가 여러개일 경우 노드 번호가 작은 노드부터 방문한다고 했을 때, 1을 시작으로 DFS한 결과는 '1 - 2 - 3 - 5 - 6 - 7 - 8 - 9 - 4 -10 - 11' 이 된다. 2) 구현 DFS(v, visited) - v는 시작점, visited는 방문한 노드 기록 v를 방문했다고 처리 v와 인접한 모든 w에 대해 다음을 반복 만약 w를 방문하지 않을 경우 DFS(w, visited) 방문 순서 반환 ※ DFS는 재..

1. 자료구조 스택 큐 트리 그래프 2. 그래프 1) 그래프 그래프는 정점과 간선으로 이루어진 자료구조이다. 현실 세계의 많은 것들을 그래프로 나타낼 수 있기에(지하철 노선, 지도, 페이스북, 등) 그래프와 관련된 문제가 매우 많다. 따라서 그래프와 관련된 수학적 정리가 매우 많으며 이론도 어렵고 구현도 어렵다. 그래프의 용어는 4가지가 있다. 정점 (Node) 간선 (Edge) 차수 (Degree) : 정점에 연결된 간선의 개수 사이클 (Cycle) : 특정 노드에서부터 시작해 다시 자기 자신으로 돌아올 수 있는 경로 그래프에 관한 기본적인 수학적 지식은 다음과 같다. 간선의 개수는 정점의 제곱보다 작거나 같다. 각 정점의 차수의 합은 간선의 개수의 2배와 같다. 2) 인접 행렬 구현 그래프는 2차원 ..

1. 동적 계획법 1) 동적 계획법과 분할 정복법 동적 계획법은 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 방법이다. 대표적으로 피보나치 수를 구하는 문제가 있다. 처음이라면 분할 정복법과 혼동될 수 있지만, 피보나치 수를 구하기 위해 다음과 같이 작성한 재귀함수를 예시를 든다면 차이를 확인할 수 있다. static int fibonacci(int n) { if(n == 0 || n == 1) return n; return fibonacci(n-1) + fibonacci(n-2); } 예를 들어 4를 넣어본다면, 중복된 계산을 계속 진행함을 확인할 수 있다. f(4) = f(3) + f(2) f(4) = ( f(2) + f(1) ) + f(2) f(4) = ( ( f(1) + f(0) ) ..