[알고리즘] 그리디(Greedy)

정의

 

미래를 고려하지 않고 현재 상황에서의 최적의 선택을 하는 방법

 

특징

• 현재에 집중한 선택
• 단순하고 빠름
• 국소 최적  : 각 단계에서의 선택이 국소적으로 최선이 되는 것을 목표
• 정렬 기법이 함께 사용되는 경우가 많다 : 큰/작은 경우 순, 긴/짧은 경우 순 등 극단적으로 문제에 접근하기 때문

 

코딩테스트 빈출 유형 & 풀이 방법 예시

1. 동전 거스름돈 문제 : 500,100,50,10원을 사용하여  거스름돈 n원을  최소 개수의 동전으로 거슬러줘야 하는 경우 
   ▶ 가장 큰 단위의 동전을 우선적으로 선택하는 방식
2. 회의실 배정 문제  : 여러 회의가 있을 때, 회의가 겹치지 않도록 하면서 가장 많은 회의를 배정하는 경우
   ▶ 끝나는 시간이 가장 빠른 회의부터 선택하는 방식

 

유형 이해 코드

import java.util.Scanner;
//문제 : 760원을 500,100,50,10원의 동전을 이용하여 최소 개수로 거슬러줘야한다.

import java.util.Scanner;

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

        // 동전의 종류를 배열로 정의 (큰 단위부터 작은 단위로)
        int[] coins = {500, 100, 50, 10};

        // 사용자에게 거슬러 줘야 할 금액을 입력받음
        System.out.print("거슬러 줄 금액을 입력하세요: ");
        int amount = scanner.nextInt();

        // 동전 개수를 셀 변수
        int coinCount = 0;

        // 거스름돈을 계산
        for (int coin : coins) {
            if (amount >= coin) {
                int count = amount / coin; // 해당 동전으로 거슬러 줄 수 있는 개수 계산
                coinCount += count;
                amount %= coin; // 남은 금액 업데이트
                System.out.println(coin + "원 동전 " + count + "개 사용");
            }
        }

        // 총 사용한 동전 개수 출력
        System.out.println("총 사용한 동전 개수: " + coinCount);
    }
}

 

주의사항

• 정당성 분석 : 코딩 테스트에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이론을 추록해야 풀리도록 출제되지만, 일반적인 상황에서의 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
  → 단계단계 최선의 선택을 반복해도 최종적으로 최적의 해가 나오는지 검토할 것!