[알고리즘] 그리디 알고리즘

 

그리디 알고리즘?

 

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 단, 모든 문제에 무작정 사용하는 것이 아니라 전체 선택지에서 똑같이 적용되는 지 꼭 확인해야 한다.

 

그래서 그리디 알고리즘을 고려하기 위한 3가지 단계는 다음과 같다.

1. 해 선택 : 현재 상태에서 최선의 해를 선택한다.

2. 적절성 검사 : 선택한 해가 전체 문제 제약 조건에 벗어나는 지 확인한다.

3. 해 검사 : 선택한 해 집합이 전체 문제를 해결할 수 있는 지 확인한다. 못한다면, 다시 해 선택으로 이동한다.

 

 

 

 

예시 문제를 통해 어떤 방식으로 그리디 알고리즘이 사용될 수 있는 지 알아보자.

 

 

 

 

 

그리디 알고리즘 문제 예시 1

 

11047번: 동전 0

 

 

그리디를 간단하게 사용해 볼 수 있는 백준 11047번 문제이다.

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] A = new int[n];

        for(int i=0; i<n; i++) {
            A[i] = sc.nextInt();
        }

        int count = 0;
        for(int i=n-1; i>=0; i--) {
            if (A[i] <= k) {
                count += (k / A[i]);
                k = k % A[i];
            }
        }

        System.out.println(count);
    }

}

 

동전을 최소로 사용하여, K를 만들기 위해서는 가장 가격이 큰 동전부터 사용해야 한다.

즉, 현재 가장 큰 동전을 사용하는 방법이 전체 답에 있어서 올바른 접근이 되므로, 그리디를 사용했다고 볼 수 있다.

 

 

가장 전형적인 그리디 알고리즘 사용은 간단하지만, 난이도가 올라가면 더욱 다양한 방법을 사용해야 하는 경우도 있다.

다음 문제를 한 번 살펴보자.

 

 

 

 

 

그리디 알고리즘 문제 예시 2

 

 

1715번: 카드 정렬하기

 

 

백준 1715번 문제는 그리디를 적용시키기 위해 우선 순위 큐를 도입한다.

어찌보면, 우선 순위를 도입한다는 것 자체가 현재 상태에 대한 최선의 선택을 전체 답을 위한 선택으로 사용한다는 것으로 이해할 수 있기도 하다.

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i=0; i<n; i++) {
            int data = sc.nextInt();
            pq.add(data);
        }

        int data1 = 0;
        int data2 = 0;
        int sum = 0;

        while(pq.size() != 1) {
            data1 = pq.remove();
            data2 = pq.remove();
            sum += data1 + data2;

            pq.add(data1 + data2);
        }
        System.out.println(sum);

    }

}

 

카드 묶음을 어떻게 묶어야 최소한의 비교를 할 수 있는 지 묻는 문제이다.

우선 순위를 사용할 줄 안다면, 티어가 높은 것에 비해 쉬운 편이다.

 

이 문제는 카드 묶음을 뽑고, 다시 정렬하는 과정이 여러번 반복된다. 이렇게 삽입, 삭제, 정렬이 자주 일어날 때, 우선 순위 큐를 생각해 볼 수 있다.

 

 

 

- 우선 순위 큐(오름차순)에 값을 삽입하여, 값을 넣을 때 마다 정렬 시켜준다.

- 큐의 크기가 1이 될 때까지, 값을 꺼내어 합치면서 비교 횟수가 최소가 될 수 있도록 한다.

 

 

 

 

그리디 알고리즘 문제 예시 3

 

 

위 문제보다 보다 복잡하게 우선 순위 큐를 사용하는 문제이다.

1744번: 수 묶기

 

 

우선 순위 큐를 도입한 순간, 현재 상황에 있어 최선의 선택을 한다는 것을 이전에 확인했다.

이 문제의 경우에도 동일한 로직으로 문제를 해결할 수 있다. 다만, 마냥 우선순위를 사용하면 안된다.

 

분기를 생성해야 한다. 양수, 음수, 1, 0인 경우로 나누어야 한다.

합이 최대가 나오게 하기 위해서는 음수끼리는 서로 곱해야 하며, 홀수라면 0을 곱해 최대한의 음수를 지워주어야 한다.

 

