내가 공부하기 위한 공간 - [알고리즘] 6 - 그리디(동전, 분할가능배낭, 최소신장트리)

[그리디 알고리즘]

정의 : 그 당시 가능한 해들 중에서 가장 좋은 해를 찾는 문제를 해결하는 알고리즘

특징 : 제한적, 단순, 번복성 X

 

 

[거스름돈]

가장 큰 액수부터 찾아 넣음

> 최소 동전수는 아님

> 동적 계획 알고리즘 사용

 

 

[분할가능배낭]

무게와 가치가 다른 n개의 물건에서 한개의 배낭에 최대한 많은 가치를 담음(물건 분할 가능)

1. 각 물건에 대한 가치들을 구함
2. 큰 가치를 가진 물건부터 담음
3. 배낭의 여유분을 초과하면 초과하지 않는 내에서 분할하여 담음

물건=가격/무게=가치

A=240/30=8

B=100/10=10

C=140/20=7

D=160/40=4

배낭이 담을 수 있는 무게 : 50

B부터 담음

남은 무게 : 40, 가격 : 100

A담음

남은 무게 : 10, 가격 : 340

C를 10만큼만 담음

남은 무게 : 0, 가격 : 410

FractionalKnapsack( C, n개의 물건 배열)
{
	각 물건의 단위 가격을 계산한다.
	단위 가격을 기준으로 내림차순으로 정렬하고, 이를 S라고 하자.
	L=∅, w=0, v=0 // w는 배낭에 담긴 물건들의 총 무게
	x = S에서 단위 가격이 가장 큰 물건
	while ( (w+x의 무게) ≤ C ) {
		x를 L에 추가시킨다.
		w = w + x의 무게
		v = v + x의 가격
		S에서 x를 제거한다.
		x = S에서 단위 가격이 가장 큰 물건
	}
	if ((C-w) > 0) { 물건 x를 (C-w) 만큼 L에 추가한다.
		v = v + (C-w) 만큼의 x의 가치
		// 배낭에 여유가 있을 경우
	}
	return L, v //배낭에 담은 물건 리스트 L과 가치 합 v
}

시간복잡도

가치 계산 : O(n)

정렬 : O(nlogn)

최대 담는 시간 복잡도 : O(n)

반복 없는 것 : O(1)

> O(nlogn)

 

 

[최소신장트리]

그래프에서 모든 노드들을 포함하면서 트리가 되는 것들 중 가중치의 합이 최소인 트리

 

Kruskal

1. 에지를 중심으로 만듦
2. 가중치가 작은 에지부터 연결, 사이클이 만들어지면 제외
3. 모든 노드가 연결되면 탐색 종료

1. D-17-Z
2. D-17-Z-18-E
3. 20은 사이클이 만들어짐 > 제외
4. A-30-B, D-17-Z-18-E
5. C-35-A-30-B, D-17-Z-18-E
6. C-35-A-30-B-40-D-17-Z-18-E
7. 모든 노드가 있으므로 탐색 종료

KruskalMST(G) // 그래프 G=(V,E), |V|=n , |E|=m
{
	L = 가중치 오름차순으로 정렬된 에지 리스트
	T=∅
	while ( T의 에지 수 < n-1 ) {
		e = L에서 최소 가중치 에지
		L에서 e를 제거한다.
		if ( T에 e를 추가할 때 사이클을 만들지 않으면) e를 T에 추가한다.
        else e를 버린다.
	}
	return T // T는 최소 신장트리
}

시간복잡도

에지 정렬 : O(mlogm)

최대 에지 탐색 : O(m)

사이클 검사 : O(log*m)

반복 없는 것 : O(1)

> O(mlogm)

 

Prim

1. 노드를 중심으로 만듦
2. 노드를 하나 선정
3. 선정 노드에서 연결 가능한 최소 에지를 선택 후 연결
4. 모든 노드가 연결되면 탐색 종료

1. B를 선택
2. 가능한 선 중 30이 최소, A-30-B
3. 35가 최소, C-35-A-30-B
4. 40이 최소,  C-35-A-30-B-40-D
5. 17이 최소, C-35-A-30-B-40-D-17-Z
6. 18이 최소, C-35-A-30-B-40-D-17-Z-18-E
7. 모든 노드가 있으므로 탐색 종료

PrimMST( G, s) // 그래프 G=(V,E), |V|=n , |E|=m, s : 시작 정점
{
	T = {s}
	while ( T에 있는 정점의 수 < n ) {
		(u,v) 는 u∈T and v∉ T 인 최소 비용 에지
		if ( (u,v) 가 존재하면 ) v를 T에 추가한다.
		else 실패
	}
	return T // T는 최소 신장트리
}

시간복잡도

최소 에지 선택 : O(n)

반복 횟수 : (n-1)

> O(n^2)