상세 컨텐츠

본문 제목

[알고리즘] Greedy Algorithm (1)

PROGRAMMING/Algorithm

by koharin 2022. 1. 8. 18:06

본문

728x90
반응형

Greedy Algorithm (탐욕 알고리즘)


  • 어떤 선택을 할 때 그 당시 가장 최선의 선택을 하여 문제를 해결하는 알고리즘
  • 순간의 선택은 지역적으로 최적이나, 이런 선택을 모아 얻은 해답이 최적인 보장이 없다.
    • 따라서 얻은 해답이 최적인지 검사하는 절차 필요

 

 

Greedy Algorithm 설계


1. 선정 과정 (selection procedure)

  • 현재 상태에서 가장 좋을 것이라 생각되는(greedy) 해답 찾아서 solution set에 포함

2. 적정성 점검 (feasibility check)

  • 새로 얻은 solution set이 적절한지 결정

3. 해답 점검 (solution check)

  • 새로 얻은 solution set이 최적의 해인지 결정

 

 

거스름돈 문제


1. 거스름돈 문제

  • 문제: 동전의 개수가 최소가 되도록하는 거스름돈 구하기
  • 탐욕 알고리즘
    • 단계 1. 거스름돈 넘지 않는 가장 큰 액수 동전 선택 (selectoin procedure)
    • 단계 2. 동전 선택 후 선택한 동전이 최종 해답에 포함될 수 있는지 검사 (feasibility test)
    • 단계 3. 건네준 동전 총액이 거스름돈과 일치할 때까지 단계 1 반복 (solution check)
  • 예) 100원, 50원 10원 동전에서 210원에 대한 거스름: 3개 (100원 X 2 + 10원 X 1)
  • 예) 120원, 100원, 50원, 10원 동전이 있을 때 210원에 대한 거스름: 6개 (120원 X 1 + 50원 X 1 + 10원 X 4) => 최적의 해가 아니다. 

 

2. 거스름돈 문제 알고리즘

  • 문제: 동전의 개수가 최소가 되도록 하는 거스름 돈
  • 입력
    • change[] : 액면가가 큰 순서대로 정렬
    • amount: 거스름 돈 액수
  • 출력
    • c[]: 거스름돈에서 필요한 각 동전의 개수 저장
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]
        }
}

 

 

최소비용 신장트리(MST)


1. 신장 트리(spanning tree)

  • 연결된 무방향 그래프에서 모든 정점을 포함하는 트리 형태의 부분 그래프
  • 순환경로(cycle)가 없는 모든 정점을 포함하는 부분 그래프

  • 트리의 특징
    • cycle이 없는 모든 정점을 연결한 그래프
    • 정점이 n개이면, 트리의 간선의 수의 (n-1)개이다. 하나라도 간선이 추가되면 cycle이 생겨서 트리가 아니게 된다.
  • 무방향 그래프의 형식적 정의
    • 무방향 그래프 G는 정점의 유한 집합 V와 V에 속한 정점의 쌍(간선)의 집합 E로 구성된다.
    • G = (V, E)
    • V의 원소 Vi와 Vj를 연결한느 간선은 (Vi, Vj)로 표시
    • G의 신장 트리 T = (V, F)이다.
      • T의 정점 집합은 G와 동일하지만 T의 간선 집합은 G의 간선 집합 E의 부분 집합ㄴ이다.

 

2. 최소 비용 신장트리 (MST, Minimum Spanning Tree)

  • 연결된 가중치 무방향 그래프의 신장트리 중 모든 간선의 합이 최소가 되는 신장트리

 

3. 최소 비용 신장트리  Greedy Algorithm

  • 문제: 비방향성 그래프 G = (V,E)가 주어졌을 때 F ⊆ E를 만족하면서 (V,F)가 G의 최소 비용 신장트리(MST)가 되는 F를 찾는 문제
  • 알고리즘
    • 문제가 해결될 때까지 다음을 반복 
    • 선정 절차: 지역적으로 최적인 간선 선택
    • 적정성 검사: 선택한 간선이 순환경로 만드는지 검사. 만들지 않으면 F에 추가
    • 해답검사: T = (V,F)가 신장트리인지 검사

 

4. Prim 알고리즘

  • 초기: F = 공집합, Y = {V1}
  • 사례가 해결될 때까지 다음을 반복
    • V-Y에서 가장 Y와 가까운 정점 선택 (선정 절차 + 적정성 검사)
    • 선택한 정점을 Y에 추가하고, 해당 간선을 F에 추가
    • Y = V(모든 정점을 선택했으면)이면 종료. T = (V,F)가 최소비용 신장트리(해답 검사)
  • Prim 알고리즘의 자료구조
    • 인접행렬 W[i][j]: Floyd의 최단경로 알고리즘에서 사용한 행렬과 같은 행렬 (n x n 행렬)
    • nearest[i]: Y에 속한 정점 중 Vi와 가장 가까운 정점의 색인
    • distance[i]: Vi와 nearest[i]를 잇는 간선의 가중치 값
  • 예) 