그 과정에서 우선순위가 여러 개 생성될 수 있다.

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        PriorityQueue<Integer> plusPq = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minusPq = new PriorityQueue<>();
        int one = 0;
        int zero = 0;

        for(int i=0; i<n; i++) {
            int data = sc.nextInt();
            if (data > 1) {
                plusPq.add(data);
            } else if (data == 1) {
                one++;
            } else if (data == 0) {
                zero++;
            } else {
                minusPq.add(data);
            }
        }

        int sum = 0;
        while(plusPq.size() > 1) {
            int num1 = plusPq.remove();
            int num2 = plusPq.remove();
            sum += num1 * num2;
        }
        if (!plusPq.isEmpty()) {
            sum += plusPq.remove();
        }

        while(minusPq.size() > 1) {
            int num1 = minusPq.remove();
            int num2 = minusPq.remove();
            sum += num1 * num2;
        }

        if (!minusPq.isEmpty()) {
            if(zero == 0) {
                sum += minusPq.remove();
            }
        }

        sum += one;
        System.out.println(sum);
    }

}

 

 

- 양수 우선순위 큐, 음수 우선순위 큐, 1의 갯수, 0의 갯수를 체크해준다.

- 양수는 그대로 곱해주고 더해주면 되지만, 음수는 -가 되는 경우를 체크해주어 0을 곱해준다.(그래야 음수를 최대한 없앨 수 있기 때문)

 

 

 

그리디 알고리즘 문제 예시 4

 

그리디 알고리즘은 우선 순위 큐 이외에도, 자바의 Comparator를 통해서 실현 할 수 있다.

결국에는 들어올 때다마 최선의 순서를 정해 줌은 동일하기 때문이다.

 

1931번: 회의실 배정

 

백준 1931번 문제에서 Comparator를 통해 그리디를 사용해 볼 수 있다.

 

Comparotor의 좋은 점은, 원하는 기준대로 정렬을 할 수 있다는 것이다.

이 말이 의미하는 것은 원하는 기준대로 최선의 선택을 할 수 있다는 것.

 

문제를 살펴보면, 현재 회의 종료 시간이 빠를 수록 좋다는 것을 알 수 있다.

즉, 정렬을 통해 종료시간이 빠른 순서대로 둘 수 있는데, 이 때 종료시간이 같다면, 앞선 회의 시간이 빠른 것이 우선으로 와야 한다.

 

이러한 기준을 통해서 정렬을 한다면, 데이터가 들어올 때마다 최선의 선택을 할 수 있고,

데이터 입력이 종료되었을 때, 전체에서 최선의 선택이 될 것이다.

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] A = new int[n][2];
        for(int i=0; i<n; i++) {
            A[i][0] = sc.nextInt();
            A[i][1] = sc.nextInt();
        }
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] S, int[] E) {
                if (S[1] == E[1]) {
                    return S[0] - E[0];
                }
                return S[1] - E[1];
            }
        });
        int count = 0;
        int end = -1;

        for(int i=0; i<n; i++) {
            if (A[i][0] >= end) {
                end = A[i][1];
                count++;
            }
        }
        System.out.println(count);


    }

}

 

 

 

- sort 시에 Comparator를 익명 객체로 인자를 둘 수 있다.

- 정렬 시에 디폴트는 오름차순이다. (반환되는 값이 양수인 경우에 원소가 swap, 음수인 경우 swap 하지 않기 때문이다.)

 

 

 

그리디 알고리즘 문제 예시 5

 

문자열에서 그리디 문제를 처리하는 경우도 생각해보자.

 

1541번: 잃어버린 괄호

 

 

가장 최솟 값을 만들기 위해서는 가장 큰 값을 빼야 한다.

그러기 위해서 더하기에 해당하는 부분을 제일 먼저 전부 더해 버린 뒤, 괄호를 치고 빼면 되는 것이다.

 

 

import java.util.*;
import java.io.*;
public class Main {
    static int answer;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String example = sc.nextLine();

        String[] str = example.split("-");
        for(int i=0; i< str.length; i++) {
            int temp = mySum(str[i]);
            if (i == 0) {
                answer += temp;
            } else {
                answer -= temp;
            }

        }
        System.out.println(answer);


    }

    static int mySum(String a) {
        int sum = 0;
        String temp[] = a.split("[+]");
        for(int i=0; i<temp.length; i++) {
            sum += Integer.parseInt(temp[i]);
        }
        return sum;
    }

}

 

 

 

 

 

- 제일 처음 -를 기준으로 split해주어, 한번에 더할 그룹들을 정해준다.

- 그룹 내에 있는 수들을 한 번에 더해주기 위한 함수 mySum을 만들어, 더해준다.

- -를 기준으로 split 한 값 중, 첫 번째 그룹은 answer에 더해주고(얘는 뺄 대상이 아니므로), 나머지는 빼준다.

 

 

 

Reference

 

- Do it! 코딩 테스트 - 기초 편