Greedy [탐욕] 알고리즘

그리디 알고리즘은 탐욕법으로도 알려져있다.
이 알고리즘의 특징은 "현재 상황에서 지금 당당 좋은 것만 고르는 방법"을 찾는 것이다.

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

순간마다 하는 선택은 그 순간, 지역적으로 최적이지만, 그 선택들을 계속 수집하여 최정적인 해답을 만들었다면, 그것은 최적이라는 보장은 없다.

탐욕 알고리즘 문제를 해결하는 법
1. 선택 절차 : 현재 상태에서 최적의 해답을 선택
2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사 : 원래의 문제가 해결 되었는지 검사 후, 해결되지 않았으면 위의 과정을 반복

그리디 알고리즘 연습

위의 해결법 3가지를 연습문제를 통해 학습해보았다.

Q1. 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원 10원 짜리 동전이 무한이 존재한다고 가정한다. 손님에게 거슬러 줘야할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

해결방법

문제에서 제한을 둔 것은 N의 값은 항상 10의 배수 이다 라는 것이다. 이것은 1원과 5원이 존재하지 않다는 것을 의미한다.
동전의 최소 개수로 손님한테 제공하기 위해서는 액수가 큰 동전부터 아래 단계의 동전으로 내려오는 방식을 선택할 수 있다.

문제 해결 code

public class Charge {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader =  new BufferedReader(new InputStreamReader(System.in));

        int cost = Integer.parseInt(bufferedReader.readLine());

        List<Integer> coins = Arrays.asList(500, 100, 50, 10);

        int count = 0;

        for(int i = 0; i < coins.size(); i++){
            count += (cost / coins.get(i));
            cost %= coins.get(i);

        }

        System.out.println(count);
    }
}

물건의 최종 가격을 받는 변수와, 동전의 종류를 담고 있는 리스트를 생성한다.
그 다음, 큰 액수의 화폐 단위부터 나눗셈을 진행하면서 현재의 가격에서 교환할 수 있는 동전의 개수를 구한다.
값을 구한 뒤, 다음 동전을 통해 개수를 구하기 전에, 나머지 연산을 통해 현재의 화폐 단위로 교환할 수 있는 금액을 차감한다.

반복문을 마치고 나면 최적의 동전 개수 결과가 나올 것이다.

Q2. 큰 수의 법칙

큰 수의 법칙은 일반적으로 통계 분야에서 다루어지는 내용이지만, OO은 본인만의 방식으로 다르게 사용하고 있다. OO의 큰 수 의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수 를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속 해서 K번 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

ex) 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46이 된다. 서로 다른 인덱스에 같은 수가 존재할 때에도 서로 다른 수로 간주한다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 최대 덧샘 가능 개수 K가 주어질 때 큰 수의 법칙에 따른 결과를 출력하시오.

입력조건

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

출력조건

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

입력예시

 5 8 3
 2 4 5 4 6

출력예시

46

해결방법

해당문제는 가장 큰 수와 두 번째로 큰 수를 구하는 것부터 진행 해야한다. 리스트 정렬을 통해 가장 큰 수와 두번 째로 큰수를 구하고, 큰 수의 법칙에 따라 값을 도출 할 수 있다.
여기서 해결법이 갈릴 수 있다.

1. for를 통한 반복을 통해 결과를 도출하는 방법
2. 계산식을 통해 결과를 도출하는 방법

위와 같이 두가지 방법을 제시할 수 있다.

M의 조건이 작을 경우에는 무엇을 사용하던 간에 상관이 없겠지만, M의 조건이 1억이 넘어가면 시간 초과가 걸릴 수 도 있다.
때문에 계산식으로 진행 하는 것도 하나의 방법이라고 할 수 있다.

public class LawOfBigNumbers {
    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());

        int[] numbers = new int[n];
        st = new StringTokenizer(br.readLine());

        int i  = 0;
        while(st.hasMoreTokens()){
            numbers[i++] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(numbers);
        int sum = 0;

		// 1번 방식
        /*for(int i = 0; i < m; i++){
            if((i + 1) % k ==0){
                sum += numbers[numbers.length - 2];
            }else{
                 sum += numbers[numbers.length - 1];
            }
        }*/


		// 2번 방식
        sum += (numbers[numbers.length - 1] * k) * (m / k);
        sum += numbers[numbers.length - 2] * (m % k);

        System.out.println(sum);
    }
}

주석으로 처리된 1번 방식은 for를 사용한 반복문을 통해 가장 큰수 카운트가 K번 이루어 질 때까지 카운트를 하다가
K 배수가 될 경우 두 번째 큰 수를 더하는 방법을 채택한 방식이다.

두 번째 방식은 계산식을 사용한 방식으로 가장 큰 수를 통해 얻을 수 있는 값과 두 번째 큰 수로 만들 수 있는 수를 계산한 것이다. 가장 큰 수의 계산 법은 1싸이클 당 K번을 더할 수 있다 했으니, (가장 큰 수 * k)를 진행한다. 이 후 M번 반복 중 몇 사이클을 돌 수 있는 지 계산을 하여 곱해주면, 가장 큰 수를 통해 얻을 수 있는 합의 값을 얻을 수 있다.

두 번째로 큰 수의 합은 M번 반복 중 가장 큰 수 덧셈 횟수의 나머지를 곱해주면 된다.

Q3. 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 < 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건

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

입력예시

25 5

출력예시

2

public class UnitBecomeOne {
    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);
    }
}

while을 통해 n이 1이 아닐 때 까지 반복을 수행한다. 이 후 1의 조건과 2의 조건에 의해 연산이 수행되면 카운트를 1씩 증가 시켜 n이 1이 될 때까지 연산을 수행한다.