그리드(Greedy) 알고리즘은 단순하지만 강력한 문제 해결 방법이다.
어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다.

예제 3-1 거스름돈

java 코드

public class Main {
    public static void main(String args[]){
    	int n = 1260;
        int count = 0;
        int[] coinTypes = {500, 100, 50, 10};
        for(int i = 0; i < 4; i++){
        	count += n / coinTypes[i];
            n %= coinTypes[i];
        }
    }
}

그리디 알고리즘의 정당성:
그리디 알고리즘은 모든 문제에 적용할 수있는 것은 아니다.
대부분의 그리디 알고리즘 문제에서는 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토 할 수있어야 답을 도출할 수있다.
거스름돈을 예로들자면 거스름돈 문제를 그리디로 풀수있는 이유는 큰수가 모든 작은 수의 배수이기 때문이다.

실전문제 1. 큰 수의 법칙

문제요약: N개만큼 배열을 입력 받을건데 M번 더할거다 그 때 한수의 연속된 덧셈은 K 번가능
조건: 2<=n<=1000 , 1<= M <=10000, 1<= K<=10000

첫번 째 풀이:

import java.util.*;

public class Main{
	public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < N; i++){
        	list.add(sc.nextInt());
        }
        Collections.sort(list);
        
        int count = 0;
        int sum = 0;
        while(true){
        	for(int i = 0; i < K; i++){
            	sum += list.get(N-1);
                count++;
                if(count == M){
                	break;
                }
            }
            sum += list.get(N-2);
            count++;
            if(count == M){
                break;
            }
        }
        
        System.out.println(sum);
        
    }
}

해설: 이 문제를 해결하기 위해 선 가장 큰 수와 다음으로 큰 수를 구해서, 가장 큰 수를 K번 더하고 그다음 큰 수를 한번 더하고를 반복하면 된다.
하지만 이문제는 M이 10000 이하이므로 이 방식으로 풀 수 있는 문제이다.
M의 크기가 100억이상처럼 커진다면 시간초과 판정을 받을 것이다.

더 효율적으로 풀기 위한 방법:
반복되는 수열을 파악하기
예를들어 가장큰수가 3 그다음수가 2일 때, M이 20 이고 K가 3이라면

3+3+3+2 3+3+3+2 3+3+3+2 3+3+3+2 3+3+3+2
(3+3+3+2) 가 수열의 형태로 일정하게 반복해서 더해지는 특징이있다.
이걸 식으로 나타낸다면

int count = (M / (k+1)) * k;
count += M % (k+1);
result += count * first;
result += (M -count) * second;

import java.util.*;

public class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M =sc.nextInt();
        int K =sc.nextInt();
        
        ArrayList<Integer> list =new ArrayList<>();
        for(int i = 0;i < N; i++){
        	list.add(sc.nextInt());
        }
        Collections.sort(list);
        int count = (M / (K+1)) * K;
        count += M % (K+1);
       	int sum =count * list.get(N-1);
        sum += (M-count) * list.get(N - 2);
        System.out.println(sum);
    }
}

실전문제 2.숫자 카드 게임

문제요약: 게임에 룰이있다. N * M 개의 카드중 가장 큰 수를 뽑아야하는데
뽑을 때 행에서 가장 작은 수를 뽑아야 한다. 즉 행들중 가장 작은 수 중에서 가장 큰수를 뽑는 문제이다.
조건은: 1<=N,M <=100 각 숫자는 1 이상10000이하의 자연수이다.

코드:

import java.util.Scanner;

public class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int m = sc.nextInt();
        int max = 0;
        for(int i = 0; i< n; i++){
            int min = 100001;
        	for(int j = 0 ; j < m ; j++){
            	 int temp = sc.nextInt();
                 min = Math.min(min,temp);
            }
            max = Math.max(max,min);
        }
        
        System.out.println(max);
    }
}

정렬관하여

package greeedy;

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

public class greedy2 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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 max = 0;
		ArrayList<Integer>list;
		for(int i = 0 ; i < n ; i ++) {
			st = new StringTokenizer(br.readLine());
			list = new ArrayList<>();
			for(int j = 0 ; j < m ; j++) {
				list.add(Integer.parseInt(st.nextToken()));
			}
			Collections.sort(list);
			max = Math.max(max, list.get(0));
		}
		System.out.println(max);
	}

}
//Collections.sort(list, Collections.reverseOrder());
//Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
//Collections.sort(list, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));

실전문제 3. 1이 될 때 까지

문제요약: N과 K 를 입력받는다. N 과 K 는 2<= N,K <=100000 이다.
이때 두가지 선택권이있다 .
1.N 에서 1을 뺀다.
2.N 을 K 로 나눈다(나누어 떨어질때만 가능)
1을 만드려고할 때 1,2번을 수행하는 최솟값을 구해라

import java.util.*;
public class Main{
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int k = sc.nextInt();
        int count = 0;
        while(n >= k){
        	if(n % k == 0 ){
            	n /= k;
            }else{
            	n--;
            }
            count++;
        }
        count += (n-1);
        System.out.println(count);
    }
	
}

책풀이:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // N, K를 공백을 기준으로 구분하여 입력 받기
        int n = sc.nextInt();
        int k = sc.nextInt();
        int result = 0;

        while (true) {
            // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
            int target = (n / k) * k;
            result += (n - target);
            n = target;
            // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
            if (n < k) break;
            // K로 나누기
            result += 1;
            n /= k;
        }

        // 마지막으로 남은 수에 대하여 1씩 빼기
        result += (n - 1);
        System.out.println(result);
    }

}