그리디 (Greedy) 알고리즘

Tags
Algorithm

개요

그리디(Greedy) 알고리즘에 대해 정리한 페이지입니다.

그리디 (Greedy) 알고리즘

개념

그리디(Greedy) 알고리즘은 각 단계마다 지금 당장 가장 좋은 방법만을 선택하여 답을 찾는 알고리즘 기법을 의미합니다. 재귀 호출과 마찬가지로 큰 문제를 여러 개의 부분 문제로 나누고, 각 부문 문제의 답으로부터 전체 문제의 답을 찾아낸다는 점에서 유사하자만, 모든 경우의 수를 고려하지 않고 항상 각 단계마다 가장 좋은 방법만을 선택한다는 점에서 차이가 있습니다.

특징

그리디 알고리즘의 특징은 다음과 같습니다.

Caution
아래의 탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)가 만족되어야만 그리디 알고리즘을 적용할 수 있습니다.

• 탐욕적 선택 속성(Greedy Choice Property)

  동적 계획법(Dynamic Programming)이 모든 경우의 수를 계산하는 것과는 다르게, 탐욕적으로 가장 좋은 방법만을 선택하더라도 최적해를 구할 수 있어야 합니다. 즉, 각 단계에서의 최적의 선택이 전체에서도 최선이어야 합니다.

• 최적 부분 구조(Optimal Substructure)

  큰 문제의 최적해를 작은 부분 문제들의 최적해로부터 구할 수 있어야 합니다. 즉, 전체 문제의 최적해는 그 부분 문제들의 최적해로부터 구성될 수 있어야 합니다.

  Info.
  최적 부분 구조(Optimal Substructure): 큰 문제의 최적해를 작은 부분 문제들의 최적해로부터 구할 수 있는 성질

• 시간 복잡도(Time complexity)

  모든 경우의 수를 구하는 동적 계획법과 달리, 항상 각 단계마다 가장 좋은 방법만을 선택하기 때문에 동적 계획법보다 훨씬 빠르게 해를 구할 수 있습니다.

Example

• 2812번: 크게 만들기

  const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
  const input = require("fs").readFileSync(path).toString().split("\n");
  
  // 1 <= k <= n <= 500,000
  let [n, k] = input[0].split(" ").map(Number);
  const num = input[1];
  const stack = [];
  
  for (let i = 0; i < num.length; i++) {
    const temp = Number(num[i]);
  
    while (stack.length > 0 && k > 0 && stack[stack.length - 1] < temp) {
      stack.pop();
      k--;
    }
    stack.push(temp);
  }
  
  for (let i = 0; i < k; i++) {
    stack.pop();
  }
  
  console.log(stack.join(""));
  

참고 자료

• 그리디 알고리즘 - 나무위키