[Coding Test Grammar] 탐욕법 (Java)

"탐욕법"(Greedy Algorithm)은

현재 시점에서 가장 최선의 선택을 반복적으로 수행하여 최종적인 최적해를 구하는 알고리즘 설계 기법입니다.

 

탐욕법의 특징

• 단계적 선택 : 매 단계에서 가장 최선의 선택을 함.
• 직관적 : 탐욕법은 문제를 해결하는 방법이 비교적 단순하고 직관적입니다.

탐욕법이 적용되기 위해서는 "탐욕적 선택 속성"과 "최적 부분 구조"를 만족해야 합니다.

Tip.
Arrys.sort(Object);
정렬하는 것을 추천

 

예제 문제: 동전 거스름돈 문제

문제 설명:

• N원이 있을 때, 500원, 100원, 50원, 10원의 동전을 사용하여 N원을 최소한의 동전 개수로 거슬러주는 프로그램을 작성하라.

탐욕법 접근:

• 가장 큰 동전부터 가능한 한 많이 사용
• 예를 들어, N = 1260원이 있다면, 500원짜리 동전을 최대한 사용하고, 남은 금액에 대해 다시 동일한 방법을 적용.

탐욕법을 사용한 자바 코드

public class GreedyExample {
    public static void main(String[] args) {
        int n = 1260;
        int count = 0; 
        
        int[] coins = {500, 100, 50, 10}; 

        for (int coin : coins) {
            count += n / coin; 
            n %= coin; 
        }

        System.out.println("최소 동전 개수: " + count);
    }
}

 

코드 설명

1. n에 거슬러줄 금액.
2. coins 배열에 사용할 동전의 종류를 내림차순으로 나열.
3. 반복문을 통해 각 동전으로 최대한 많이 걸러줌.

• n / coin : 현재 동전으로 거슬러줄 수 있는 최대 개수를 의미
• n %= coin : 해당 동전을 거슬러주고 남은 금액을 계산

1. 남은 금액이 0이 될 때까지 이 과정을 반복하면, 최종적으로 필요한 동전의 최소 개수를 구함.

결과

• 1260원을 거슬러줄 때, 500원 2개, 100원 2개, 50원 1개, 10원 1개가 필요하며, 총 6개의 동전이 필요