🌓 Greedy 그리디

@ 6~N차시
@ Chapter 2

💫 Greedy 그리디 (욕심쟁이)

---

최적해, 최고 좋은 해답

부문제
원래의 문제와 똑같은 성질을 가지면서 단지 크기만 작은 문제

• 욕심쟁이 방법의 개요
  • 일련의 단계를 거치면서 (최적)해를 구성한다고 판단되는 요소들을 모음
  • 매 단계마다 전체적으로 최적인지는 판단하지 않고 현재 최적이라고 판단되는 결정을 함. 즉 과거나 미래는 생각하지 않고, 오직 현재의 최대 만족만을 추구(近視眼)
  • 전체를 고려치 않고 현재만을 생각하므로 비교적 간단히 구현
  • 한번 내린 결정은 취소•변경하지 않기 때문에 어떤 다른 최적화 문제 해결기법보다 빠름
  • 최적해를 구하는 데 시간이 오래 걸린다면 욕심쟁이 방법에 기반한 근사 알고리즘을 고려 가능

Greedy
지금 최적해 선택
지금만을 생각하므로 비교적 구현 쉬움
취소/변경 X → 비교적 빠름
오래 걸린다면 근사 알고리듬

• 욕심쟁이 방법을 사용하려면
  • 최적화 문제 ∧최적 부분구조 ∧ 최적 선택
  • 최적화 문제(optimization problem)
    • 가능한 모든 대안 중에서 가장 좋은 해답(최적해)을 고르는 문제
    • 가장 가까운 길을 찾아라, 최소 비용 신장 트리를 구하라, …
  • 최적 부분구조(optimal substructure)
    • 문제(problem)의 최적해가 부문제(subproblem)들의 최적해로부터 효율적으로 생성
    • 부문제는 원래의 문제와 똑같은 성질을 가지면서 단지 크기만 작은 문제
  • 최적 선택
    • 각 단계에서 내리는 선택이 최적이라는 사실을 수학적 귀납법으로 증명
• 조건 (1 && 2 && 3)
  • 최적화 문제 Optimization Problem
    • 최적해 문제 (가장 가까운 길, 최소 비용 신장 트리, …)
  • 최적 부분구조 Optimal Substructure
    • 문제의 최적해, 부문제들의 최적해보루터 효율적으로 생성
  • 최적 선택
    • 각 단계 선택이 최적임을 수학적 귀납법으로 증명

그리디의 구성

1. 선택 작업
   • 현 상태에서 최적해에 포함시킬 대안을 선택
2. 타당성 조사
   • 선택된 해가 주어진 문제의 조건을 만족하는지 검사
3. 해답 조사
   • 원래의 문제가 해결되었는지를 검사

greedy_method( )
{
	solution = { };
	while (condition)
	{
		s = select(); // 1. 선택 작업 - 현 상태에서 최적해에 포함시킬 대안을 선택
		if (feasible(s)) // 2. 타당성 조사 - 선택된 해가 주어진 문제의 조건을 만족하는지 검사
		{ 
			solution = solution ∪ {s};
			if (problem_solved(solution)) // 3. 해답 조사 - 원래의 문제가 해결되었는지를 검사
			{
				return solution; 
			}
		}
	}
}

💫 Optimization Problem - 최적화 문제 예시

---

최단 경로 문제
고속도로에서 자동차를 몰고 운전하는 경우를 생각해보자. 서울에서 강릉까지 가는 최단 경로가 원주와 평창을 차례로 경유해야 한다면 서울에서 평창까지의 최단 경로는 반드시 원주를 경유하여야 한다. 즉 최단 경로 문제는 최적 부분구조를 갖는다.

사이클이 없는 최장 경로 문제
역시 고속도로에서 자동차를 몰고 운전하는 경우를 생각해보자. 이번 여행은 두루두루 여러 도시를 많이 들리면서 최대한 늦게 목적지에 도착하고자 한다. 서울에서 강릉까지 가는 최장 경로가 대전, 광주, 부산, 대구, 원주를 차례로 경유해야 한다면 부산에서 원주로 가는 최장 경로는 반드시 대구를 포함하는가? 아닐 수 있다. 즉 최장 경로 문제는 최적 부분구조를 갖지 않는다.

