[Java] 알고리즘 Day3

그리디 알고리즘(Greedy)

- 탐욕법

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 매 순간 가장 좋아 보이는 것을 선택하며, 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디에서 중요한 것은

- 창의력 -> 문제를 풀기위한 아이디어를 떠올릴 것 -> 정당한지 검토할 수 있어야할 
- 특정 문제를 만났을 때, 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야함

 

 

그리디 알고리즘 주요 속성

1. 탐욕적 선택 속성 (Greedy Choice Property):

• 각 단계에서 탐욕적으로 선택한 것이 항상 최적이라는 것을 보장합니다.
• 즉, 각 선택 시점에서 지금 당장 최적인 선택을 하며, 그 선택이 최종적으로 최적해로 이어질 수 있어야 합니다.

 

2. 최적 부분 구조 (Optimal Substructure):

• 큰 문제의 최적해가 작은 문제의 최적해를 포함한다는 성질
• 그리디 알고리즘에서는 각 단계에서의 최적 선택이 전체 문제의 최적해를 보장한다.

 

예시 - 거스름돈 문제

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int money = sc.nextInt();
    int cnt = 0;
    int[] coinTypes = {500, 100, 50, 10};

    for (int i = 0; i < 4; i++) {
        int coin = coinTypes[i];
        cnt += money / coin;
        money %= coin;
    }

    System.out.println(cnt);
}