Post

그리디 (Greedy) 알고리즘

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

그리디 (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번: 크게 만들기

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    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(""));
    

참고 자료

This post is licensed under CC BY 4.0 by the author.