태인의 Blog/
그리디 알고리즘
Forest
그리디 알고리즘

그리디 알고리즘

작성자
태인태인
카테고리
📗 스터디
작성일
2024년 06월 29일
태그
Java
Algorithm

그리디(Greedy) 알고리즘

그리디 알고리즘은 ‘욕심’이라는 영어 뜻에서 유추할 수 있듯이, 현재 상태에서 선택 가능한 최선의 선택지를 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 매 순간에 최적의 선택을 해나가는 방식이므로, 항상 최적의 해를 보장하지 않음을 주의해야 한다. 아래 사진을 보면 이해가 쉽다.
그리디 알고리즘의 수행 과정을 정리하면 다음과 같다.
  1. 최선의 해 선택 : 현재 상태를 기준으로 가장 최선의 해를 선택한다.
  1. 적절성 검사 : 현재 선택한 해가 문제의 제약 조건에 부합하는 지 확인한다.
  1. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지를 확인한 후, 만약 해결하지 못한다면 1번으로 돌아가 반복한다.
 
이해를 돕기 위해, 예제를 살펴보자.

백준 #11047번 : 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
먼저, 그리디 알고리즘을 적용할 수 있는 문제인지를 확인해봐야 한다. 입력 조건에서 Ai는 Ai-1의 배수 라고 명시되어 있으므로, 매번 가장 가격이 큰 동전부터 차례대로 사용하면 된다.
즉, 가격이 큰 동전부터 내림차순으로 K(현재 지불해야 하는 금액)보다 작거나 같은 동전이 나올 때까지 탐색한 후, 그때의 가격으로 K를 갱신해가면 문제를 해결할 수 있다. 사용한 동전의 개수는 result 에 저장하자.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    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[] coins = new int[N];


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

        int result = 0;
        for(int i=N-1; i>=0; i--) {
            if(coins[i] <= K) {
                result += K / coins[i]; // 사용한 동전 개수 추가
                K = K % coins[i]; // 남은 금액 갱신
            }
        }

        System.out.println(result);
    }
}
 
문제를 하나 더 풀어보자.

백준 #1541번 : 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.
역시 그리디 알고리즘을 이용하면 쉽게 풀 수 있는 문제이다. 식의 결과를 최소로 만들어야 하므로, 뺄셈을 할 때는 최대한 큰 수를 빼야 한다. 수식에는 덧셈과 뺄셈만 포함되어 있으니 더하기 부분에 괄호를 만들어 계산한 후, 빼기를 실행하면 된다. 아래의 식을 예를 들어보자.
이렇게, 덧셈끼리 괄호로 묶은 후 뺄셈하면 최솟값을 구할 수 있다. 이를 구현하기 위해서는 우선 수식을 ‘-’ 부호를 기준으로 자른 후, 덧셈을 먼저 계산한 후 뺄셈을 진행해주면 된다. 코드로 작성하면 다음과 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String exp = br.readLine();
        int result = 0;

        String[] termsByMinus = exp.split("-");
        for(int i=0; i<termsByMinus.length; i++) {
            int sum = getSum(termsByMinus[i]);
            if(i==0) result += sum;
            else result -= sum;
        }

        System.out.println(result);
    }

    private static int getSum(String exp) {
        String[] termsByPlus = exp.split("\\+");
        int sum = 0;
        for(int i=0; i<termsByPlus.length; i++) {
            sum += Integer.parseInt(termsByPlus[i]);
        }
        return sum;
    }
}
 

댓글

guest