Greedy

"탐욕스러운, 욕심 많은", 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

Greedy 문제 해결 단계

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복.

예시

동전 거스름돈을 위 단계를 바탕해서 예시를 담아보자

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

960원을 거슬러 주는데 일상적으로 생각하면

1. 먼저 큰 단위인 500원을 골라 한개 고르고 500원보다 작은 단위 남았으니 끝
2. 그다음 100원을 460원에 4개로 채우고 끝
3. 10원 6개로 채우고 끝

이걸 그리디로 생각하면

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복.

결론: 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.

단점

즉, 그리디는 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.

그런데 마시멜로 실험같이 좀 더 미래를 본다거나, 아니면 다양한 조합? 이 필요할 땐 그리디는 최적의 해를 도출하지 못한다.

마시멜로 실험이란?
지금 마시멜로를 받겠다고 말하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 "현재"에 최선인 선택을 하기 때문에 마시멜로를 당장 받아내어 1개를 받게 되지만,
전체적으로 보게 되면 1분 뒤에 받는 2개가 최적의 선택이 된다.

따라서, 적어도 두 가지의 조건을 만족하는 "특정한 상황" 에서 써야한다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용 가능!

예제

minPaperCount

문제

사용 가능한 종이 길이 중 최소 개수로 필요한 길이를 만드는 함수 minPaperCount(targetLength, paperLengths)를 작성하세요. targetLength는 목표 길이이고, paperLengths는 사용 가능한 종이 길이가 담긴 배열입니다. paperLengths의 각 요소는 1 이상 10^4 이하의 자연수입니다. targetLength는 1 이상 10^6 이하의 자연수입니다.

예를 들어, targetLength = 18, paperLengths = [10, 7, 5]이면, 최소 개수의 종이로 18을 만들기 위해서는 길이 10의 종이 1개, 길이 5의 종이 1개 총 2개가 필요합니다.

function minPaperCount(targetLength, paperLengths) {
  let count = 0;
  paperLengths.sort((a, b) => b - a); // 종이 길이를 내림차순으로 정렬

  for (let i = 0; i < paperLengths.length; i++) {
    while (targetLength >= paperLengths[i]) {
      targetLength -= paperLengths[i];
      count++;
    }
  }

  return count;
}

이 함수는 사용 가능한 종이 길이 중 최소 개수로 targetLength를 만듭니다. 이 함수는 그리디 알고리즘을 사용하여 문제를 해결합니다. 우선, paperLengths 배열을 내림차순으로 정렬합니다.
그런 다음, paperLengths 배열에서 큰 종이부터 시작하여, targetLength가 해당 종이의 길이보다 큰 경우, 해당 종이를 사용하여 targetLength에서 종이의 길이를 뺍니다. 이렇게 종이의 길이를 뺄 수 없을 때까지 반복하면서, 사용한 종이의 개수를 카운트합니다.
마지막으로, 사용한 종이의 개수를 반환합니다. 이 알고리즘은 항상 최적의 결과를 반환하는 것은 아니지만, 이 문제에서는 그리디 알고리즘이 최적해를 구할 수 있습니다.