알고리즘/이론 (16) 썸네일형 리스트형 서로소 집합(Disjoint-set) 서로소 집합 : 서로소 또는 상호 배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 집합에 속한 하나의 특정 멤버(representative) 를 통해 각 집합들을 구분한다. 상호배타 집합을 표현하는 방법 : 연결리스트, 트리 상호배타 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y) CODE 1. Make-Set(x) void makeSet(int x) { parents[x] = x; } 2. Find-Set(x) int findSet(int x) { if(x == parents[x]) return x; else { parents[x] = findSet(parents[x]); return findSet(parents[x]); } } 3. Union(x, y) vo.. 프림 알고리즘 (Prim Algorithm) 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 정점을 하나씩 선택할 때마다 간선을 추가하면서 트리 확장 두 종류의 상호배타집합 정보를 유지 - 트리 정점들(tree-vertices) : MST를 만들기 위해 선택된 정점들 - 비트리 정점들(non-tree vertices) : 선택 되지 않은 정점들 동작과정 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때까지 1, 2 과정을 반복 import java.util.Arrays; import java.util.Scanner; /* 7 11 0 1 2 0 2 2 0 5 8 1 2 1 1 3 19 2 5 5 3 4 7 3 5 11 3 6 15 4 .. 크루스칼 알고리즘 (Kruskal Algorithm) 1. 신장트리 : 그래프의 모든 정점과 간선의 부분집합으로 구성되는 트리 2. 최소신장트리(MST) : 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 - 무방향 가중치 그래프 - 그래프의 가중치의 합이 최소여야 한다. - N개의 정점을 가지는 그래프에 대해 반드시 (N-1) 개의 간선을 사용해야 한다. - 사이클을 포함해서는 안된다. 3. Kruskal Algorithm - 탐욕적인 방법을 이용하여 가중그래프(가중치를 간선에 할당한 그래프)의 모든 정점을 최소비용으로 연결하는 최적해를 구하는 것 - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 - 동작과정 ① 그래프의 간선들을 가중치의 오름차순으로 정렬한다. ② 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. a. 가.. 순열 (Permutation) SW 역량테스트문제를 풀면서, 완전 탐색 (브루트포스) 문제를 해결할 때 필수적인 개념인 순열에 대해서 정리하려고 합니다. 브루트포스 문제를 만나면 단순 반복문을 통해 탐색하는 문제가 아닌, 재귀와 백트래킹을 통한 순열 또는 조합이 엮인 문제가 많은 것 같습니다. 그래서 순열과 조합에 대한 부분은 반드시 완벽하게 이해하고 문제를 풀어야 합니다. 그림만 통해서 저는 이해하기 어려웠기 때문에 문제와 그림을 통해서 정리해보겠습니다. 순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말합니다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시하기도 합니다. [네이버 지식백과] 순열 [Permutat.. 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘을 공부하기 전에, 스패닝 트리에 대해서 먼저 알아야 한다.span 은 '완전히 덮다' 라는 느낌의 뜻을 가지고 있는 단어이고, 트리는 사이클이 없는 그래프이다.그래서 스패닝 트리는 그래프의 모든 노드를 포함하는 트리이다. 위의 경우에도 스패닝 트리이고, 밑의 경우에도 스패닝 트리이다.하나의 그래프에서 스패닝트리는 여러개 존재할 수 있다.스패닝 트리의 가중치를 합하면 weight를 알 수 있는데, 그래프에서 weight의 값이 최소인 스패닝 트리를최소 스패닝 트리 (Minimum Spanning Tree) 이라고 한다. 위의 그래프에서 표시된 트리가 최소 스패닝 트리이다.크루스칼 알고리즘을 알기 위해서 또 알아야할 개념중에 하나가 Cut Property 라는 것이다.T1과 T2는 서로 다.. 다익스트라 알고리즘 (Dijkstra's Algorithm) 최단경로를 구하는 알고리즘인 다익스트라 알고리즘을 공부하고자 한다.다익스트라 알고리즘은 한 점에서 모든 점까지 최단거리를 구하는 알고리즘인데, 가중치가 양수일 때만 사용하는 알고리즘이다.예시에서는 1에서 7까지 도달하는 최단경로를 구한다고 해보자. 먼저 시작정점 1까지는 최단경로 0으로 왔기 때문에 최단경로 0으로 도착했다고 표시한다.그리고 다음 경로로 2와 6으로 갈 수 있는데, 1에서 6으로 가는 방법은1 --> 6 과 1 --> 2 --> 6 두가지가 있다. 1에서 2로 가는 방법은 1 --> 6 --> 2 와 1 --> 2 가 있다. 1 --> 2 --> 6 과 1 --> 6 --> 2 를 구하려면2 --> 6 과 6 --> 2 를 알아야 하는데, 아직 1 --> 6 로 갈지 1 --> 2 로 갈.. 최단경로 알고리즘 노드와 노드를 이어주는 간선의 어떤 값을 부여한 것을 간선의 가중치(weight)라고 한다.최단경로 문제는 어떤 노드부터 노드까지 가는 경로의 가중치의 최솟값을 구하는 문제이다. 위의 경로대로 A부터 B까지 가면 1+1+1+2+9 = 14 가 경로의 가중치를 모두 합한 값이다.하지만 이것은 최단경로가 아니므로 그래프에서 최단경로를 구해보면 12로 다음와 같다. 기초 최단경로 알고리즘은 세가지가 있는데, 특징은 위와 같다.플로이드 알고리즘은 모든 정점에서 모든 정점까지 최단거리를 구하지만, 그만큼 시간이 많이걸린다.다익스트라와 벨만포드 알고리즘의 차이점은 가중치의 음수값이 있느냐 없느냐에 따라 나뉜다. 최단경로 문제를 풀 때 중요한 특징은 2가지가 있는데첫번 째는 X까지 최단거리로 가기 위해서는 그 직전의.. 넓이우선탐색 (Breadth First Search) BFS는 DFS와 다르게 Queue를 이용하여 그래프를 순회하는 방법이다. 제일 먼저시작하는 노드를 큐에 push하고 색칠한 후에 시작한다. 그 다음에① pop 하는 노드에서 인접한 노드들을 큐에 넣고 색칠한다.② 더이상 넣을 노드들이 없다면 큐에서 pop을 한다.이런식으로 동작한다. 예를 들어 설명해보자. 위에 그림에서 1에서부터 시작하므로1을 큐에 넣고 방문했다고 색칠한다. 1을 pop하고 나면, 이제 1에 인접한 노드들을 확인 한다. 즉 2와 4를 push 하고 방문했다고 색칠한다.현재 큐 상태는 1이 pop되어 있는 상태이고, 큐에 2와 4가 들어가있다.이제 1에 인접한 모든 노드 2와 4를 큐에 넣었으므로 더이상 넣을 노드가 없다.그러므로 현재 큐에서 pop을 해보면 front에 있는 2가 po.. 이전 1 2 다음
