[알고리즘] Greedy Algorithm

그리디(=욕심쟁이, 탐욕) 알고리즘

 그리디 알고리즘은 각 단계에서 가장 최선의 선택을 한 후, 선택한 답이 전체적으로도 최선의 방법이기를 '바라는' 알고리즘이다. 최선의 방법이기를 바란다는 말에서 알 수 있듯이 부분적(local)으로만 최선의 해답이고 전역적(global)으로는 최선의 방법이 아닌 경우에 그리디 알고리즘을 적용하게 되면 최선의 해답을 얻을 수 없다. 즉, 그리디 알고리즘을 사용한다고 해서 무조건 최선의 해답을 보장할 수 없다. 따라서 그리디 알고리즘을 사용했을 때 최적의 해답을 주는지가 검증되어야 한다.

 

vs DP

그리디 알고리즘은 동적 프로그래밍과 다르게 지난 선택이나 앞으로의 선택을 고려하지 않는다. 그러므로 탐욕 알고리즘을 적용하려면 앞의 선택이 이후 선택에 영향을 주지 않고 부분적인 해답이 전역적 해답인 경우에 적용해볼 만하다. 탐욕 알고리즘은 이렇듯 모든 경우에 최적의 결과를 도출하지는 않지만, 어느 정도 최적의 근사한 값을 빠르게 구할 수 있기 때문에 최적화 이외에도 근사 알고리즘으로도 사용된다.

 

설계

1. Selection procedure(선정과정)

 : 현재 상태에서 가장 좋으리라고 생각되는 해답을 찾아서 해답모음에 포함시킨다.

2. Feasibility check(적정성 점검)

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

3. Solution check(해답점검)

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

//설계 예시
//Problem : 동전의 개수가 최소가 되도록 거스름돈을 주는 문제

while(problem not yet solved) {
    grab the largest remaining coin; //선정과정
    
    if(adding the coin makes the change exceed the amount owed) //적정성 점검
        reject, put it back the coin;
    else
        add the coin to the change;
        
    if(the total value of the change == amount owing) //해답 점검
        instance solved;
}

 

그리디 문제를 bfs나 dfs등으로도 풀 수 있는데, 이렇게 되면 시간이나 메모리 측면에서 손해를 많이 보기 때문에 주의하자.

 

 

예시) BOJ 1931: 회의실 배정

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int cnt=0;
        int prev_end_time=0;

        int[][] arr = new int[N+1][3];

        for(int i=1; i<=N; i++) {
            arr[i][1] = sc.nextInt(); //시작시간
            arr[i][2] = sc.nextInt(); //종료시간
        }

        //Comparator의 compare메소드를 재정의
        //배열을 비교하여 종료시간이 빠른순 정렬. 단 종료시간이 같다면 시작시간이 빠른순 정렬
        // == 종료시간이 빠른것부터 추가되며, 종료시간이 같다면 시작시간이 느린순 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                if(o1[2]==o2[2])
                    return o1[1]-o2[1];

                return o1[2]-o2[2];
                //
            }
        });

        for(int i=1; i<=N; i++) {
            if(prev_end_time <= arr[i][1]) {
                prev_end_time = arr[i][2];
                cnt++;
            }
        }

        System.out.println(cnt);

    }
}

> 종료시간 순으로 정렬하고, 종료시간이 같은 경우 시작시간 순으로 정렬해주면 된다. 왜냐하면 종료시간이 빠를 경우, 아무리 회의시간이 짧더라도 종료시간이 느린 것과 비교했을 때 우선순위를 갖기 때문이다.

출처 https://st-lab.tistory.com/145

 

 

예시 2) BOJ 16953: A->B

//BOJ 16953 greedy
package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        long A = Integer.parseInt(line_1[0]);
        long B = Integer.parseInt(line_1[1]);
        int depth = 1;

        while(A<=B) {
            if(B==A) {
                System.out.println(depth);
                return;
            }
            if(B%10==1) {
                B-=1;
                B/=10;
            }
            else if(B%2==0) {
                B/=2;
            }
            else {
                break;
            }
            depth++;
        }

        System.out.println("-1");
    }
}

 A에서 B를 만드는 최소값을 찾는 과정은 B에서 A를 찾아가는 최소 과정을 찾는 것과 동일하므로, 끝자리가 1로 끝나면 무조건 (B-1)/10을, 2로 나누어 떨어지면 B/2를 계산하면 되고, 둘 다 불가능하면 A에서 B를 만들 수 없다는 것을 의미한다.

 

(이 문제의 경우 bfs로도 풀 수 있는 방법이 있긴 하지만, 앞서 말했듯이 그리디 문제의 경우 bfs로 풀 수 없는 경우도 있다고 한다. )

//BOJ 16953 bfs
package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        long A = Integer.parseInt(line_1[0]);
        long B = Integer.parseInt(line_1[1]);
        int depth=1;

        Queue<Long> queue = new LinkedList<>();
        queue.add(A);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0; i<size; i++) {
                long pop = queue.remove();
                if (pop == B) {
                    System.out.println(depth);
                    return;
                } else {
                    long i1 = pop * 2;
                    long i2 = pop * 10 + 1;
                    if (i1 <= B) queue.add(i1);
                    if (i2 <= B) queue.add(i2);
                }
            }
            depth++;
        }
        System.out.println("-1");
    }
}

 

이처럼 앞의 선택이 뒤의 선택에 영향을 주지 않아 부분적인 해답이 전역적 해답이 될 경우 그리디 알고리즘을 사용하면 된다. 다만 위의 16953번과 같은 케이스에 그리디 알고리즘인지 구분하는 것은 직관의 영역인 것 같아서,, 문제를 많이 풀어보는 수밖에 없는 것 같다.