티스토리 뷰
정의
그리디 알고리즘은 최적화 문제를 해결하는 알고리즘
최적화(optimization) 문제 : 가능한 해들 중(선택 순간)에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제
욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불린다.
이름만큼 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 '욕심내어' 최소값 또는 최대값을 가진 데이터를 선택하는 것.(부분적인 최적해(Partial Solution)) 당장 눈 앞의 선택을 하기 때문에 '근시안적'선택이라고도 말한다. 이들을 모아 문제의 최적해(Final Solution)를 구한다.
\
특징
-그리디 알고리즘은 한 번 선택하면 이를 절대로 번복하지 않는다. 뒤에 나쁜 결과가 나와도 선택한 데이터를 버리고 다른 것을 취하지 않는다.
-대부분의 그리디 알고리즘은 매우 단순하고 직관적이다. 현재 경우의 수만 잘 잡아주면, 심플하게 가장 좋은 것만 선택하면 된다.
-재현적인 문제들만이 그리디 알고리즘으로 해결된다. 하지만 항상 최선은 아니다.
예시
1.동전 거스름돈 문제
-남는 액수를 초과하지 않는 조건하에 '욕심내어' 가장 큰 액면의 동전을 취해야 한다.
- 동전 거스름돈 문제의 Pseudo Code
CoinChange(Pseudo Code)
입력: 거스름돈 액수 w
출력: 거스름돈 액수에 대한 최소 동전 수
change=w n500=0 n100=0 n50=0 n10=0 n1=0//동전 카운트
while( change >= 500 )
change= change-500, n500++
while( change >= 100 )
change= change-100, n100++
while( change >= 50 )
change= change-50, n50++
while( change >= 10 )
change= change-10, n10++
while( change >= 1 )
change= change-1, n1++
return (n500+n100+n50+n10+n1) //총 동전 수를 리턴한다.
2.최소 신장 트리 구하기(MST)
-트리란?
서로 다른 두 노드를 잇는 길이 하나뿐인 그래프
-최소 신장 트리란?
주어진 가중치 그래프에서 사이클이 없이 모든 점(node, vertex)들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리
-주어진 그래프에서 최소 신장 트리를 찾는 방법.
1.kruskal MST : 전체 그래프에서 가중치가 작아보이는 edge부터 조합해본다. edge부터 찾고 graph를 생각하자!
2.Prim MST : 임의의 vertex 하나를 선택한 후, edge를 하나씩 추가시켜 트리를 만든다. 자세한 건 다음 게시물에...
-주의할 점
edge의 개수=vertex의 개수 -1
cycle이 만들어지지 않도록 주의
-Kruskal MST의 Pseudo Code
그래프 vertext 수 = n
edge 수 = m
가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자.
트리 T를 초기화시킨다.
while(T의 선분 수 <n-1){
L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다.
if(선분e가 T에 추가되어 사이클을 만들지 않으면)
e를 T에 추가시킨다.
else //사이클이 만들어지면
e를 버린다.
}
return T-Kruskal MST의 Time Complexity
Total Time Complexity에 유의미한 값은 Cycle Check와 edge 정렬
Total=Cycle check *(n-2)+edge 정렬 O(nlogn)
Cycle check 방법은
E1,E2가 vertex를 모두 포함하는지를 체크한다. ->2개의 set를 합치고 조건문으로 판별 필요 ->Union/Find 알고리즘
이 때 heap을 사용.=>O(log*) 거의 1에 가까운 값이라고 한다.
따라서 Kruskal 알고리즘을 구현하기 위해서는
1.그래프 형태 구현
2.Sorting
3.Union/Find
의 내용이 필요하다.
-Union/Find
'합집합 찾기'
여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
1.초기화 과정. Make-set
2.Union
1과 2를 연결시키는 Union(1,2)를 적용하면 1이 2를 가리키는 그림이 된다.
union을 실행하면 1과 2의 루트를 찾는다. 두 루트가 같다면 이미 같은 트리에 속해 있으므로 아무런 작업도 하지 않는다.
다르다면 한 노드를 다른 노드의 부모로 설정한다.
3.Find
부모를 따라 반복적으로 이동하여 트리의 루트를 반환한다.
1의 부모를 찾기 위해서 1의 값인 2를 따라가야 한다. 2의 값은 2로, 1의 부모는 2가 된다. 여기서 2의 부모 또한 2이기 때문에, 두 노드는 같은 그래프에 속한다. 다른 부모를 가리키는 나머지 노드들은 다른 그래프에 속한다.
4.Kruskal MST에 적용
Kruskal MST에서 가중치가 가장 적은 edge를 선택하고, 사이클 여부를 검사할 때 Union을 이용할 수 있다.
(1)그래프의 노드 개수가 N개라면 N개의 원소를 갖는 Union/Find구조를 초기화한다.
(2)edge 양끝의 두 노드에 대해 Union(x,y)연산을 수행한다.
(3) 실제로 두 트리가 병합하면 해당 edge를 MST에 추가한다.
(4) x와 y의 부모가 같으면 사이클이 발생한다는 의미이다. 이 때는 edge를 MST에 추가하지 않는다.
-소스코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//부모 노드 찾기
int getParent(int parent[], int x) {
if (parent[x - 97] == x) return x;//부모가 자기 자신을 가리키고 있으면 그대로 반환
return parent[x-97] = getParent(parent, parent[x-97]);//부모가 다른 노드를 가리키고 있으면 그 노드가 가리키는 값을 찾는다.
}
//두 부모 노드를 연결
void unionParent(int parent[], int a, int b) {
a = getParent(parent, a);//부모가 가리키는 값을 찾아온다.
b = getParent(parent, b);
//더 숫자가 작은 부모로 병합
if (a < b)
parent[b-97] = a;
else
parent[a-97] = b;
}
//같은 부모를 가지는지 확인. 두 노드가 같은 그래프에 존재하면 1, 아니면 0
int findParent(int parent[], int a, int b) {
a = getParent(parent, a);
b = getParent(parent, b);
if (a == b)
return 1;
else
return 0;
}
//edge 클래스 선언
class Edge {
public:
int node[2];
int distance;
Edge(int a, int b, int distance) {
this->node[0] = a;
this->node[1] = b;
this->distance = distance;
}
bool operator <(Edge& edge) {
return this->distance < edge.distance;
}
};
int main() {
int n = 7;
int m = 11; //정점 간선
vector<Edge> v;
vector<Edge> T;
v.push_back(Edge('a', 'b', 8));
v.push_back(Edge('b', 'c', 1));
v.push_back(Edge('c', 'f', 1));
v.push_back(Edge('f', 'e', 9));
v.push_back(Edge('e', 'a', 4));
v.push_back(Edge('a', 'd', 2));
v.push_back(Edge('d', 'b', 4));
v.push_back(Edge('e', 'd', 3));
v.push_back(Edge('d', 'f', 7));
// weight에 따른 edge 정렬. 오름차순
sort(v.begin(), v.end());
cout << "정렬 후=> ";
for (int i = 0; i < v.size(); i++) {
cout << v[i].node[0] << ",";
cout << v[i].node[1] << ":";
cout << v[i].distance << " ";
}
cout << endl;
//그래프의 노드 개수에 따라 N개의 원소를 갖는 Union/Find구조를 초기화한다.
int parent[10000];
for (int i = 97; i < 97 + n; i++) {//노드를 알파벳으로 표시하기 위해 인덱스 0에 알파벳 a의미의 97부터 저장
parent[i - 97] = i;
}
//거리의 합을 0으로 초기화
int sum = 0;
for (int i = 0; i < v.size(); i++) {
//가중치가 적은 edge부터 선택하고, 사이클 여부를 검색한다.
if (!findParent(parent, v[i].node[0], v[i].node[1])) {//두 점의 부모가 같은지 검사한다.
//사이클이 발생하지 않으므로 MST에 추가한다.
sum += v[i].distance;//거리의 합에 가중치 더하기
unionParent(parent, v[i].node[0] , v[i].node[1]);//해당 edge를 MST에 추가
T.push_back(Edge(v[i].node[0],v[i].node[1],v[i].distance));
}
cout << "union 결과: ";
for (int i = 0; i < T.size(); i++) {
cout << (char)T[i].node[0] << ",";
cout << (char)T[i].node[1] << ":";
cout << T[i].distance << " ";
}
cout << endl;
}
cout <<"weight:"<< sum;
}
전체 흐름. (1)~(10)까지 따라갈 것
'강의내용 복습 > 컴퓨터 알고리즘' 카테고리의 다른 글
| Greedy 알고리즘 -Dijkstra 알고리즘 (0) | 2023.04.18 |
|---|---|
| Greedy 알고리즘 - Prim 알고리즘 (0) | 2023.04.16 |
| 분할 정복 알고리즘 - Selection 알고리즘 C언어 (0) | 2023.04.09 |
| 분할 정복 알고리즘-merge sort (1) | 2023.03.21 |
| 컴퓨터 알고리즘- 알고리즘의 첫걸음 (0) | 2023.03.21 |