동전 거스름돈 문제
가능한 적은 수의 동전을 받기
큰 액면 동전부터(욕심을 부린다!) 차례로 선택하여 남은 거스름돈 액수보다 작을 경우 해답에 포함시켜 나가면 된다

int coin_change_making_GM(int change) {
int solution = 0, coin = 500;
while (true) {
if (change >= coin) {
solution++;
change = change - coin;
if (change == 0) return solution;
}
else coin = select_next(coin);
}
}

항상 최적해를 구할 수 있는가? : NO 130원짜리 동전이 있다고 가정하고 거스름돈이 150원인 경우 [알고리즘 2.2]는 3개{130원, 10원, 10원}라는 답을 내놓지만 최적해는 2개{100원, 50원} 최적 부분구조를 갖는가? : YES But, 부문제의 최적해를 모두 알아보고 그 중에 최적해를 찾아야 하는데 욕심쟁이 방법에서는 일단 동전을 거슬러주고 나서 부문제를 해결하려다 보니 최적해를 얻을 수 없게 됨

항상 최적해를 구할 수 있는가? X
150; 130, 10, 10 < 100, 50

최적 부분구조를 갖는가?

최소신장트리

💫 최소 신장 트리

---

• 신장 트리
  • 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리
  • 정점의 수가 n 개이면 신장 트리의 간선 수는 n-1 개
  • 계층 구조가 없는 그래프(사이클없이 연결되어 있다는 트리 특성을 가짐)
  • 활용 예) 각 정점이 도시를 나타내고 간선이 도로를 나타낸다면 신장 트리는 모든 도시들을 연결하는 최소한의 도로망
• 최소 신장 트리(MST: minimum spanning tree)
  • 최소 비용 신장 트리(MCST: minimum cost spanning tree)
  • 간선들의 가중치 합이 최소가 되는 신장 트리
  • 활용 예
    • “최소한의 비용으로 모든 도시를 연결하는 도로망을 건설하라”
    • “도로의 길이를 최소로 하면서 모든 도시를 연결하는 도로망을 건설하라”
    • 도로망, 통신망, 유통망, 배관 등 네트워크 상에서 비용, 거리, 시간 등의 가중치를 갖는 그래프를 이용하여 최소 신장 트리 구하기
  • 문제: 방 향성이 없는 연결된 가중치 그래프가 주어졌을 때, 간선들의 가중치 합이 최소가 되는 신장 트리 구하기
• 무작위 기법
  • 가능한 신장 트리를 모두 구한 다음, 최소 비용의 신장 트리를 선택
  • 모든 정점 간에 간선이 있는 완전 그래프의 경우 신장 트리의 수는 n^(n-2)
    • 정점이 10 개: 1억 개의 신장 트리
    • 정점이 19 개: 약 5.4 ×10^21 개의 신장 트리
  • 욕심쟁이 방법
    • 프림(Prim)의 알고리즘
    • 크러스컬(Kruskal)의 알고리즘

💫 크러스컬 알고리듬

---

@ U 중간고사 출제 : 크러스컬 알고리듬 과정 (최소신장트리, 가중치가 중복되는게 없다면 어떤 알고리듬써도 간선 모양 같음 = 프림 알고리듬 결과와 똑같음)

최소 신장 트리을 구하는, 그리드 알고리듬의 일종

1. 선택 작업, 각 단계에서 가중치가 최소인 간선을 선택
   • 방법 1. 최소값 찾기 알고리듬을 여러 번 실행 (x)
   • 방법 2. 미리 모든 간선을 가중치에 따라 정렬
     • i.e. a-b 1, a-d 2, b-d 2, b-c 3, c-d 4
2. 타당성 조사, 선택한 간선 때문에 사이클이 만들어진다면 선택한 간선을 버림
   • 방법 1. 깊이 우선 탐색 DFS을 이용 (x)
   • 방법 2. 배타적/서로소 집합 (Disjoint Set)의 개념을 이용하는 Union-Find 연산

받아들여진 간선의 수가 n-1개가 되면 종료
→ n개의 트리로 구성된 프로스트에서 출발하여 최종 1개의 트리를 생성

Union-find
Disjoint Set 서로소 집합을 표현하는 자료구조

Union
서로 다른 두 집합을 병합

Find
집합 원소가 어떤 집합에 속해있는지

어떤 정렬 알고리듬을 쓰냐가 시간에 영향을

@ TODO : 또 졸았다. 다시 공부.

