[이코테 ]그리디(Greedy) 알고리즘

그리디 알고리즘이란?

현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

즉, 매 순간 가장 좋아 보이는 것을 선택하며 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

정렬 알고리즘과 짝을 이뤄서 출제되는 경우가 많다.

 

바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심해볼 수 있다.

 

하지만 그리디 알고리즘을 모든 상황에 적용할 수 있는 것은 아니다.

현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.

그렇기 때문에 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한 방법인지 검토해야 한다.

 

대표적인 그리디 알고리즘의 문제로 '거스름돈' 문제가 있다.

---

예제 1) 거스름돈

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구한다.

거스름돈으로는 500원, 100원, 50원, 10원짜리 동전을 사용하고, N은 항상 10의 배수이다.

 

문제 해설

• '가장 큰 화폐 단위부터' 돈을 거슬러준다.
• 각 동전마다 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 거슬러 줄 수 있다.
• ex) 거스름돈 N=1260이면 500원 2개, 100원 2개, 50원 1개, 10원 1개 로 최소 동전의 개수는 6개 이다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int[] coins = {500, 100, 50, 10};

        int N = Integer.parseInt(br.readLine());

        int count = 0;
        for (int coin : coins) {
            count += N / coin;
            N %= coin;
        }

        bw.write(count + "\n");

        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 2) 큰 수의 법칙

큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때, 이 수들을 M번 더해서 가장 큰 수를 만드는 법칙이다.

이 때, 배열의 특정 인덱스에 해당하는 수가 연속해서 K번을 초과해서 더하면 안된다.

예를 들어 2, 4, 5, 4, 6 배열과 M=8, K=3이라고 하면, 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5 = 46 이다.

배열크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때, 큰 수의 법칙에 따른 결과를 출력한다.

 

문제 해설

• '가장 큰 수를 K번, 두 번째로 큰 수를  1번' 더하는 것을 반복해서 가장 큰 수를 만들 수 있다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());	//배열의 크기
        int m = Integer.parseInt(st.nextToken());	//숫자가 더해지는 횟수
        int k = Integer.parseInt(st.nextToken());	//연속 가능 횟수

        int[] array = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(array);
        int first = array[n - 1];   //가장 큰 수
        int second = array[n - 2];  //두번째로 큰 수

        int result = 0;
        int count = 0;  //가장 큰 수의 덧셈 횟수
        count += m / (k + 1) * k;
        count += m % (k + 1);

        result += count * first;
        result += (m - count) * second;
        bw.write(result + "\n");

        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 3) 숫자 카드 게임

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다.

n * m 형태로 숫자 카드가 놓여 있을 때,

1. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

2. 그 행에 포함된 카드들 중에서 가장 숫자가 낮은 숫자 카드를 뽑는다.

3. 1에서 행을 선택할 때, 최종적으로 각 행의 가장 숫자가 낮은 카드들 중에서 가장 높은 숫자 카드를 뽑아야 하는 것을 고려해서 행을 선택해야한다.

 

문제 해설

• 각 행마다 가장 작은 수를 찾은 후, 그 작은 수들 중에서 가장 큰 수를 찾는다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] array = new int[m];
        int result = 0;
        //각 행에서 가장 작은 수들의 모임들 중에서 가장 큰 수를 구해라
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int row_min = 100001;
            for (int j = 0; j < m; j++) {
                array[j] = Integer.parseInt(st.nextToken());
                row_min = Math.min(row_min, array[j]);	//각 행에서 가장 작은수 찾기
            }
            result = Math.max(result, row_min);	//가장 작은 수들 중에서 가장 큰 수 찾기
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

 

 

 

 

예제 4) 1이 될때까지

어떠한 수 N이 1이 될 때까지 아래 두 과정 중 하나를 반복적으로 선택해서 수행한다.

1. N에서 1을 뺀다.

2. N을 K로 나눈다. (N이 K로 나누어떨어질 때만 가능)

이 때, 최소 수행 횟수를 구한다.

 

문제해설

• 최소 수행 횟수가 되기 위해서 '1을 빼는 것' 보다 '나누는 것'이 숫자를 빠르게 줄일 수 있다.
• 따라서 '최대한 많이 나누기'를 수행한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int result = 0;

        /*
        방법1. 일일이 1을 빼고 k로 나눈다.
        */
        /*
        while (n > 1) {
            if (n % k == 0) {
                n /= k;
            } else {
                n -= 1;
            }
            result++;
        }*/


        /*
        * 방법2. 1을 한번에 빼고 k로 나눈다.
        */
        while (true) {
            //n이 k로 나누어떨어지도록 1씩 빼기
            int target = (n /k) * k;
            result += n - target;
            n = target;

            //n < k이면 더이상 나눌 수 없기 때문에 탈출
            if (n < k) {
                break;
            }

            //k로 나누기
            result++;
            n /= k;
        }

        result += n - 1;    //k로 나누지 못하고 남은 수 빼기

        bw.write(result + "\n");
        bw.flush();
        bw.close();
    }
}

---

[참고]

이것이 취업을 위한 코딩 테스트다 with 파이썬