1. 선정 과정 (selection procedure)
2. 적정성 점검 (feasibility check)
3. 해답 점검 (solution check)
void minChange(int changes[], int amount, int &c[]){
c[] = {0,};
for(i=0; i<r; i++) // r: 배열 크기
while(amount >= changes[i]){
c[i]++;
amount -= changes[i]
}
}
1. Y = {v1}
2 | 3 | 4 | 5 |
1 | 1 | 1 | 1 |
2 | 3 | 4 | 5 |
1 | 3 | ∞ | ∞ |
2. Y = {V1, V2}
2 | 3 | 4 | 5 |
1 | 1 | 2 | 1 |
V3~V5 정점이 V1과 V2 중에 어떤 정점과 더 가까운지 표시 (이미 Y에 포함한 정점은 이전 값 그대로 사용)
2 | 3 | 4 | 5 |
-1 | 3 | 6 | ∞ |
방문했으면 distance는 -1로 구분
3. Y = {V1, V2, V3}
2 | 3 | 4 | 5 |
1 | 1 | 3 | 3 |
2 | 3 | 4 | 5 |
-1 | -1 | 4 | 2 |
4. Y = {V1, V2, V3, V5}
2 | 3 | 4 | 5 |
1 | 1 | 3 | 3 |
2 | 3 | 4 | 5 |
-1 | -1 | 4 | -1 |
5. Y = {V1, V2, V3, V5, V4}
2 | 3 | 4 | 5 |
1 | 1 | 3 | 3 |
2 | 3 | 4 | 5 |
-1 | -1 | -1 | -1 |
void prim(int n, number W[][], EdgeSet& F){
index i, vnear;
number min, edge e;
index nearest[2..n]; number distance[2..n];
F = ∅;
for(i=2; i<=n; i++){ // Y = {V1}인 경우
nearest[i] = 1;
distance[i] = W[1][i];
}
for(j=1; j<=n-1; j++){ // Y와 가장 가까운 정점 검색
min = ∞;
for(i=2; i<=n; i++)
if(0 <= distance[i] < min){
min = distance[i];
vnear = i;
}
e = (nearest[vnear], vnear);
F = F ∪ {e};
distance[vnear] = -1; // vnear 포함시켰으면 distance를 -1로 변경
for(i=2; i<=n; i++) // 추가된 정점 포함하여 nearest와 distance 갱신
if(W[i][vnear] < distance[i]){
distance[i] = W[i][vnear];
nearest[i] = vnear;
}
}
}
void initial(int n){
for(i=0; i<=n; i++) parent[i] = -1;
}
set_pointer find(index i){
for(; parent[i] >= 0; i = parent[i]);
return i;
}
bool equal(set_pointer p, set_pointer q){
if(p == q) return true;
else return false;
}
void merge(set_pointer p, set_pointer q){
parent[q] = p;
}
void kruskal(int n, int m, EdgeSet E, EdgeSet& F){
index i, j;
Set_pointer p,q;
edge e;
VertexSet V[1..n];
E에 속한 m개의 간선을 가중치에 따라 오름차순으로 정렬
F = ∅;
Initial(n); // 각 n개의 노드를 서로소의 집합으로 만든다. n개의 서로소 부분집합 초기화
while(|F| < n-1){
e = 아직 고려하지 않은 가중치가 최소인 간선;
i,j = e에 의해 연결되는 정점 색인
p = find(i); // V1이 포함되어 있는 집합
q = find(j); // Vj가 포함되어 있는 집합
if(!equal(p,q)){
merge(p,q); // 두 집합 결합
F = F ∪ {e}; // 간선을 F에 포함
}
}
}
W(m,n) | sparse graph | dense graph | |
Prim | Θ(n^2) | Θ(n^2) | Θ(n^2) |
Kruskal | Θ(mlgm) 또는 Θ(n^2lgn) | Θ(nlgn) | Θ(n^2lgn) |
[알고리즘] Backtracking (백트래킹) (0) | 2022.01.08 |
---|---|
[알고리즘] Greedy Algorithm (2) (0) | 2022.01.08 |
[백준(BOJ)] 11656번: 접미사 배열 (C++) (0) | 2021.08.30 |
[백준(BOJ)] 10824번: 네 수 (C++) (0) | 2021.08.30 |
[백준(BOJ)] 11655번: ROT13 (C++) (0) | 2021.08.30 |