[TIL] 알고리즘 - 탐욕 알고리즘, GCD

Today I Learned

탐욕 알고리즘 Greedy Algorithm

• 모든 경우를 탐색하지 않고 각 단계에서 최적의 선택을 함
• 지역적 최적값이 전역적 최적값이 아닐 수도 있기 때문에 모든 문제에 적용할 수는 없음
• 동적 프로그래밍과 상호 보완
  • 동적 프로그래밍 : 느리지만 정확
  • 탐욕 : 빠르지만 부정확할 수 있음
• 탐욕 알고리즘은 항상 정확한 최적해를 도출하지는 않지만 빠르기 때문에 근사 알고리즘으로 사용할 수 있다
• 매트로이드 : 탐욕 알고리즘으로 언제나 최적해를 도출할 수 있는 구조의 문제

탐욕 알고리즘을 사용할 수 있는 조건

• 탐욕스런 선택 조건 : 앞의 선택이 이후 선택에 영향을 주지 않음
• 최적 부분 구조 조건 : 문제의 최적해는 부분 최적해로 구성됨

탐욕 알고리즘 문제 해결 방법

1. 현재 상태에서 최적의 해를 선택
2. 선택한 해가 문제의 조건을 충족하는지 검사
3. 전체 문제가 해결되었는지 검사 (=> 해결되지 않았다면 다시 1번으로 돌아가 반복)

예 : 동전의 개수를 최소한으로 하여 거스름돈 만들기

거스름돈 change가 주어졌을 때, 동전의 개수를 최소한으로 하여 거스름돈을 만들려면 몇 개의 동전을 사용해야 하는지 구하시오.

function makeChange(change) {
  const target = change;
  const coins = [500, 100, 50, 10, 5, 1];
  let current = 0;
  let count = 0;
  for (let i = 0, n = coins.length; i < n; i++) {
    const n = Math.floor(target / coins[i]);
    count += n;
    target -= (n * coins[i]);
  }
  return count;
}

GCD 최대공약수

유클리드 호제법

• 유클리드 호제법으로 GCD를 구할 수 있다
• 원리 : a > b일 때, a와 b의 GCD는 b와 r(r = a % b)의 GCD와 같다
• 위 과정을 반복하며 나머지가 0이 되었을 때 나누는 수가 a와 b의 GCD가 된다
• 구현 :

function getGCD(a, b) {
  while(b !== 0) {
    a = a % b;
    if (b > a) {
      let temp = b;
      b = a;
      a = temp;
    }
  }
  return a;
}