Greedy Algorithm 그리디 알고리즘

By Jimmyberg
algorithm greedy

Greedy Algorithm

그리디 알고리즘

그리디 알고리즘은 현재 상태에서 최선의 선택지가 전체 문제를 해결할 수 있다고 가정하는 알고리즘이다.

그리디 알고리즘 수행 과정

  1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
  2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
  3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사하고, 해결하지 못한다면 1 번으로 돌아가 다시 반복

그리디 알고리즘 관련 문제

문제 032. 동전 개수의 최솟값 구하기

문제 설명

소유하고 있는 동전 총 N 종류 중, 동전의 합 K 를 구하기 위한 동전 개수의 최솟값 구하는 프로그램을 작성하시오.

문제 조건
  • 1 <= N <= 10
  • 1 <= K <= 100,000,000
  • 동전 N 배열은 금액 오름차순으로 정렬
  • 동전 A^i = 동전 A^i-1 의 배수

풀이 방법

  1. 동전 N 배열은 오름차순이며 앞 동전의 배수로 이뤄진다. 이는 동전 금액이 큰 동전부터 탐색을 해야한다.
  2. K 를 만족하는 최대 금액 동전을 찾고, K / 동전 금액 = 동전 사용 개수 를 구하고, 나머지는 K 값으로 변경한다.
  3. 다시 1번 항목부터 탐색하면서 같은 동작을 반복한다.

구현

public void solution() {
    int N = 10, K = 4200, count = 0;
    int[] coins = {1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000};

    for (int i = coins.length - 1; i >= 0; i--) {
        int coin = coins[i];

        if (coin <= K) {
            // 현재 동전의 금액이 K 와 같거나 작은 경우
            count += K / coin;
            K = K % coin;
        }
    }

    System.out.println("count = " + count);
}

문제 033. 카드 정렬하기

문제 설명

정렬된 두 개의 숫자 카드 묶음 A와 B가 있다면, 각 카드 묶음을 1개로 합칠려면 A + B번 비교해야한다.

N 개의 숫자 카드 묶음이 있는 경우, 최소한의 비교로 합칠 수 있는 횟수를 구하는 프로그램을 작성하시오.

문제 조건

  • 1 <= N <= 100,000
  • 숫자 카드 묶음의 크기는 1,000 보다 작거나 같다.

풀이 방법

  • 해당 문제는 최소한의 비교를 위해 작은 카드 묶음부터 비교해야 한다.
  • 2개의 작은 묶음을 비교하고, 합쳐진 묶음의 크기를 다시 다음 작은 카드 묶음과 비교한다.
    • 데이터의 삽입, 삭제, 정렬이 자주 일어나므로, 큐 Queue를 활용하는 것이 좋다.
  1. 현재 카드 개수가 가장 작은 묶음 2개를 선택하여 합산한다.
  2. 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.
  3. 다시 1번 항목부터 카드 묶음이 1개만 남을 때까지 반복한다.

구현

public void solution() {
    int N = 3;
    int[] A = {10, 20, 40};
    A = Arrays.stream(A).sorted().toArray();

    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for (int i : A) {
        queue.add(i);
    }
    int sum = 0;
    while (queue.size() > 1) {
        int i = queue.remove();
        int j = queue.remove();
        sum += i + j;
        queue.add(sum);
    }

    System.out.println("queue.poll() = " + queue.poll());
}

문제 034. 수를 묶어서 최댓값 만들기

문제 설명

수열의 합을 구하지만, 구하기 전에 먼저 수열 안에 있는 임의의 두 수를 묶어서 합산을 한다.

단, 같은 위치에 있는 수(자기 자신)를 묶을 수 없고, 묶인 두 수는 수열의 합을 구할 때 서로 곱한 후 계산된다. 수열의 모든 수는 각 한 번씩만 묶을 수 있다.

각 묶음 수까지 모두 합산하였을 때, 최댓값을 구하는 프로그램을 작성하시오.

문제 조건

  • 1 <= N <= 10,000
  • 수열의 각 수 범위 : -10,000 <= n <= 10,000

풀이 방법

  1. 수열을 3가지의 집합으로 나눈다.
    • 1보다 큰 양수
    • 1의 개수
    • 0의 개수
    • 음수
  2. 1보다 큰 양수 집합은 정렬을 한 뒤, 가장 큰 수부터 2개씩 순서대로 곱한 후에 나머지를 더한다.
  3. 음수 집합은 정렬을 한 뒤, 가장 작은 수부터 2개씩 곱하여 더한다. 집합 원소가 홀수일 때, 0의 개수 집합이 있다면 0을 곱해서 0으로 만들고, 없다면 그대로 합산한다.
  4. 1의 개수 집합은 그대로 더한다.

구현

public void solution() {
    int N = 9;
    int[] A = {-1, -8, 2, 1, 3, 6, -5, 0, 1};
    System.out.println("A.length = " + A.length);

    PriorityQueue<Integer> positive = new PriorityQueue<>(Collections.reverseOrder());
    PriorityQueue<Integer> negative = new PriorityQueue<>();
    int one = 0, zero = 0;

    for (int i : A) {
        if (i > 1) {
            positive.add(i);
        } else if (i < 0) {
            negative.add(i);
        } else if (i == 1) {
            one++;
        } else {
            zero++;
        }
    }

    int positive_sum = 0, negative_sum = 0;

    while (positive.size() > 1) {
        positive_sum += positive.remove() * positive.remove();
    }
    if (!positive.isEmpty()) {
        positive_sum += positive.remove();
    }

    while (negative.size() > 1) {
        negative_sum += negative.remove() * negative.remove();
    }
    if (zero == 0) {
        negative_sum += negative.remove();
    }

    System.out.println("total_sum = " + (positive_sum + negative_sum + one));
}

출처