edge_set kruskal_MST(edge_set E, int n)
{
	sort(E); // A
	edge_set MST_E = { };
	for (i=0; i＜n; i++) init_set(i); // B, n개의 집합(트리)을 생성
	while (MST_E의 간선 수 ＜ n-1)
	{ 
		(u, v) = E의 최소 가중치 간선;
		E = E - {(u, v)} ;
		if (find(u) ≠ find(v))  // u와 v가 다른 집합(트리) 원소
		{
			MST_E = MST_E ∪ {(u, v)} ;
			union(u, v);	// 두 집합(트리)을 합병
		}
	}
	return MST_E;
}

• 연산
  • 최초에 정점 하나를 원소로 하는 집합을 만드는 init_set 연산
  • 임의의 정점이 어느 집합의 원소인지를 알아내는 find 연산
  • 두 집합을 하나로 합치는 union 연산
• 시간 복잡도(상환 분석)
  • 트리로 구현된 집합에서 원소수기반 union 연산과 경로붕괴 find 연산 사용
  • 세 연산을 합하여 전부 m번 실행하고 init_set을 n번 실행하면 O(m log*n)
  • n이 매우 크더라도 logn 은 아주 작은 상수 값이기 때문에 O(m logn)≒O(m). 즉 세 연산을 전부 m 번을 실행할 경우 O(m)이므로 연산 하나하나 당 상수시간 걸림
• 복잡도(정점의 수가 n 이고 간선의 수가 e )
  • A에서 퀵정렬, 합병정렬, 히프정렬 등 가장 성능이 우수한 기법을 사용하면 O(e loge)
  • while 문은 최대 e 회 반복
    • 한번 반복할 때마다 2번의 find 연산과 최대 1번의 union 연산 실행하므로 while 문을 통틀어 최대 2e번의 find 연산과 최대 e번의 union 연산을 실행
    • B의 init_set 연산은 n번 실행
    • 위 세 연산을 합하여 전부 n+3e번을 실행하고 init_set의 실행 횟수가 n이므로 상환분석에 따라 시간 복잡도는 O(n+3e)=O(n+e)
    • 연결 그래프에서는 n-1 ≤ e이므로 O(n+e) =O(e)
  • 결국 A의 정렬이 전체 알고리즘의 복잡도를 좌우: O(eloge)
  • e는 최대 O(n2)이므로 O(eloge)=O(elogn^2)=O(2elogn)=O(elogn)

💫 프림 알고리듬

---

@ U 중간고사 출제 : 프림 알고리듬 과정 (최소신장트리, 가중치가 중복되는게 없다면 어떤 알고리듬써도 간선 모양 같음 = 크러스컬 알고리듬 결과와 똑같음)

최소 신장 트리을 구하는, 그리드 알고리듬의 일종

• 아무 정점에서 시작 트리 초기화
• 매 단계 + (1 간선, 1 정점) 하며 트리 유지
• MST가 아닌 모든 정점과 간선에 대해, 가중치가 낮은 간선부터 선택
• 모든 정점 선택 (= n-1개 간선 선택) 시 종료

타당성 (사이클 존재 여부) 조사 X
MST 아닌 (선태되지 않은) 정점만 선택하기 때문

행렬 or 인접/연결 리스트, 배열 or 우선 순위 큐 or 최소 힙

• 알고리즘 개요
  • 크러스컬 알고리즘처럼 가중치가 낮은 간선부터 선택
  • 크러스컬의 알고리즘은 포리스트에서 출발하여 하나의 트리를 생성하는 반면 프림의 알고리즘은 처음부터 끝까지 트리를 유지
  • 아무 정점 하나를 선택하여 시작 트리로 초기화하고 매 단계에서 간선 하나와 정점 하나를 붙여나가면서 트리를 유지
  • 모든 정점을 선택하면(n-1개의 간선을 선택하면) 종료
• 타당성 조사(사이클이 존재하는지 검사)가 없음
  • 간선 (X, V)를 선택하는 순간, 정점 X, Y, V 를 포함 하는 사이클이 생성된다고 가정하자. 그렇다면 정점 V는 이미 MST에 포함되어 있어야 하며 간선 (X, V)를 절대로 선택할 수 없다. 따라서 사이클을 생성하지 않는다.

