[2025 1학기 알고리즘 스터디] 남윤찬 #3주차

그리디 알고리즘

정리

그리디 알고리즘(Greedy Algorithm), 직역하면 탐욕 알고리즘이다. 이름에서 직관적으로 알 수 있듯이, 매 선택에서 최선으로 보이는 답을 선택하는 알고리즘이다. 그만큼 빠르고 단순하지만 항상 최적해를 보장하지는 못한다.

조건

그리디 알고리즘을 적용시키기 위해서는 두 가지의 조건이 필요하다

탐욕 선택 속성: 앞의 선택이 이후의 선택에 영향을 주면 안된다. 현 시점에서의 최선의 선택이 전체적으로도 최선의 선택이어야 한다. 이 말이 완벽히 이해되지는 않는데, 가장 큰 예시인 활동 선택 문제를 떠올리면 받아들이기는 비교적 수월할 것 같다.

최적 부분 구조: 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 한다. 쉽게 말해 점화식이다. 해결하고자 하는 문제를 부분으로 나눈 작은 문제들을 반복했을 때 큰 문제에 도달할 수 있어야 한다.

그리디 알고리즘을 적용시키는 대표적인 예시는 아래와 같다.

 

---

회의실 배정

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] times = new int[n][2];
        for (int i = 0; i < n ; i++) {
            times[i][0] = scanner.nextInt(); // 회의 시작 시간
            times[i][1] = scanner.nextInt(); // 회의 종료 시간
        }
        
        // Arrays.sort를 이용한 이차원 배열 정렬
        Arrays.sort(times, new Comparator<int[]>() {
            
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) return o1[0] - o2[0]; // 종료 시간이 같으면 시작 시간이 작은 순서대로 정렬
                return o1[1] - o2[1]; // 종료 시간이 작은 순서대로 정렬
            }
        });

        for (int[] time : times) {
            System.out.println(time[0] + " " + time[1]);
        }

        int answer = 0;
        int endTime = 0;

        for (int i = 0; i < n; i++) {
            if (endTime <= times[i][0]) { // 시작 시간이 이전 회의의 끝나느 시간보다 크거나 같으면 갱신
                endTime = times[i][1];
                answer++;
            }
        }

        System.out.println(answer);
    }
}

한 블로그에서 이 문제를 풀 때 그려야 할 활동 시간들의 길이에 대한 그림을 제시해주었는데, 이것을 이해하면 문제를 쉽게 풀 수 있다. 이 문제는 활동 선택 문제라고 한다.

활동 선택 문제(Activity Selection Problem): 여러 활동이 있고, 작업 큐가 하나일 때, 최대한 많은 활동을 선택하는 것. 가장 먼저 끝나는 문제를 선택하고, 종료된 시간에 시작할 수 있는 가장 빠른 작업을 선택한다.

정렬하면 아래처럼 배열이 바뀌게 된다.

---

잃어버린 괄호

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(scanner.nextLine(), "-");

        int answer = Integer.MAX_VALUE;

        while(st.hasMoreTokens()) {
            int temp = 0;
            StringTokenizer tempSt = new StringTokenizer(st.nextToken(), "+");
            while (tempSt.hasMoreTokens()) {
                temp += Integer.parseInt(tempSt.nextToken());
            }

            if (answer == Integer.MAX_VALUE) {
                answer = temp;
            } else {
                answer -= temp;
            }
        }

        System.out.println(answer);
    }

}

“-”를 기준으로 먼저 자르고, “+”를 기준으로 잘라 숫자들을 더해서 answer에 더해준다. “-”가 없는 경우도 찾아내기 위해 초기값을 Integer.MAX_VALUE로 해주고, 처음에만 더해주고 이후엔 뺄셈을 한다.

---

동전 0

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

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

        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        int answer = 0;
        while (k != 0) {
            if (coins[--n] <= k) {
                answer += k/coins[n];
                k = k%coins[n];
            }
        }

        System.out.println(answer);
    }
}

거스름돈 문제와 비슷한데, 가장 큰 수의 동전부터 k를 나누며 나아간다. 너무 간단한 문제라 설명은 생략..