알고리즘으로 기강 잡기 - 그리디 알고리즘 (탐욕법)

그리디 알고리즘

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

핵심 이론

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사, 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복 수행

그리디 알고리즘 구현

백준 11047번 - 동전 0

import java.util.*;

class Main {
    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 = k % a[i];
            	if (k == 0) break; 
            }
        }
        
        System.out.println(count);
    }
}

백준 1541번 - 잃어버린 괄호

import java.util.*;

class Main {
    public static void main(String[] args) {
        int answer = 0;
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strs = str.split("-");
        
        for (int i = 0; i < strs.length; i++) {
            int num = sumNumber(strs[i]);
            if (i == 0) answer += num;
            else        answer -= num;
        }
        
        System.out.println(answer);
    }    
    
    public static int sumNumber(String str) {
        int sum = 0;
        String[] strs = str.split("[+]");
        
        for (int i = 0; i < strs.length; i++) {
            sum += Integer.parseInt(strs[i]);
        }
        
        return sum;
    }
}