탐욕(Greedy) 알고리즘

그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

특징은 항상 최적의 해라는 보장은 없다. 잘 따져보지 않으면 반례가 있기 때문

핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.

3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 해결하지 못한다면 1로 돌아가서 같은 과정을 반복한다.

문제풀이

동전 개수의 최솟값 구하기 (백준 11047)

https://www.acmicpc.net/problem/11047

import java.util.Scanner;

public class Baekjoon11047 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] A = new int[N];

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        // 큰 동전의 가치만큼 먼저 사용하기
        int count = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (A[i] <= K) {
                count += K / A[i];
                K %= A[i];
            }
        }
        System.out.println(count);
    }
}

잃어버린 괄호 (백준 1541)

https://www.acmicpc.net/problem/1541

public class Baekjoon1541 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int answer = 0;

        String[] minus = sc.nextLine().split("-");
        for (int i = 0; i < minus.length; i++) {
            int sum = 0;
            String[] plus = minus[i].split("[+]");
            for (int j = 0; j < plus.length; j++) {
                sum += Integer.parseInt(plus[j]);
            }

            if (i == 0) answer = sum;
            else answer -= sum;
        }

        System.out.println(answer);
    }
}