Greedy

Greedy❓ 

탐욕 알고리즘이라는 이름의 의미는 무엇일까요❓ 

 

Greedy 알고리즘은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달합니다.

하나의 선택은 그 당시에는 최적이며, 계속해서 최적들 중 최적의 해답을 골라내어 궁극적인 최적의 해답을 이끌어냅니다.

 

하지만, 해답이 궁극적으로 최적이라는 보장을 할 수는 없죠.

그래서 Greedy를 사용할 때에는 항상 최적의 해답을 주는지 반드시 검증하는 과정을 거쳐야 합니다.

 

 

Greedy 방법을 사용할 때, 다음과 같은 세 가지의 과정을 거치게 됩니다.

 

1. 선정 과정 Selection procedure

현재 상태에서 가장 좋다고 생각되는 해답을 찾아 Solution Set에 포함시킨다.

 

2. 적정성 점검 Feasibility check

새로 얻은 해답 모음이 적절한지 결정

 

3. 해답 점검 Solution Check

새로 얻은 해답 모음이 최적의 해인지 결정한다.

 

위의 과정을 pseudocode로 적으면 아래와 같이 표현됩니다.

 

// A(1..n) contains the n inputs

solution = null
for i=1 to n do
	x = SELECT(A)
    	if FEASIBLE(solution, x)
        	then solution = solution ∪ {x}
        endif
endfor
return(solution)

 

아직 뭔지 잘 모르시겠죠? 

지극히 정상입니다.

 

 

실제 JAVA 코드를 보면 이해가 갈 것 같아요 〰️ 

 

Activity Selection Problem

 

지정된 시간 내에 가장 많은  활동을 하려고 할 때, 어떤 활동들로 구성하면 되는지 탐색합니다.

 

Activity Selection Problem

 

예를들어 A라는 영업사원이 판매를 위해 a,b,c, 3개 업체와 미팅을 해야하는데 각 회의이 시작 시간과 회의 종료시간이 다음과 같다고 할때 A영업사원은 최대한 많은 업체와 미팅을 하기위해 어떤 업체를 선택할 수 있는가 ? 단, 회의는 겹치면 안된다.

 

위를 보면, s[]에는 시작 시간을 담아두었고 f[]는 종료시간을 담아두었습니다.

s와 f 는 종료 시간에 맞춰 정렬되었다고 가정합니다.

 

i 는 가능성있는 시작 시간의 인덱스를 저장하고, j는 다음 시작 시간을 확인합니다.

 

// JAVA CODE

class activitySelection {
    public static void printMaxActivities(int s[], int f[], int n) {
        int i = 0;
        for (int j = 1; j < n; j++) {
            if (s[j] >= f[i]) {
                System.out.print(j+" ");
                i = j;
            }
        }
    }

    public static void main(String[] args) {
        int s[] =  {1, 2, 4, 1, 5, 8, 9, 11, 13};
        int f[] =  {3, 5, 7, 8, 9, 10, 11, 14, 16};
        int n = s.length;

        printMaxActivities(s, f, n);
    }
}

 

출력 결과는 어떻게 될까요❓예상이 되나요 ~.~

 

0 2 5 7 

 

 

위와 같은 출력을 하면 되겠죠❓ 

이해가 어렵다면 아래의 그림을 보면 이해가 갈 것 같아요 〰️ 

 

 

Activity Selection Problem

 

 

참고 : https://www.geeksforgeeks.org/activity-selection-problem-greedy-algo-1/

 

위 사이트에 정렬되지 않을 때의 코드가 있으니 참고하시길 바랍니다  〰️