// 단순화한 프림의 MST(욕심쟁이 방법)
edge_set prim_MST_1(edge_set E, vertex s)
{
	edge_set MST_E = { }; 
	vertex_set MST_V = {s}; 
	loop (n-1)
	{ // n-1번 반복
		(u, v) = E의 최소 가중치 간선, 단 u ∈ MST_V, v ∉ MST_V; MST_E = MST_E ∪ (u, v) ; // A
		MST_V = MST_V ∪ v ;
	}
	return MST_E;
}

• 최소 가중치 간선을 선택하는 방법(A)
  • 정점 별로 최소 가중치를 관리(간선의 가중치 정보를 정점에 부여하고 각 단계에서 정점을 선택)
  • MST에 아직 포함되지 않은 각 정점 v에 대해 distance(v)와 nearest(v) 값을 지정
    • distance(v): 이미 MST에 속한 정점과 v사이의 간선 가중치 중 최소값
    • nearest(v): 그 때의 MST에 속한 정점
  • 정점 u가 선택될 때마다 u에 인접했으나 아직 MST에 포함되지 않은 모든 정점 w에 대해 재계산

distance(w) = minimum {distance(w), weight(u, w)} 단, weight(u, w) = 간선 (u,w)의 가중치 nearest(w) = u if distance(w)가 변경

//프림의 MST(욕심쟁이 방법)
// 복잡도:  Θ(n2) , select_min 비용 인접 행렬을 기반
void prim_MST_2(int graph[ ][MAX], int n, int s)
{
	bool MST_V[MAX] ;
	int distance[MAX], nearest[MAX], i, u, w;
	for (i = 0; i ＜ n; i++) 
	{ // 초기화
		MST_V[i] = false; 
        distance[i] = graph[s][i]; nearest[i] = s;
	}
	MST_V[s] = true;
	loop (n-2)
	{ // n-2번 반복
		u = select_min(distance, n, MST_V); MST_V[u] = true;
		for (w = 0; w ＜ n; w++)
			if (MST_V[w] == false)
				if (graph[u][w] ＜ distance[w])
				{
					distance[w] = graph[u][w];
					nearest[w] = u;
				}
	}
}

int select_min(int distance[ ], int n, bool MST_V[ ])
{
	int i, min = ∞, min_index = 0;
	for (i = 0; i ＜ n; i++)
	if (distance[i] ＜ min && MST_V[i]==false)
		min = distance[i]; min_index = i;
	return min_index;
}

그래프: 인접 행렬에 저장 distance: 1차원 배열 (즉, select_min 연산: 배열 순차탐색) Θ(n2)

디코 사진
그래프: 인접 리스트에 저장 distance: 최소 히프 (즉, select_min 연산: 최소히프의 삭제연산)  delete_min_heap 연산과  decrease_key 연산의 실행 시간이 전체 실행 시간을 좌우  (줄10) loop는 n-2회 반복. (줄11)의 delete_min_heap 함수는 O(logn)이므로 delete_min_heap 함수의 총 실행 시간은 O(nlogn)  loop과 for은 묶어서 분석. for은 “u에 인접한 모든 정점에 대해”라는 의미로 u와 인접한 간선 수만큼 반복. 따라서, for의 총 반복 회수는 O(e). (줄16)의 decrease_key 함수는 O(logn). 따라서 decrease_key 함수의 총 실행 시간은 O(elogn) +=O((n+e)logn), 연결 그래프에서는 n-1≤e이므로 O((n+e)logn)=O(elogn)

// 인접리스트와 이진 히프를 사용한 프림의 MST (욕심쟁이 방법)
// 디코 사진

💫 최소 신장 트리 비교

---

• 두 방법 모두 가중치가 낮은 간선을 우선시하는 전략을 사용, but
  • 크러스컬 알고리즘: 포리스트에서 트리로 변환
  • 프림 알고리즘: 트리의 모습을 끝까지 유지
• 복잡도
  • 크러스컬 알고리즘
    • 그래프를 저장하는 방식과는 관계없는 복잡도
    • 간선들을 정렬할 때 사용하는 정렬 알고리즘의 성능에 민감하게 반응
  • 프림 알고리즘: 그래프의 저장 방식과 최소값을 찾는 방법에 따라 복잡도가 달라짐

디코 사진 표

💫 다익스트라 알고리듬

---

단일 시작점 최단 경로
다익스트라 알고리듬

