그리디 알고리즘(greedy algorithm)

그리디 알고리즘 : 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

BUT
이런 방법은 항상 최적의 결과를 보장하지는 않는다.

THUS
다음 두 조건을 만족하는 '특정한 상황'이 아니라면 최적의 해를 보장하지 못한다.

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

그리디 알고리즘으로 문제를 해결하는 방법

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

예시 문제

짐 나르기

김코딩과 박해커는 사무실 이사를 위해 짐을 미리 싸 둔 뒤, 짐을 넣을 박스를 사왔다. 박스를 사오고 보니 각 이사짐의 무게는 들쭉날쭉한 반면, 박스는 너무 작아서 한번에 최대 2개의 짐 밖에 넣을 수 없었고 무게 제한도 있었다.

예를 들어, 짐의 무게가 [70kg, 50kg, 80kg, 50kg]이고 박스의 무게 제한이 100kg이라면 2번째 짐과 4번째 짐은 같이 넣을 수 있지만 1번째 짐과 3번째 짐의 무게의 합은 150kg이므로 박스의 무게 제한을 초과하여 같이 넣을 수 없다.

박스를 최대한 적게 사용하여 모든 짐을 옮기려고 합니다.

짐의 무게를 담은 배열 stuff와 박스의 무게 제한 limit가 매개변수로 주어질 때, 모든 짐을 옮기기 위해 필요한 박스 개수의 최소값을 return 하도록 movingStuff 함수를 작성하세요.

수도코드

  //stuff = [70, 50, 80, 50]
  //최대 2개의 짐 밖에 넣을 수 없으므로 무거운것, 가벼운것 짝지어서 박스에 넣는 것을 시도하기 위해... 정렬을 한다
  //sortedStuff = [80, 70, 50, 50]
  //limit = 100
  //80 -->shift --> count!
  //[70, 50, 50]
  //70 -->shift --> count!
  //[50, 50]
  // 50+50 = 100
  // shift, pop --> count!
  // []
  //반복의 조건: sortedStuff.length !==0

function movingStuff(stuff, limit) {

let count = 0; 
let sortedStuff = stuff.sort((a, b) => a - b) 

while (sortedStuff.length !==0) { 
if (sortedStuff[0] + sortedStuff[sortedStuff.length-1] <= limit) { 
    count++ 
    sortedStuff.shift();
    sortedStuff.pop();
  } else {
    count++
    sortedStuff.pop();  
  }
}
return count; 
}

연습문제 : https://www.acmicpc.net/problem/5585
공통문제 :
https://www.acmicpc.net/problem/2839
or
https://www.acmicpc.net/problem/2212