[그리디 알고리즘]

그리디 알고리즘 글로벌 최적을 찾기 위해 각 단계에서 로컬 최적의 선택을 하는 휴리스틱 문제 해결 알고리즘이다.

그리디 알고리즘이 잘 작동하는 문제들의 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조 문제의 최적 해결방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다.

정답 근사하게 찾는 용도로도 쓰일수 있고, 계산속도가 매우 빠른 특징을 가진다.

[그리디 vs 다이나믹 프로그래밍]

그리디 알고리즘은 최적 부분 구조 문제를 푼다는 점에는 흔히 다이나믹 프로그래밍과 비교되는데, 서로 풀 수 있는 문제의 성격이 다르며 알고리즘의 접근 방식 또한 다르다. 다이나믹 프로그래밍이 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다면, 이에 반해 그리디 알고리즘은 각 단계마다 로컬 최적해를 문제로 접근해 문제를 더 작게 줄여나가는 형태로, 서로 반대 방향으로 접근하는 구조를 띈다.

[배낭 문제 Fractional Knapsack Problem - 그리디로 접근]

# cargo는 가격 + 무게로 이루어진다. 
def fractional_knapsack(cargo):
	capacity = 15
	pack = []
	# 단가 계산 역순 정렬
	for c in cargo:
		pack.append((c[0]/c[1], c[0], c[1]))
	pack.sort(reverse=True)
	
# 단가 순 그리디 계산
total_value = 0
for p in pack:
	if capacity - p[2] >= 0:
		capacity -= p[2]
		total_value += p[1]
	else:
		fraction = capacity/p[2]
		total_value += p[1] * fraction
		break
return total_value

[동전 바꾸기 문제]

동전의 액면이 10원, 50원, 100원 처럼 증가하면서 이전 액면의 배수 이상이 디면 그리디 알고리즘으로 풀수 있다.

예를들어 160원을 거슬러 준다면 10원 짜리 16개 보다는, 100원짜리 하나, 50원 짜리 하나, 10원짜리 하나로, 각각의 동전을 최대한 활용하는 그리디한 방법이 가장 작은 동전 개수로 거슬러 줄 수 있는 방법이다.

근데 만약 80원짜리 동전이 존재하면 80원 두개가 정답이고, 그리디는 100부터 선택하기 때문에 더이상 그리디로 풀수 없고, 이 때는 다이나믹 프로그래밍으로 풀어야 한다.

[가장 큰 합]

이미 선택을 하는 순간 다른 경로를 버리기 때문에 그리디의 실패 예시이다.

1)주식을 사고팔기 가장 좋은 시점II-하, 그리디