티스토리 뷰

알고리즘

Greedy 그리디 알고리즘

이채야채 2021. 12. 14. 19:59

그리디 알고리즘?

 

당장 눈앞에 보여지는 최적의 상황만을 쫓는 알고리즘

대표적인 예제 : 거스름돈 문제 => 무조건 더 큰 화폐 단위 부터 거슬러준다. : 최적의 해 보장!

 

그리디 알고리즘 : 무조건 큰 경우대로, 무조건 작은대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 <= 극단적으로 문제에 접근

 

특징 : 정렬기법 sort를 함께 사용한다.

 

단순하게 큰 경우 부터 찾는 알고리즘과 같이 탐욕적으로 문제를 해결하는것. 그리디 알고리즘

 


1.

현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다. 동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

 

입출력 예시

// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개, 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

 

풀이 방법

function partTimeJob(k) {
  // TODO: 여기에 코드를 작성하세요.
  let result = 0; 
  let wallet = [500,100,50,10,5,1]

  for(let i=0; i<wallet.length; i++){
    if(k>0){
      let count = parseInt(k/wallet[i])
      result = result + count
      k = k-(wallet[i]*count)
    }
  }
  return result
}

1. sort가 된값을 배열에 담는다.

2. k = k-(wallet[i]*count) <= 다시 K에 담아서 K의 값을 변화시켜준다.

 

어려운 문제는 아니였으나, 단순한 하드 코딩으로 작업했었다. 

생각을 좀더 깊게 해야겠다. 

 

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

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

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

 

입출력 예시

let output = movingStuff([70, 50, 80, 50], 100);
console.log(output); // 3

let output = movingStuff([60, 80, 120, 90, 130], 140);
console.log(output); // 4

 

가장 큰 경우를 생각해서 접근하자. 2가지를 선택할때 가장 큰 경우하나를 잡아서 생각.

1. 큰 경우 80, 작은경우 50을 잡는다.  해결된다면 그 인덱스들을 제외시켜야한다.

function movingStuff(stuff, limit) {
  // TODO: 여기에 코드를 작성합니다
  let count = 0;
  let sort = stuff.sort((a,b)=>a-b); //[50,50,70,80] //[60,80,90,120,130]
  let left= 0;
  let right = sort.length-1
  
  while(left<right){
    if(sort[left]+sort[right]<=limit){
      count++
      left++
      right--
    }else{
      right--
    }
  }
  
  return stuff.length - count
}

 

 

'알고리즘' 카테고리의 다른 글

[조합] 블랙잭!  (0) 2022.01.02
최대공약수 (유클리드 호제)  (0) 2021.12.16
Quick sort (퀵소트, 퀵정렬) / merge sort(머지소트, 병합정렬)  (0) 2021.12.12
삽입정렬(insertionSort)  (0) 2021.12.12
toy 4. 버블정렬  (0) 2021.11.30
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/07   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함