탐욕법

Greedy Algorithm🏋

탐욕 알고리즘은 말 그래도 탐욕스러운 이라는 의미를 가지며 , 선택의 순간이 오면 눈앞에 보이는 최적의 상황만을 고려하여 최종적인 해답에 도달하는 방법을 말합니다. 이 알고리즘은 각 선택의 순가에는 최적으로 보일 수 있지만, 그 선택이 전체적으로 보았을 때 최적인지는 보장되지 않을 수 있습니다.

Greedy Algorithm  불가능한 경우

1. 현재 상황에서는 마시멜로 1개를 받을 수 있습니다.(현재 시점에서의 최선의 선택)

2. 그러나 5분을 기다리면 2개의 마시멜로를 받을 수 있습니다. (미래를 고려한 선택)

 

그리디 알고리즘에 따르면 각 단계에서 현재 최선으로 보이는 선택을 하기 때문에 현재 시점에서 1개의 마시멜로를 받는 것이 선택될 것입니다. 그러나 미래를 고려할 경우 5분을 기다린다면 2개의 마시멜로를 받는 것이 더 많은 마시멜로를 받는 최선의 선택입니다. 따라서 그리디 알고리즘을 사용하면 항상 1개의 마시멜로만 받게 됩니다. 하지만 최적의 해를 찾기 위해서는 미래의 상황을 고려해야 하므로 그리디 알고리즘은 적절하지 않습니다.

Greedy Algorithm 정당성 - 최적해 도출

탐욕적 선택 속성

각 단계에서 최적으로 보이는 선택을 하여도 전체적으로 항상 최적의 해를 보장한다는 의미, 즉 각 단계에서의 선택이 그 순간에는 최적으로 보이지만, 이러한 선택들이 모여서 최종적으로는 전체 문제의 최적해를 구성합니다.

 

문제

가게에서 물건을 사고 돈을 지불할 때, 거스름돈으로 줘야 하는 동전의 개수를 최소화하는 문제입니다.

예시

물건 가격이 520원이고 손님이 1000원을 지불한다고 할 때 최소한의 동전 개수로 거스름돈을 주려면 어떻게 해야 할까?

 

가장 큰 단위의 동전을 사용하여 거스름돈을 주는 것이 최적의 해를 구할 수 있는 경우

 

해결방법

1. 손님이 지불한 돈의 물건의 가격을 뺀 480원이 거스름돈입니다.
2. 거스름돈을 주기 위해 가장 큰 단위의 동전부터 사용하게 됩니다. 가장 큰 단위의 동전은 500원입니다. 
3. 그러나 거스름돈이 480원 이므로 500원을 사용학 되면 20원이 초과하게 됩니다. 따라서 500원짜리 동전은 사용하지 않습니다.
4. 다음으로 큰 단위인 동전 100원짜리를 사용해 100원짜리 동전 4개를 주고, 남은 거스름돈 480 - 400 = 80 이 됩니다.
5. 남은 거스름돈 80원에 대해 다시 큰 단위 동전부터 시도합니다.
6. 80원에서 50원짜리 동전을 사용하면 남은 거스름돈은 30원이 됩니다.
7. 남은 거스름돈 30원에 대해 다시 큰 동전부터 시도합니다.
8. 30원 에서 10원짜리 동전 3개를 사용하여 거스름돈을 줍니다.

 

최적 부분 구조

큰 문제를 작은 부분 문제로 나눌 수 있고, 각 부분 문제의 최적해가 전체 문제의 최적해에 기여할 수 있다는 개념, 즉 전체 문제를 작은 단위로 분할하여 각 단계에서 최적해를 찾으면 이를 조합하여 전체 문제의 최적해를 찾을 수 있습니다.

 

