그리디(Greedy) 자바 백준 11047, 1715, 1744

그리디(Greedy)

그리디(Greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다.

그래서 동적 계획법(Dynamic Programming) 보다 구현하기 쉽고 시간 복잡도가 우수합니다. 

 

하지만 항상 최적의 해를 보장하지는 못한다는 단점도 있습니다. 그래서 항상 그리디 알고리즘을 사용하기 전 논리에 대해 자세히 살펴보아야 합니다.

 

그리디 알고리즘의 수행 과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2. 적절성 검사: 현재 선택한 해가 전체 문제의 조건에서 벗어나지 않는지 검사

3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결할 수 없다면 1의 과정을 반복.

 

바로 문제를 3개 정도 풀어봅시다!

 

백준 11047 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

1. 문제 분석

크게 어려울 것이 없는 전형적인 그리디 문제입니다. N의 최대가 10밖에 되지 않으므로 시간 제약은 크지 않습니다. 

동전을 최소로 사용하여 K 를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 됩니다.

 

2. 손으로 풀기

 

3. 슈도코드

N: 동전 종류, K: 주어진 값.
배열 coins: 동전 종류

index: coins 의 마지막 인덱스 = N -1
cnt: 동전 개수 = 0

while(K 가 0이 될 때까지){
    coin 은 coins[index]
    if(K < coin){ index--;}
    else { // K >= coin
       cnt += (K / coin)
       K = K % coin
       index--;
   }
}
sout(cnt)

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BaekJun11047 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        int index = N - 1;
        int cnt = 0;

        while (K != 0) {
            if (K < coins[index]) {
                index--;
            } else {
                cnt += (K / coins[index]);
                K = K % coins[index];
            }
        }
        System.out.println(cnt);
    }
}

 

 

백준 1715 카드 정렬하기

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

1. 문제 분석

문제에서 친절히 설명하듯이 먼저 선택된 카드 붂음이 비교횟수에 더 많은 영향을 미치는 것을 알 수 있습니다. 그러므로 먼저 선택하는 카드는 가장 작은 것부터 합쳐야 합니다.

 

 

왼쪽처럼 카드 뭉치가 5개 있다고 합시다.

대략적인 순서를 봅시다.

 

1. 가장 작은 10 과 20을 합칠 때 결과에 (10 + 20)인 30 을 더합니다. 카드 뭉치 10, 20 짜리가 없어지고 30짜리가 생겼습니다.

2. 가장 작은 25와 25가 합쳐졌습니다. 결과에  (25 + 25)인 50 을 더합니다. 카드 뭉치 25, 25가 없어지고 50짜리가 생겼습니다.

3. 가장 작은 30과 40 이 합쳐집니다. 여기서 30에는 기존에 10 카드 뭉치가 포함되어 있습니다. 그러므로 결과에 (10 + 20) + (40)인 70을 더합니다. 카드뭉치 30, 40이 없어지고 70짜리가 생깁니다.

4. 가장 작은 카드 뭉치 50과 70이 합쳐집니다. 3과 마찬가지로 생각하면 결과에 (25 + 25) + ( (10 + 20) + 40) 인 120 을 더합니다.

 

가장 작은 카드 뭉치였던 10짜리 카드들은 합쳐질 때 3번이나 다시 합쳐지고 있습니다. 즉, 가장 작은 수가 결과에 3번이나 영향을 미치고 있습니다. 

더 카드 뭉치의 개수가 많아질 때를 생각하면 항상 카드를 합칠 때 가장 작은 카드 뭉치부터 합쳐나가야 하는 것을 생각할 수 있습니다.

 

그런데 항상 이를 탐색할 때 단순 반복 탐색을 하면 O(N) 의 시간이 듭니다. N 은 최대 100,000 일 때 합치는 수행은 99,999 번 해야 한다.  그러므로 최대 O(100,000 𝘅 99,999) => 약 10,000,000,000 의 연산으로 100억번 의 연산. 100초가 걸립니다.

우선순위 큐를 이용한다면 O(NlogN) = 100,000 𝘅 17 = 1,700,000 번의 연산으로 가능합니다. 우선순위 큐를 이용해봅시다.

 

2. 손으로 풀기

문제 분석에서 상세히 분석했으니 간단히 풀어봅시다.

 

먼저 카드뭉치의 개수를 우선순위 큐에 넣습니다.

만약 하나의 카드뭉치밖에 없다면 합칠 수가 없으므로 그냥 0번입니다.

그렇지 않다면 우선순위 큐가 빌 때까지 두개씩 poll 이 둘을 합치고 결과에 더해준 뒤, 합친 값을 큐에 넣어줍니다. 우선순위 큐에 값이 들어갈 때 이미 정해진 정렬 순서를 따라 자동으로 정렬됩니다. 기본으로 오름차순으로 정렬되기 때문에 따로 정렬 규칙도 구현하지 않아도 되겠네요!

 

3. 슈도코드

N: 카드 뭉치들의 수
pQu: 각 카드 뭉치의 수를 저장하는 우선순위 큐
우선순위 큐는 오름차순으로 정렬하도록 설정.