@ U 중간고사 출제 : 다익스트라 알고리듬 실행과정 (어떤 정점을 선택하는지 distance/)

허프만 코딩
무손실 압축에 쓰이는 엔트로피 부호화 방법

@ U 중간고사 출제 : 주어진 코드를 허프만 코딩을 통해 압축하시오.

TSP

NP-Complete 완전 문제
~ 아무튼 오래 걸리는 문제
→ 특별한 값 제외하고 처리
→ 최적해와 근사한 값

@ Theory of Computation 계산 이론에서 주로 하는 이야기

70~80년 전
수학 문제를 어떻게 해결할 것인가?

정형화된 문제
풀 수 있는 문제와 없는 문제

@ TM : Turing Machine

Tracktable
Intracktable 아무리 빨리 풀어도

Polynomial Time 다항식 시간 :
O(n^k) (상수, 로그, 지수 함수를 포함)
n^3 정도만 되어도 복잡하긴한데, 이론적으로는

P Class : 풀기 쉬운 문제, 다항식 시간 내에 풀 수 있는 문제
Polynomial Time Class
결정적 TM 을 이용해 다항식 시간 내에 풀 수 있는 문제

NP Class :
NonPolynomial Time Class
비결정적 TM 을 이용해 다항식 시간 내에 풀 수 있는 문제
병렬처리 할 수 있는 문제, 컴퓨터 마다 다른 처리할 수 있게 하는 문제
다항식 시간 내에 해답을 검증할 수 있는 문제 (누군가 낸 해답을 맞는 지 없는 지 검증할 수 있는)

P 이면 NP 일것이라고 강한 추측
~ 시간 내에 풀 수 있으면, ~ 시간 냉 검증할 수 있을 것이라는
P 가 NP 의 부분집합
@ 아닌 사례를 아직 발견한 적 없지만, 수학적으로 증명되지는 않은

NP 중에 P 가 아닌 애들 중, NP-Complete 라는 문제가 있음
NP-Complete 문제들 중 어느 하나라도 P 로 풀리는 문제가 있다면,
그 문제는 전부 P 로 풀리는 문제인 집단

A 문제 → B 문제 → C 문제 … Reduce
~ 시간 내에 축약(= 치환) 될 수 있음

C 문제가 P 로 풀린다면, A, B 문제도 P로 풀림
~ 시간 * 상수 = ~ 시간 내에 축약(= 치환) 되기에

TSP
Traveling Salesman Problem
여행하는 외판원(세일즈맨) 문제

모든 도시 한 번씩 방문하고 돌아오는 최단 경로

TSP 조건

1. 대칭성 : 두 도시 사이 간 거리 양방향으로 동일 → 방향성이 없는 가중치 그래프
2. Triangle Inequality 삼각 부등식 만족 : 삼각형으로 위치한 세 도시를 잇는 도로 가운데 두 도로의 길이의 합은 다른 한 도로의 길이보다 같거나 길다는 것
3. 완전 그래프 : 모든 도시들 간에 반드시 도로가 존재

Brute Force => O(n!) 중 가장 작은
동적 계획법 => O(n^2 * 2^n)

근사 알고리듬
Nearest Neighbor Algorithm 최근접 이웃 알고리듬
안 간 곳 중에 가장 가까운 곳 부터

구현 쉬움, 나름 짧은 경로를 짧은 시간에
완전 그래프가 아니라면 경로가 존재해도 못 찾는 경우가

근사 알고리듬
MST 이용 알고리듬

기본 아이디어
MST는 연결되어 있음, 상대적으로 낮은 가중치를 갖는 간선들로 구성
→ TSP의 최적해에 가까울 수도
But, MST는 선형 구조가 아니므로, 차례로 방문 못하는 경우가
→ SO, MST로부터 선형순서를 만듦 (DFS, 삼각 부등식 이용)
→ → 1213 방문이라면, 정점 2 1 3 은 삼각 부등식을 만족하므로 돌아갈 필요 없이 정점 2에서 3으로 바로 방문

방법
MST 구하고
S 출발점으로 부터 DFS 실행
방문 순서에서 두 번 이상 중복 방문되는 정점 제거 (마지막 방문 출발점 제외)

근사해 <= ~ < MST 가중치 < 최적해
MST 가중치 + 1 간선 = Cycle (최적해)