그리디 알고리즘

: 매 선택에서 그 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘

• 실제 최적해는 107
• 그리디 알고리즘은 처음에 7과 13중에 13을 선택하므로, 최종 결과값으로 13+11=24를 도출

1) Greedy 알고리즘이 잘 동작하는 경우

1) Greedy choice property (탐욕 선택 속성)
: 앞의 선택이 다음 선택에 영향을 주지 않는 경우

2) Optimal substructure (최적 부분 구조)
:매 순간의 최적해가 전체 문제에 대한 최적해인 경우

• ex) 아래 그림과 같은 길 start에서 goal까지 가는 최단 거리를 구할때
  

3) 알고리즘 문제 풀때!
문제에 제약조건이 많다면 그리디로 풀리는 경우가 많다고 한다

2) 대표적 문제

(1) 거스름돈 문제

손님에게 n원을 거슬러 주려고 할 때, 동전 개수를 최소로 하는 방법은?

• 가장 큰 화폐단위부터 거슬러주는 방법 선택

coin = [500, 100, 50, 10]
n = 1260  #거슬러줘야 할 돈
cnt = 0  #동전 개수
for i in coin:
    cnt += n // i  #큰 화폐단위부터 거슬러준다
    n %= i
print(cnt)

• 만약 큰 화폐단위가 작은 화폐단위의 배수가 아닐 경우 최적해를 보장해주지 못한다.

(2) 1이 될 때까지

숫자 n에 대하여 ( -1 ) 또는 ( /k)를 적용하여 가장 빨리 1로 만들 수 있는 횟수 구하기

• 우선 최대한 나누기를 많이 하는 방법 선택

result = 0
while True:
    target = (n//k) * k  # target: n 이하의 k로 나누어지는 가장 큰 수
    result += (n - target) # target을 n에서 빼면 -1 하는 횟수
    n = target  

    if n < k:
        break

    result += 1 # K로 나누는 횟수 추가
    n //= k

result += (n-1) # 반복문 후에도 n이 1보다 크다면 n-1번만큼 더 -1 해야함
print(result)

(3) 배낭 채우기

도둑이 물건의 '무게'와 '가치'를 알고 있을 때, 배낭 용량 내에서 최대한의 값어치를 담는 방법 구하기

• 물건을 쪼개서 넣을 수 있다면(Fractional Knapsack) 그리디로 해결 가능(무게당 가치가 높은 순으로 넣으면 됨)
• 그럴 수 없을때(0-1 Knapsack) : Dynamic Programming 이용해야 함

# W : 배낭 총 용량
# n : 물건의 개수
# wieght : 물건 무게의 집합 (오름차순)
# value : 물건 가치의 집합 (오름차순)

def solution(W, n):
    if W == 0 or n == 0:
        return 0

    if weight[n-1] > W: 
        return solution(W, n-1)
    else:
        return max( value[n-1] + solution(W-wieght[n-1], n-1),  solution(W, n-1) )