각 카드 뭉치의 수를 입력받아 pQu 에 저장
int result;

카드 뭉치의 수가 1이면 그냥 sout(result)
아니라면{
    while(큐가 빌 때까지){
        a = pQu.poll();
        만약 큐가 비어있으면{ result += a; break;}
        아니면
        b = pQu.poll();)
        c = a + b
        result += c
        만약 큐가 비었으면{ break;}
        아니라면 pQu.offer(c)
    }
}
sout(result)

4. 코드

public class BaekJun1715 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pQu = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {
            pQu.offer(Integer.parseInt(br.readLine()));
        }

        int result = 0;
        if (N != 1) {
            while (!pQu.isEmpty()) {
                int a = pQu.poll();
                if (pQu.isEmpty()) {
                    result += a;
                    break;
                }
                int b = pQu.poll();
                int c = a + b;
                result += c;
                if (pQu.isEmpty()) {
                    break;
                } else {
                    pQu.offer(c);
                }
            }
        }
        System.out.println(result);
    }
}

 

 

백준 1744 수 묶기

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

1. 문제 분석

N의 최대값은 10,000 이므로 시간 복잡도 제약은 적습니다. 가능한 큰 수들끼리 묶어야 결과값이 커진다는 것을 알 수 있습니다. 

그런데 주의할 점은 음수와 0입니다. 주의할 수들을 정리해봅시다.

 

2. 손으로 풀기

a. 양수

    a-1. 양수가 두 개 이상이면

        a-1-1. 두 양수가 1일 때는 곱하는 것보다 더하는 것이 값이 더 큽니다.

        a-1-2. 아닐 때는 곱하는 것이 더 크다. 큰 것들부터 곱하는 것이 유리합니다.

    a-2. 양수가 한 개이면 그냥 더합니다.

 

b. 0을 입력받은 횟수를 저장해야 합니다. 

 

c. 음수

    c-1. 음수가 두 개 이상이면 해당 두 음수를 곱한다. 음수의 절대값이 큰 것, 즉, 작은 것들부터 곱하는 것이 유리하다.

    c-2. 음수가 한 개 이면 

        c-2-1. 0을 입력받은 횟수가 1이상이라면  0과 곱합니다. 그렇다면 이 음수는 결과값에 영향을 주지 않습니다. 그리고 0을 입력받은 횟수를  1만큼 줄입니다.

        c-2-2. 입력된 수 중에서 0이 없다면 그냥 더합니다.

 

그렇다면 양수와 음수를 위한 우선순위큐를 만들어서 해결하면 좋을 것 같습니다.

양수 우선순위큐는 정렬 기준을 내림차순으로, 음수 우선순위큐는 정렬 기준을 오름차순으로 하면 되겠네요. 0 은 얼마나 입력받았는지 횟수만 중요하므로 단순 int 값으로 하면 될 것 같습니다.

 

3. 슈도코드

N: 수의 개수
int result = 0;
posPQ: 양수우선순위큐, 내림차순 정렬
negPQ: 음수 우선순위 큐. 오름차순 정렬
zeroCnt: 0의 개수

for(N){ 수 입력 받기
    수가 양수면 posPQ 에 담고, 음수면 neqPQ 에 담는다.
    만약 0이면 담지 않고 zeroCnt 을 1 늘린다.
}

while(posPQ 가 빌때까지){
    posPQ 안에 수가 두개 이상이면{
        a = poll, b = poll
        temp = (a*b)와 (a+b) 중 최대
        result += temp
    } 한 개이면{
        result += poll;
    }
}

while(negPQ 가 빌때까지){
    negPQ 안에 수가 두개 이상이면 {
        a = poll, b = poll
        result += a * b
    } 한개이면
        만약 0 이 있었다면{
            zeroCnt--;
            poll;
        }0이 없으면{
            result += poll
        }
    }
}
sout(result)

4. 코드

public class BaekJun1744 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> posPQ = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> negPQ = new PriorityQueue<>();
        int result = 0;
        int zeroCnt = 0;
        for (int i = 0; i < N; i++) {
            int curNum = Integer.parseInt(br.readLine());
            if (curNum > 0) {
                posPQ.offer(curNum);
            } else if (curNum == 0) {
                zeroCnt++;
            } else { // curNum < 0
                negPQ.offer(curNum);
            }
        }

        while (!posPQ.isEmpty()) {
            if (posPQ.size() > 1) {
                int a = posPQ.poll();
                int b = posPQ.poll();
                int temp = Math.max(a + b, a * b);
                result += temp;
            } else {
                result += posPQ.poll();
            }
        }

        while (!negPQ.isEmpty()) {
            if (negPQ.size() > 1) {
                int a = negPQ.poll();
                int b = negPQ.poll();
                result += (a * b);
            } else {
                if (zeroCnt > 0) {
                    zeroCnt--;
                    negPQ.poll();
                } else {
                    result += negPQ.poll();
                }
            }
        }
        System.out.println(result);
    }
}