[Algorithm] 그리디

* Python을 기준으로 합니다

---

그리디 (Greedy)

- 개념

• 그리디 전략 : 각 단계에서 최적의 결과만을 선택하여 문제를 해결하는 방식
  • 이전 선택이 이후 선택에 영향을 주지 않으면서, 부분 문제에 대한 해가 전체 문제의 최적 해로 구성되는 Greedy Choice Property를 가지는 최적 부분 구조 문제에 적용 가능
    
  • 그리디 적용 가능 예시 : 다익스트라, 분할 가능 배낭 문제, 거스름돈 나누기, 회의실 배정 문제, 신장 트리 (프림, 크루스칼 알고리즘)
  • 그리디를 적용할 수 없는 경우 : 0-1 배낭 문제, 외판원 순회, 이진 트리의 최적 합 경로

- 구현

1. 분할 가능 배낭 문제

• 무게 $w$와 가치 $v$인 $n$개의 물건들을 배낭에 넣을 때, 물건들의 가치의 합이 최대가 되도록 배낭을 채우는 경우 (이때 물건들을 나누어서 일부만 넣을 수도 있음)
  • Greed Property : 단위 무게당 가치가 가장 높은 물건부터 넣기
  • 0-1 배낭 문제와 달리 분할 가능 배낭 문제는 배낭을 항상 최대 용량으로 채울 수 있음
  • 분할 가능 배낭 문제의 동작
    1. 각각의 물건들에 대한 단위 무게당 가치를 구함
    2. 무게당 가치가 가장 높은 물건부터 최대한으로 배낭에 넣음
       - 물건 무게가 배낭 용량보다 크면 물건을 나누어 넣음
    3. 위 과정을 배낭 용량이 가득 찰 때까지 반복

def knapsack(item, weight_limit):
  total = 0
  limit = weight_limit

  #단위 무게당 가치 계산
  unit_val = []
  for weight, val in item:
    unit_val.append([weight, val, val/weight])
  
  #무게당 가치가 높은 순으로 정렬
  unit_val.sort(key=lambda x:x[2], reverse=True)

  #가치가 높은 것부터 넣음
  for weight, val, _ in unit_val:
    if weight <= limit: #배낭 무게보다 물건 무게가 작으면
      total += val #그대로 넣음
      limit -= weight
    else: #배낭 무게보다 물건이 크면
      divide = limit/weight #나눔
      total += val*divide
      break
  return total

#------
item = [[10,19],[7,10],[6,10]]
weight = 15

print(knapsack(item, weight)) #27.333333333333336

2. 예시 문제 1

• 프로그래머스 - 큰 수 만들기 
  
  • Greedy Property : 현재 수 중에서 가장 작은 수만을 제거하기
  • 스택을 활용하여 각 수들을 비교하고, 가장 큰 수만을 저장함

큰 수 만들기 문제

def solution(number, k):
    stack = []

    for num in number: #주어진 각 숫자들에 대해
        #k번 제거하는 동안, 스택에 저장된 현재 수보다 더 높은 수가 있으면
        while k > 0 and stack and stack[-1] < num:
              stack.pop() #현재 수를 제거하고
              k-=1
    
        stack.append(num) #더 큰 수를 추가

    if k > 0: #스택이 남아있으면
        stack = stack[:-k]

    answer = ''.join(stack)
    return answer

3. 예시 문제 2

• 프로그래머스 - 구명보트 
  • Greedy Property : 가장 무거운 사람부터 구출하기
  • 이때 남아있는 사람들 중에서 가장 가벼운 사람을 같이 구출할 수 있는지 확인하기 위해 투 포인터를 활용해 탐색

구명 보트 문제

def solution(people, limit):
    answer = 0

    people.sort() #무게 순으로 정렬
    i = 0 #가장 가벼운 사람
    j = len(people)-1 #가장 무거운 사람
	
    #투 포인터
    while i<=j: #전부 구출할 때까지
      if people[i]+people[j]<=limit: #가장 무거운 사람과 가벼운 사람을 태웠을때 limit 이하면
        i+=1 #가장 가벼운 사람도 같이 구출
      
      j-=1 #기본적으로 무거운 사람 부터 구함
      answer += 1 #구출 횟수 증가
    return answer