그리디 (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
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(""));