[알고리즘] 탐욕법(Greedy)

탐욕법 (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)
중복 부분 문제	중복 부분 문제를 해결하지 않습니다.	중복 부분 문제를 해결할 수 있습니다.
상황	- 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구합니다. - 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될수 있습니다.	- 모든 상황을 계산하여 최적의 경로를 구할 수 있습니다 - 모든 상황을 계산하기에 시간이 오래 걸립니다.

 

 

💡 그리디 알고리즘이라는 개념 자체가 다른 알고리즘과 비교하여 눈에 띄는 특징이나 패턴을 가지는 것이 아니기 때문에 그리디 알고리즘을 눈치채는게 나는 꽤 어렵게 느껴진다.

그리디 알고리즘의 주요 특징은 각 단계에서 현재 상황에서 가장 최적인 선택을 하는 것임을 잊지 말아야겠다.