💻 [코테11] 16장 그리디

16장. 그리디

16-1. 그리디 개념

• 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않는 알고리즘
• 지역 최적해 추구(전체에서의 최적해 보장 X)

1) 그리디 알고리즘이 최적해를 보장하려면?

• 아래와 같은 특정 상황에서 최적해 보장
  • 최적 부분 구조 : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
  • 그리디 선택 속성 : 선택 과정이 다른 과정에 영향을 주지 않음
• 한계는 있지만, 빠른 시간 내에 근사해를 제공 가능

16-2. 최소 신장 트리

1) 신장 트리란?

• 모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

2) 최소 신장 트리(Minimum Spanning Tree; MST)란?

• 신장 트리 중 간선의 가중치 합이 최소인 경우
• 최소 신장 트리를 구하는 그리디 알고리즘
  • 프림 알고리즘 : 임의 정점에서 최소 인접 가중치를 가지는 정점을 찾아 확장하는 방식
  • 크루스칼 알고리즘 : 최소 가중치를 가지는 간선부터 하나씩 추가하는 방식

16-3. 배낭 문제(Knapsack Problem; 냅색 문제)

• 짐들을 잘 조합하여 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제

1) 짐을 쪼갤 수 있는 부분 배낭 문제

• 부분 배낭 문제(Fractional Knapsack Problem) 해결 방법 : 무게 당 가치가 높은 짐을 최대한 많이 넣는 그리피 알고리즘 사용

2) 짐을 쪼갤 수 없는 0/1 배낭 문제

• 그리디 알고리즘을 통한 최적해 구하기 불가능
• 동적 계획법으로 접근 필요

16-4. 몸풀기 문제

• 문제80_거스름돈 주기

def solution(amount):
    units = [1, 10, 50, 100]
    units.sort(reverse=True)
    changes = []
    
    for coin in units:
        while amount >= coin:
            changes.append(coin)
            amount -= coin
    return changes

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution(123)) # 반환값 : [100, 10, 10, 1, 1, 1]
print(solution(350)) # 반환값 : [100, 100, 100, 50]

• 문제81_부분 배낭 문제

def solution(items, weight_limit):
    for item in items:
        item.append(item[1] / item[0])
    items = sorted(items, key=lambda x:x[2], reverse=True)
    
    sum_value = 0
    for item in items:
        if weight_limit >= item[0]:
            sum_value += item[1]
            weight_limit -= item[0]
        else:
            if weight_limit == 0:
                break
            value = item[1] * weight_limit / item[0]
            sum_value += value
            break
    return sum_value

# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
print(solution([[10, 19], [7, 10], [6, 10]], 15)) # 반환값 : 27.33
print(solution([[10, 60], [20, 100], [30, 120]], 50)) # 반환값 : 240

16-5. 합격자가 되는 모의 테스트

• 문제82_예산