그리디 (Greedy) 알고리즘

Tags

Algorithm

1. 개요

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

2. 그리디 (Greedy) 알고리즘

2.1. 개념

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

2.2. 특징

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

Caution

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

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

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

• 최적 부분 구조(Optimal Substructure)

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

  Info.

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

• 시간 복잡도(Time complexity)

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

3. Example

• 2812번: 크게 만들기

  javascript

  1const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
  2const input = require("fs").readFileSync(path).toString().split("\n");
  3
  4// 1 <= k <= n <= 500,000
  5let [n, k] = input[0].split(" ").map(Number);
  6const num = input[1];
  7const stack = [];
  8
  9for (let i = 0; i < num.length; i++) {
  10  const temp = Number(num[i]);
  11
  12  while (stack.length > 0 && k > 0 && stack[stack.length - 1] < temp) {
  13    stack.pop();
  14    k--;
  15  }
  16  stack.push(temp);
  17}
  18
  19for (let i = 0; i < k; i++) {
  20  stack.pop();
  21}
  22
  23console.log(stack.join(""));

4. 참고 자료

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