그리디 알고리즘 (feat. leetcode)

진과 해나와 함께 한 알고리즘 스터디

진이 정말 열심히 준비해주셔서 넘 감사했다.
(참고: https://possible-oatmeal-64f.notion.site/3d7cea299b074ae7b1512421c104ba75)

그리드 알고리즘

정의

https://ko.wikipedia.org/wiki/탐욕_알고리즘

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

중요한건 지역적 -> 전역적으로 넓혀가진다는 것
그리고 모든 경우에 최적은 아니다.
특정 조건이 만족되어야 동작한다. 그러지 않으면? -> 완전탐색법 같은 다른 알고리즘을 사용한다.

문제 풀이

-> 엄선한 문제들

1. https://leetcode.com/problems/maximum-69-number/

// 탐욕법 문제
// 숫자를 바꿔서 얻을 수 있는 가장 큰 수
// 6을 9로 바꾼다

var maximum69Number  = function(num) {    
     return String(num).replace('6', '9');
};

2. https://leetcode.com/problems/maximum-units-on-a-truck/

var maximumUnits = function(boxTypes, truckSize) {
  boxTypes.sort((a,b)=> b[1]-a[1]);

  let capacity = truckSize;
  let toiesCount = 0;
  
boxTypes.forEach(([boxCount, toyPerBox]) => {
    if (capacity < boxCount) {
      toiesCount += (capacity * toyPerBox);
      capacity = 0;
      return;
    }
    capacity -= boxCount;
    toiesCount += (boxCount * toyPerBox);
  });

  return toiesCount;
}

3. https://leetcode.com/problems/longest-palindrome/

-> 예외 조건 하나를 조금 생각하기 어려웠던 문제..!

var longestPalindrome = function(s) {
      const dict = [...s].reduce((a, i) => (a[i] = (a[i] || 0) + 1, a), {});

  let result = 0;

  Object.values(dict).forEach((count) => {
    if (count % 2 === 0) {
      result += count;
    }

    // 그 다음으로 있는 홀수 값(짝수개로 만들어줌)
    if (count % 2 === 1) {
      result += count - 1;
    }

    // 최초에 더해주는 홀수 값
    if (result % 2 === 0 && count % 2 === 1) {
      result += 1;
    }
  });

  return result;

};