Java에서 구현하는 그리디 알고리즘: 이해와 실제 사례 분석

그리디 알고리즘은 매 순간 최적의 해를 선택하여, 전체에서의 최적해를 도출하는 방식입니다. 이는 지역적으로 최적의 선택을 함으로써 전역적으로도 최적의 결과를 얻을 수 있다는 가정 하에 작동합니다. 이러한 접근 방식은 특정 문제에서 매우 효율적인 해결책을 제공할 수 있으며, Java는 이러한 알고리즘을 구현하기에 충분한 기능과 유연성을 제공합니다. 본문에서는 Java를 활용한 그리디 알고리즘의 구현 방법과, 동전 교환 문제와 작업 스케줄링 문제라는 두 가지 실제 사례를 통해 그리디 알고리즘의 적용 방법을 소개합니다.

• 동전 교환 문제 (Coin Change Problem)

동전 교환 문제는 주어진 동전들을 사용하여 특정 금액을 만드는 데 필요한 최소한의 동전 수를 찾는 문제입니다. 이 문제를 그리디 알고리즘으로 해결하기 위해서는 동전의 단위가 서로 배수 관계에 있을 때 가장 효율적입니다.

 

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins); // 동전을 내림차순 정렬
    int coinCount = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            coinCount++;
        }
    }
    return coinCount;
}

 

 

이 알고리즘은 가장 큰 단위의 동전부터 시작하여, 주어진 금액을 만들 수 있을 때까지 해당 동전을 사용합니다. 이 방식은 각 단계에서 최적의 선택을 하여 문제를 해결합니다.

• 작업 스케줄링 문제 (Job Scheduling Problem)

작업 스케줄링 문제는 각 작업에 대해 시작 시간, 종료 시간, 그리고 이익이 주어졌을 때, 최대 이익을 얻을 수 있는 작업의 조합을 찾는 문제입니다. 그리디 알고리즘을 적용하여 이 문제를 해결하기 위해 작업을 종료 시간 기준으로 정렬한 후, 가장 먼저 끝나는 작업부터 선택하는 방법을 사용합니다.

 

class Job {
    int start, finish, profit;
    
    Job(int start, int finish, int profit) {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
}

public int scheduleJob(Job[] jobs) {
    Arrays.sort(jobs, Comparator.comparingInt(a -> a.finish)); // 종료 시간 기준으로 정렬
    int n = jobs.length;
    int[] table = new int[n];
    table[0] = jobs[0].profit;

    for (int i = 1; i < n; i++) {
        int inclProfit = jobs[i].profit;
        for (int j = i - 1; j >= 0; j--) {
            if (jobs[j].finish <= jobs[i].start) {
                inclProfit += table[j];
                break;
            }
        }
        table[i] = Math.max(inclProfit, table[i - 1]);
    }
    return table[n - 1];
}

 

이 알고리즘은 각 작업을 종료 시간에 따라 정렬하고, 각 작업을 추가할 때 현재까지의 최대 이익을 업데이트하는 방식으로 작동합니다. 각 단계에서 최적의 선택을 하는 것이 전체 문제의 최적해를 보장하는 경우에 그리디 알고리즘은 매우 효과적입니다.

그리디 알고리즘은 문제를 해결하는 데 있어 직관적이고 단순한 접근 방식을 제공합니다. 그러나 모든 문제에 적용 가능한 만능 키는 아니며, 알고리즘이 적용되는 문제의 구조를 이해하고 적절히 선택하여 사용해야 합니다. Java를 통한 그리디 알고리즘 구현은 알고리즘의 기본 원리를 이해하고 실제 문제 해결 능력을 키우는 데 큰 도움이 될 것입니다.