그리디 알고리즘 (Greedy)

알고리즘 파트는 책 "이것이 취업을 위한 코딩테스트다 -나동빈" 책을 기반으로 제가 이해한부분을 정리하기 위해 작성되었습니다 .

그리디 알고리즘이란? 

그리디 알고리즘은 탐욕법으로 현재 상황에서 좋은 것만 고르는 방법을 의미한다. 매 순간에서 최선의 방법을 선택하며 나중의 영향에 대해선 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로 혹은 가장 작은 순서대로 와 같은 기준을 제시해준다. 대체로 정렬을 통해 이 기준을 만족시킬 수 있으므로 그리디 문제는 정렬과 짝을 이뤄 출제된다. 

 

백준 알고리즘에서 5585번 거스름돈 문제를 한번 보면 더 잘 이해가 된다.

그리디 알고리즘 문제의 대표적인 유형인 거스름돈 문제다. 이때, 잔돈의 종류가 6개로 제시되어져 있고 최소의 잔돈의 개수를 구하면 된다.

 

import java.util.*;
public class B3085 {
    public static void main(String[]args) {
        Scanner sc = new Scanner(System.in);
        int n = 1000 - sc.nextInt();
        int count = 0;
        int[] coinArr = {500, 100, 50, 10, 5, 1};
        for (int i = 0 ;i <coinArr.length ;i++) {
            count += n/coinArr[i];
            n %= coinArr[i];
        }
        System.out.println(count);
    }
}

 

위의 코드를 보면 보이겠지만 반복문을 잔돈의 종류만큼 반복했다. 이 말은 즉, 화폐의 종류가 k개라면, 위 코드의 시간복잡도는 O(K)라는 것이다. 그래서 거스름돈에 상관없이 동전의 종류만 시간복잡도에 영향을 주는 것을 알 수 있다.

 

그리디 알고리즘의 정당성

그러나 대부분의 알고리즘 문제에선 그리디 알고리즘을 이용해선 답을 찾기 힘들다. 그래서 그리디 알고리즘으로 해결했을 때는, 그 알고리즘이 정당한지를 검토해야 한다. 위의 거스름돈 문제가 그리디 알고리즘으로 풀어도 정당한 이유는 동전의 큰 단위가 작은 단위의 배수이므로 작은 단위들을 종합해 다른 해가 나올 수 없기 때문이다.