그리디(Greedy) 알고리즘

1. 그리디 알고리즘이란?

그리디 알고리즘은 현재 상황에서 가장 좋은 것만 선택하고 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에 단순 암기를 통해서는 모든 문제에 대처하기 어렵다.

기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 “가장 큰 순서대로”, “가장 작은 순서대로”와 같은 기준을 알게 모르게 제시해준다. 또한 대체로 정렬 알고리즘과 짝을 이뤄 출제된다.

 

2. 예제

💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수 있음을 미리 밝힙니다.

2-1. 큰 수의 법칙

문제

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자.

이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에는 서로 다른 수로 간주한다.

예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고 K가 2라고 가정하자.

이 경우 두 번째 원소인 4와 네 번째 원소인 4를 번갈아 두 번씩 더하는 것이 가능하기 때문에 결과적으로 4+4+4+4+4+4+4인 28이 도출된다.

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

 

입력

• 첫째 줄에 N(2≤N≤1,000), M(1≤M≤10,000), K(1≤K≤10,000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단 각각의 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

입력 예시

5 8 3
2 4 5 4 6

출력 예시

46

 

풀이

가장 큰 수를 K번 더하고, 두번째로 큰 수를 1번 더하고, 다시 가장 큰 수를 K번 더하고… 이렇게 총 M번 더하면 된다고 생각했다.

주어진 N개의 자연수를 배열에 담고 Arrays.sort()를 이용해 정렬한다.

오름차순 정렬이기 때문에 가장 마지막 원소를 더하면서 count도 1을 더해준다.

만약 count가 K가 됐다면 두번째 큰 수를 한 번 더하고 count는 0으로 리셋한다.

count 변수를 쓰지 않고 인덱스로 계산해도 상관 없긴 한데 더 직관적으로 count 변수를 사용했다.

 

코드

package Study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

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

        int sum = 0;
        int count = 0;
        Arrays.sort(numArr);
        for(int i=0; i<M; i++) {
            if(count==K) {
                sum += numArr[N-2];
                count = 0;
                continue;
            }
            sum += numArr[N-1];
            count++;
        }
        System.out.println(sum);
    }
}

 

2-2. 숫자 카드 게임

문제

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

단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이 때, N은 행의 개수를 의미하며 M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

예를 들어 3 X 3 형태로 카드들이 다음과 같이 놓여 있다고 가정하자.

여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서는 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다.

카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

입력

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤N, M≤100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

출력

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

 

입력 예시

3 3
3 1 2
4 1 4
2 2 2

출력 예시

2

 

풀이

굳이 원소들을 2차원 배열에 담고 탐색할 필요가 없다.

한 줄씩 끊어서 최소값을 찾아낸 다음 N행의 최소값들 중 가장 큰 값을 출력하도록 했다.

 

코드

package Study;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] minArr = new int[N];
        for(int i=0; i<N; i++) {
            int min = 10_001;
            st = new StringTokenizer(br.readLine());
            for(int k=0; k<M; k++) {
                int temp = Integer.parseInt(st.nextToken());
                if(temp<min) min = temp;
            }
            minArr[i] = min;
        }

        System.out.println(Arrays.stream(minArr).max().getAsInt());

    }
}

 

2-3. 1이 될 때까지

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

예를 들어 N이 17, K가 4라고 가정하자. 이 때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.

N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 N(2≤N≤100,000)과 K(2≤K≤100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

 

입력 예시

25 5

출력 예시

2

 

풀이

N이 K로 나누어 떨어진다면 무조건 2번을 선택해야 한다.

따라서 나누어 떨어지지 않는다면 -1을, 나누어 떨어진다면 /K를 하도록 했다.

 

코드

package Study;

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

public class Main {
    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 count = 0;
        while(N>1) {
            if(N%K==0) {
                N /= K;
            }
            else {
                N -= 1;
            }
            count++;
        }
        System.out.println(count);

    }
}