탐욕법 ( Greedy )

탐욕법

탐욕법(탐욕 알고리즘, Greedy Algorithm)은 문제를 해결하는 방법 중 하나로, 매 선택에서 그 순간에 가장 좋아 보이는 것을 선택하는 방식이다. 이 방법은 전체를 고려하지 않고, 각 단계에서 최적의 해를 찾으려고 한다. 탐욕법은 구현이 간단하고 효율적인 경우가 많지만, 항상 최적의 해를 보장하지는 않는다.

탐욕법은 다양한 문제에 적용할 수 있지만, 모든 문제에 효과적인 것은 아니다. 예를 들어, 배낭 문제(Knapsack Problem), 최소 신장 트리(Minimum Spanning Tree), 그래프의 최단 경로 찾기 등이 탐욕법을 사용하여 효율적으로 해결할 수 있는 문제들이다. 그러나, 탐욕법을 적용할 때는 그 선택이 전체 문제에 대한 최적해를 보장하는지 검증하는 과정이 필요하다.

탐욕법의 주요 특징

• 지역 최적해 선택: 각 단계에서 지역적으로 최적인 선택을 함으로써, 최종적으로 전체 문제의 해결책을 도출한다.

• 탐욕적 속성: 한 번 선택된 해는 번복되지 않는다.

• 분할 불가능한 문제: 문제를 더 작은 문제로 나눌 수 없을 때 주로 사용된다.

프로그래머스 문제

프로그래머스 코딩테스트 문제에서 탐욕법 항목의 문제 중 하나다.

문제링크 - 프로그래머스 - 체육복

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {

        int answer = n;
        Arrays.sort(lost);
        Arrays.sort(reserve);

        List<Integer> list = new ArrayList<>();

         f2 : for (int j = 0; j < lost.length; j++) {
            for (int i = 0; i < reserve.length; i++) {
                if( lost[j] == reserve[i]) {
                    reserve[i] = -1;
                    continue f2;
                }
            }
            list.add(lost[j]);
        }

        f1 : for (int lo : list) {
            for (int i = 0; i < reserve.length; i++) {

                if( lo - 1 == reserve[i] || lo + 1 == reserve[i]) {
                    reserve[i] = -1;
                    continue f1;
                }
            }
            answer--;
        }
        return answer;

    }
}

1. 여벌 체육복을 가진 학생이 도둑맞은경우 ( 첫 반복문 (f2) )

여벌의 체육복을 가져온 학생이 동시에 체육복을 잃어버린 경우를 먼저 처리한다. 이는 탐욕법에서 자주 사용되는 "지금 당장의 최적해"를 찾는 방법이다. 여기서 최적해는 '자신의 체육복을 잃어버린 학생이 우선적으로 여벌을 사용하는 것'이다. 이 단계를 통해, 추가적인 체육복 분배를 위한 선택지를 명확하게 정리했다.

2. 체육복을 잃어버린 학생에게 적절한 학생이 체육복을 빌려주기 ( 두 번째 반복문 (f1) )

체육복을 잃어버린 학생들에게 여벌 체육복을 가진 학생들이 체육복을 빌려주는 과정이다. 이때, 체육복을 빌려줄 때마다 가장 가까운 번호의 학생에게 빌려주는 선택을 했다. 이는 "현재 상황에서 가장 좋아 보이는 선택"을 하는 탐욕적 접근법의 전형적인 예시이다.