1. Y = {v1}

  • nearest
2 3 4 5
1 1 1 1
  • distance
2 3 4 5
1 3

 

2. Y = {V1, V2}

  • nearest
2 3 4 5
1 1 2 1

V3~V5 정점이 V1과 V2 중에 어떤 정점과 더 가까운지 표시 (이미 Y에 포함한 정점은 이전 값 그대로 사용)

  • distance
2 3 4 5
-1 3 6

방문했으면 distance는 -1로 구분

 

3. Y = {V1, V2, V3}

  • distance가 가장 작은 3 선택해서 Y에 포함
  • nearest
2 3 4 5
1 1 3 3
  • distance
2 3 4 5
-1 -1 4 2

 

4. Y = {V1, V2, V3, V5}

  • distance가 가장 작은 5 선택해서 Y에 포함
  • nearest
2 3 4 5
1 1 3 3
  • distance
2 3 4 5
-1 -1 4 -1

 

5. Y = {V1, V2, V3, V5, V4}

  • nearest
2 3 4 5
1 1 3 3
  • distance
2 3 4 5
-1 -1 -1 -1
  • Y = V 이므로 종료

 

  • 알고리즘
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;
            }
    }
}

 

Prim 알고리즘 시간복잡도 분석

  • 기본 연산: 비교 연산
  • 입력 크기: n
  • 분석
    • for(j=1; j<=n-1; j++) => (n-1)번 반복
    • for(i=2; i<=n; i++) => (n-1)번 반복
    • for(i=2; i<=n; i++) => (n-1)번 반복
    • T(n) = (n-1)*2(n-1) ∈ Θ(n^2)

 

 

5. kruskal 알고리즘

1) 분리집합

  • 분리 집합(disjoint set)
    • 집합의 모든 원소는 수 0, 1, ..., n-1
    • 임의의 두 집합은 어떤 원소도 공유하지 않음
    • 자식에서부터 부모로 가는 링크로 연결 (자식은 부모가 누구인지에 대한 정보 가짐)

  • 연산
    • 분리 합집합(disjoint set union) merge(Si, Sj)
      • Si∪Sj = {x|x는 Si 또는 Sj 에 포함되는 모든 원소}
      • 두 트리 중 하나를 다른 트리의 서브트리로 넣음
      • 배열 표현
        • 인덱스(i): 트리 노드
        • 원소: 대응되는 트리 노드의 부모 포인터 (루트의 parent는 -1)
    • 탐색 find(i)
      • 원소 i를 포함하는 집합 탐색

  • 분리집합 알고리즘
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;
}

 

2) Kruskal 알고리즘

  • 단계 1. 각 정점을 하나만 포함하는 n 개의 집합 만든다.
  • 단계 2. 모든 간선을 가중치 값을 기준으로 오름차순 정렬
  • 단계 3. 가중치가 가장 작은 것부터 검사하여 간선이 서로 소(disjoint)인 두 집합을 연결하면 그 간선을 F에 추가하고, 연결된 두 집합을 하나의 집합으로 결합
  • 단계 4. F가 MST가 될 때까지 단계 3 반복
  • 예)

  • 간선을 오름차순으로 정렬
  • F = {(v1,v2)} => {(v1,v2), (v3,v5)} => {(v1,v2), (v3,v5), {v3,v4}}
  • (v2,v3)의 경우 cycle이 생기므로 선택 X
  • 정점 5일 때 모든 정점을 포함하는 간선 4개를 포함하는 MST 트리 생성했으므로 종료
  • 알고리즘
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에 포함
        }
    }
}

 

3) Kruskal 알고리즘 분석

  • 최악의 경우 분석
    • 기본 연산: 비교
    • 입력 크기: 정점의 수 n, 간선의 수 m
    • 고려사항
      • 정렬에 소요되는 비용: Θ(mlgm)
      • while 루프: 최악의 경우 모든 간선 고려 -> m번 반복 -> 비용: Θ(mlgm)
      • V[i] 집합 초기화 비용: Θ(n)
    • n < m이므로 전체 비용: Θ(mlgm)
    • m은 최악의 경우 n(n-1)/2이므로 전체 비용은 Θ(n^2lgn)

 

6. Prim 알고리즘 vs. Kruskal 알고리즘

  • m (edge 수) 범위: n-1 <= m <= n(n-1)/2
  • 시간복잡도
  W(m,n) sparse graph dense graph
Prim Θ(n^2) Θ(n^2) Θ(n^2)
Kruskal Θ(mlgm) 또는 Θ(n^2lgn) Θ(nlgn) Θ(n^2lgn)

 

728x90
반응형

관련글 더보기