그리디 (Greedy) 알고리즘

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

Posted Jan 26, 2024

By HyunJinNo

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. 참고 자료

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