Greedy 알고리즘이란?

: 현재 단계에서 가장 좋은 방법을 선택하는 알고리즘

= 탐욕법

고로 순간마다 최적의 선택이 전체 최적해가 되지 않을 수도 있다!

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이므로
잘 작동하는 문제가 따로 정해져 있다

그리디 알고리즘을 적용할 수 있는 문제는

조건

1. 현재 선택이 이전의 선택에 있어 독립적이다. (탐욕 선택 조건)
2. 전체 최적해가 부분 최적해를 만족한다. (최적 부분 구조 조건)

독립적이어야 매 순간마다의 선택이 최적해를 이끌어낼 수 있을 것이니까...

백준 예제

11047번 - 동전 0

package Greedy;

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

public class Coin0 { //11047
    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 cnt = 0; // 금액 K를 만드는데 필요한 동전 개수
        int[] coin = new int[n]; //동전 종류 배열

        for(int i =0;i<n;i++){
            coin[i] = Integer.parseInt(br.readLine());
        }


        for(int i =n-1;i>=0;i--){
            while(k/coin[i] >0){
                int div = k/coin[i];
                k %= coin[i];
                cnt += div;
            }
        }

        System.out.println(cnt);
    }
}

1541번 - 잃어버린 괄호

package Greedy;

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

public class LostBracket {//1541

    /*
    빼기 부호가 하나라도 나타난다면 그 후는 모두 빼기처리가 가능하다
     */

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //delimiter 2가지 + - return 하도록
        StringTokenizer st = new StringTokenizer(br.readLine(), "-|+", true);

        String[] oper = new String[51];

        int n = st.countTokens();
        
        for (int i = 0; i < n; i++) {
            oper[i] = st.nextToken();
        }
        int ans = Integer.parseInt(oper[0]);

        for (int i = 1; i < n; i++) {
            if (oper[i - 1].equals("+")) {
                ans += Integer.parseInt(oper[i]);
            } else if (oper[i - 1].equals("-")) {
                while (i < n) {
                    ans -= Integer.parseInt(oper[i]);
                    i = i + 2;
                }

            }
        }

        System.out.println(ans);
    }

}

알고리즘을 계속 공부하고 있지만...
마음에 안드는 그리디... 후 유노댓 암 그리디뽀럽