탐욕법 (Greedy)
그리디 알고리즘 (탐욕법, Greedy Algorithm) 이란?
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
'각 단계에서 최적이라고 생각되는 것을 선택'해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘
- 이 때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 한다.
탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
그리디 알고리즘 활용 기법
1. 탐욕 선택 속상 (greedy choice property)
각 단계에서 '최선의 선택'을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말한다.
즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것이다.
2. 최적 부분 구조(Optimal Substructure)
전체 문제의 최적해가 '부분 문제의 최적해로 구성'될 수 있는 경우를 말한다.
즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다.
그리디 알고리즘 단계
매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정
1. 문제의 최적해 구조를 결정한다.
2. 문제의 구조에 맞게 선택 절차를 정의한다. → 선택 절차 (select procedure)
💡 선택 절차란 : '현재 상태'에서 '최적인 선택'을 한다. 이 선택은 이후에는 바뀌지 않는다.
3. 선택 절차에 따라 선택을 수행한다.
4. 선택된 해가 문제의 조건을 만족하는지 검사한다. → 적절성 검사(Feasibility Check)
💡 적절성 검사 : 선택한 항목이 '문제의 조건'을 만족시키는지 확인 후 조건을 만족하지 않으면 해당 항목은 제외
5. 조건을 만족하지 않으면 해당 해를 제외한다.
6. 모든 선택이 완료되면 해답을 검사한다. → 해답 검사 (solution check)
💡 해답 검사 : 이 단계에서는 모든 선택이 완료되면, '최종선택'이 '문제의 조건을 만족'시키는지 확인한다. 조건을 만족시키면 해답으로 인정
7. 조건을 만족하지 않으면 해답으로 인정되지 않음.
예시 # 프로그래머스 Level1 : 체육복
https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript
1. 선택 절차 : 선택 과정에서 체육복을 읽어버린 학생과 여벌 체육복을 가져온 학생의 번호를 오름차순으로 정렬합니다.
2. 적절성 검사 : 체육복을 잃어버린 학생 중 여벌이 있는 학생에게 빌려줄 수 있는 학생 수를 계산하고, 그다음에는 체육복을 잃어버린 학생 중 여벌이 없는 학생에게 빌려줄 수 있는 학생 수를 계산합니다.
3. 해답 검사 : 체육복을 빌려 받은 학생 수를 계산하여 반환합니다.
내가 작성한 코드
function solution(n, lost, reserve) {
var answer = 0;
const students = Array(n).fill(1);
lost.forEach(st => students[st-1]--);
reserve.forEach(st => students[st-1]++);
for(let i = 0 ; i < students.length ; i++) {
if(students[i] !== 0) continue;
if(students[i-1] > 1) {
students[i]++;
students[i-1]--;
} else if(students[i+1] > 1) {
students[i]++;
students[i+1]--;
}
}
students.forEach(st => {if(st > 0) answer++});
return answer;
}
1. 최적 부분 구조 : 각 학생에게 최적의 선택을 한다고 가정할 때, 이 선택이 전체 학생들에 대한 최적의 해결책으로 이어진다.
2. 탐욕적 선택 속성 : 각 학생이 가장 적은 비용으로 체육복을 얻을 수 있는 방법을 선택한다.
→ 각 학생이 도난당한 체육복이 있거나 여분의 체육복이 있는 상황에서 최대한 많은 학생이 체육 수업에 참여해야한다.
그리디 알고리즘 vs 동적 계획법
분류 | 그리디 알고리즘(Greedy Algorithm) | 동적 계획법(DP: Dynamic Programming) |
설명 | 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결하는 방식 | 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결하는 방식 |
성립 조건 | 1. 탐욕 선택 속성(Greedy Choice Property) 2. 최적 부분 구조(Optimal Substructure) |
1. 중복 부분 문제 (Overlapping Subproblems) 2. 최적 부분 구조 (Optimal Substructure) |
중복 부분 문제 | 중복 부분 문제를 해결하지 않습니다. | 중복 부분 문제를 해결할 수 있습니다. |
상황 | - 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다. - 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다. |
- 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다 - 모든 상황을 계산하기에 시간이 오래 걸립니다. |
💡 그리디 알고리즘이라는 개념 자체가 다른 알고리즘과 비교하여 눈에 띄는 특징이나 패턴을 가지는 것이 아니기 때문에 그리디 알고리즘을 눈치채는게 나는 꽤 어렵게 느껴진다.
그리디 알고리즘의 주요 특징은 각 단계에서 현재 상황에서 가장 최적인 선택을 하는 것임을 잊지 말아야겠다.
'알고리즘' 카테고리의 다른 글
[알고리즘]프로그래머스 - N으로 표현 <동적계획법(DP)> (0) | 2024.03.04 |
---|---|
[알고리즘] 백준 13904 과제 node.js (Greedy) (0) | 2024.02.23 |
[알고리즘] 완전탐색 예제 # 1 단순 브루트포스 (0) | 2024.02.05 |
[알고리즘] 완전 탐색 (0) | 2024.02.02 |
[알고리즘] Hash (1) | 2023.12.06 |