큰 문제를 해결하는 최적의 방법이 그 문제를 구성하는 작은 부분들의 최적의 해결 방법으로 구성될 수 있다는 개념이며 예를 들어보면 서울에서 부산까지 가는 최단 경로 문제라고 생각해 보면, 이 문제는 서울에서 대구까지의 최단 경로와 대구에서 부산까지의 최단 경로라는 두 개의 부분 문제로 나눌 수 있습니다. 서울에서 대구까지 가는 최단 경로가 200km , 대구에서 부산까지 가는 최단 경로가 80km일 때 전체 경로의 최단 거리는 이 두 부분 문제의 해결 방법을 합친 280km가 됩니다. 따라서, 복잡한 문제의 최적해는 그 문제를 구성하는 더 작은 부분 문제들의 최적해를 결합함으로써 찾을 수 있다는 것이 최적 부분 구조의 핵심 원리입니다.

 

탐욕법 문제 적용

import java.util.*;

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

        // 배열로 체육복 보유 여부
        int[] students = new int[n];
        
        // 잃어버린 학생
        for (int i : lost){
            students[i - 1]--;
        }
        // 가지고 있는 학생
        for (int j : reserve){
            students[j - 1]++;
        }
        
        // 빌려줌
        for (int k = 0; k < students.length; k++){
            //도난
            if(students[k] == -1){
                //앞 번호 여벌 체육복
               if(k - 1 >= 0 && students[k-1] == 1){
                   students[k]++;
                   students[k - 1]--;
                //뒷 번호 여벌 체육복
               } else if (k + 1 < students.length && students[k + 1] == 1) {
                   students[k]++;
                   students[k + 1]--;
               }
            }
        }
        // 듣는 학생수
        int studentsCount = 0;
        for (int s : students) {
            if(s>=0){
                studentsCount++;
            }
        }
        return studentsCount;
    }
}

초기 설정

학생들의 체육복 상태를 나타내기 위한 배열 students를 생성합니다. 배열의 각 원소는 해당 학생의 체육복 보유 상태를 나타냅니다 (기본값 0: 체육복을 딱 맞게 가지고 있음, -1: 체육복을 잃어버림, 1: 여분의 체육복이 있음).

 

체육복 상태 업데이트

먼저 lost 배열을 순회하여 체육복을 잃어버린 학생의 students 배열에서 해당 학생의 값을 -1로 감소시킵니다.

reserve 배열을 순회하여 여분의 체육복을 가진 학생의 students 배열에서 해당 학생의 값을 1로 증가시킵니다.

 

체육복 빌려주기

students 배열을 순회하면서 체육복을 잃어버린 학생(-1)을 찾습니다.

각 잃어버린 학생에 대하여, 앞 번호 학생부터 여분의 체육복(1)을 가진 학생이 있는지 확인하고, 있다면 그 학생으로부터 체육복을 빌립니다. 앞 번호 학생에게서 빌릴 수 없는 경우, 뒷 번호 학생에게서 빌립니다.

여분의 체육복을 빌려줄 때마다 해당 학생의 students 배열 값을 조정하여, 체육복을 빌린 학생은 0으로 (체육복을 가진 상태로), 체육복을 빌려준 학생은 1에서 0으로 조정합니다.

 

체육 수업을 들을 수 있는 학생 수 계산

마지막으로, students 배열을 순회하면서 체육복을 가지고 있는 학생의 수를 세어 (students 배열의 값이 0 또는 1인 학생), 이를 반환합니다.

 

탐욕적 선택의 적용

이 문제에서 탐욕적 선택은 잃어버린 학생이 체육복을 빌릴 수 있을 때, 가능한 한 가까운 번호의 학생으로부터 빌리는 것입니다. 이 방식은 각 단계에서 지역적으로 최적의 선택을 하여, 전체적으로도 최대한 많은 학생이 체육 수업을 들을 수 있도록 합니다. 여기서 지역적으로 최적이란, 잃어버린 학생 바로 앞이나 바로 뒤의 학생으로부터 체육복을 빌리는 것을 의미합니다. 이러한 탐욕적 접근 방식은 이 문제의 구조와 맞아떨어져, 전체적으로도 최적의 결과(최대한 많은 학생이 체육 수업을 듣는 것)를 도출할 수 있습니다.