[강의정리] 알고리즘 Greedy Approach
Greedy Algorithm
- Dynamic programming?
- recursive property(재귀함수)로 풀 수 있는 문제를 DP로 풀 수 있음
- Greedy approach
- 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택
- simple is best
- local에서는 최적, 최적을 모아서 최종답을 만들어도 검증까지 해야함
Greedy Approach 설계 절차
- Selection procedure (선정 과정)
- 현재 상태에서 가장 좋다고 생각되는 해답을 찾음
- Fesibility check(적정성 점검)
- 적절한지 결정
- Solution check(해답 점검)
- 최적의 해인지 결정
Spanning Tree (신장 트리)
- 그래프의 모든 vertex G를 가지고 있는 트리
- 비방향성 그래프 G에서 순환 제거, 연결된 부분 그래프가 되도록 이음선 제거
- G안에 있는 모든 정점을 다 포함하면서 트리가 되는 연결된 부분그래프
Minimum Spanning tree(최소비용 신장트리)
- 가중치의 합이 최소가 되는 신장트리
- 그래프는 트리형태(cycle없는)여야함
브루트포스 방식
모든 신장트리를 다 고려해보고, 그중에서 최소비용을 고름
분석:
- 최악의경우, 지수보다 나쁨
Prim’s Algorithm
v1에서 vi까지 모든 정점을 돌면서 가장 가까이 있는 vnear찾음
- nearest[i]: vi에서 가장 가까운 정점
- distance[i]: 거리
Every-case Time Complexity Analysis
단위연산: repeat 루프 안에 있는 두개의 for루프 안의 명령문
inputSize: 마디개수, n
분석: repeat-루프가 n-1번 반복
- T(n) = 2(n-1)(n-1)
최적여부 검증 (Optimality Proof)
Definition
- 만약 E의 부분집합 F에 MST가 되도록 이음선을 추가할 수 있으면 (MST에 F가 포함되어있으면) F는 Promising(유망하다) 하다고 함
Lemma (*중요)
- F는 E의 유망한 부분집합, Y는 F안에 있는 이음선 들에 의해서 연결된 정점의 집합.
- 이때 Y에 있는 어떤 정점과 V-Y에 있는 어떤 정점을 잇는 이음선 중에서 가중치가 가장 작은 이음선을 e라고 하면..
- F + e는 유망하다
Prim’s Algorithm 특징?
- 특정 v1을 기준으로 뻗어나감
Kruskal’s Algorithm
- edge그래프를 기준으로
- Edge List를 sorting해줌
- 순서대로 추가해도 되면 연결
- subset을 merge해줌
- 다연결될 때까지 반복
Worst-Cast Time Complexity Analysis
(시험출제)
- 단위연산: 비교문
- 입력크기: 정점의 수 n과 이음선의 수 m
- 정렬하는데 걸리는 시간 O(m lg m);
- n개의 서로소인 집합 set을 초기화 시간 O(n)
- 루프 m번 수행, 서로소인 집합 자료구조 사용, find, equal, merge등 포함하면 O(m lg n)
여기서 m >= n-1, 1과 3은 2를 지배
W(m, n) = O (m lg m);최악의 경우 모든 정점이 다른 모든 정점과 연결,
M = n(n-1) / 2 = O(n^2), 최악의 경우 시간복잡도는 W(m, n) O(n^2 lg n)
Dijikstra’s Algorithm
- 한 정점에서 다른 모든 정점으로 가는 최단경로 문제
- Single-Source Shortest Paths: 시작점v1
- v1에서 갈수있는 경로로 table을 만듬
- table에서 가장 짧은 거리를 선택해서 그지역을 경유하는 경로까지 비교
- 모든 정점을 경유하는 거리를 비교함
Define touch & length
- touch[i]: I까지 가는 경로의 마지막 노드
- length[i]: 현재까지 구해진 최단거리
length[vnear] = -1로 만들어주는 이유?
- 현재 선택된 노드를 다시 선택하는걸 방지
The Knapsack Problem
- 배낭에 넣을 수 있는 최대 가치(Array)를 구하는 문제
The Knapsack Problem: Greedy
- 탐욕적알고리즘: n개의 물건에 대해 모든 부분집합 고려
- 부분집합의 수는 2^n개
The 0-1 Knapsack Problem
일반 Fractional Knapsack problem: 남은공간 물건을 잘라서 꽉채울수있음
0-1 Knapsack problem: 물건을 못자름
Fractional Knapsack: Greedy로 구할 수 있음(무게당 가치가 가장 높은순)
Dynamic Programming Approach
i > 0, w > 0 최대무게: w
i번째 항목중에서 얻어진 최고의 이익(optimal profit) = P[i][w];
if w[i] <= w:
max(P[i-1][w], p[i] + P[i-1][w-w[i]]);
else:
p[i-1][w];
여기서 P[i-1][w]는 i번째 항목을 포함시키지 않은 경우의 최고 이익,
p[i] + P[i-1][w-w[i]]는 i번째 항목을 포함시키는 경우 최고 이익
최대이익 P[n][W]는?
- intP[0..n][0..W]의 2차원배열을 만든 후 각 항을 계산해서 넣음
- P[0][w] = 0, P[i][0] = 0이므로 O(nW);
DP방법 보완
임의로 W = n!이라 한다면 수행시간은 O(n*n!)이 되므로 무작정 알고리즘보다 나을게 없음
최악을 O[n^2]로 만드는법? 무작위보다 빠르게하는법?
- **P[n][W]를 계산하기 위해 (n-1)번째 행을 모두 계산할 필요 없음)
P[n][W] = max(P[n-1][W], p[n] + P[n-1][W-w[n]]]);
따라서 (n-1)번째 항은 P[n-1][W]와 P[n-1][W-w[n]]만 필요
i번째항에 필요한 항목만 결정해서 계산함Worst case
- O(2^i)
O(min(2^n, nW));
Greedy vs. Dynamic Programming
| Greedy | DP |
|---|---|
| 최적화문제 | 최적화문제 |
| 알고리즘이 존재하면 더 효율적 | 때론 불필요하게 복잡 |
| 단위출발점 최단경로 문제: O(N^2) | 단위출발점 최단경로 문제: O(N^3) |
| 알고리즘이 최적인지 증명해야함 | 최적화원칙이 적용되는지 점검만하면됨 |
| 0-1Knapsack은 못품 | 0-1Knapsack 풀수있음 |