[개념 정리] 그리디

문제를 해결할때, 각 단계의 최선의 선택을 하려면 어떻게 할까요?

 

 

이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다.

 

그리디

그리디 알고리즘은 문제를 해결할 때 각 단계에서 최선이라고 생각되는 선택을 하는 방식으로, 이 선택들이 모여 전체 문제에 대한 최적의 해를 도출해내는 알고리즘 입니다.

 

언제 그리디를 사용해야 할까요?

 

무식하게 완전탐색 → 조건 처리 하면 될거같은데? 백트래킹  → 그래도 시간초과 날꺼 같아? DP → 배열에 다 못담을거 같은데.. 메모리 초과날꺼 같아? 그리디(정렬, 우선순위 큐)

 

그리디는 제일 마지막 단계에서 생각을 합니다.

 

그리디하게 풀기 위해선 3단계를 거쳐야 합니다.

1. 최고의 선택을 할 수 있는 하나의 명제를 생각합니다.
2. 명제를 기반으로 테스트 코드가 되는지 판단하고, 구현한 후 테스트 코드 검증을 합니다.
3. 반례가 존재하는 경우 명제를 다시 구축하고 2번 과정을 반복합니다.

 

그리디를 사용하기 위해선 어떠한 조건이 충족되어야 할까요?

 

그리디 조건

그리디를 사용하기 위해선 최적 부분 구조, 탐욕 선택 속성의 조건이 충족되어야 합니다.

 

최적 부분 구조가 뭘까요?

 

최적 부분 구조는 문제를 작은 부분 문제로 나눌 수 있고, 그 작은 부분들의 문제들의 최적해가 모여 전체 문제의 최적 해를 이룰 수 있는 구조를 의미합니다.

 

탐욕 선택 속성이 뭘까요?

 

각 단계에서의 최적 선택이 전체 문제에 대해서도 최적의 해를 보장한다는 것을 의미합니다.

 

해당 명제가 탐욕 선택 속성이 충족됨을 알기 위해선 증명을 해봐야 합니다.

하지만, 코딩테스트에선 증명하는 것이 시간상 어렵기 때문에 아래와 같은 순서로 문제를 접근합니다.

명제 → 코드 구현 → 각 상태값의 가장 최적의 로직 → 해당 명제가 틀린 경우, 명제를 빠르게 변경해서 다시 풀기

 

보통 그리디는 정렬, 우선순위 큐를 사용하는 2가지 방법이 주로 나옵니다.

해당 방법을 먼저 숙달하고, 이 방법이 안되는 경우 각 상태에서 최선이 되는 로직을 생각해서 풉니다.

 

 

그리디를 사용하는 사용하는 간단한 문제를 풀면서 적용해보겠습니다.

 

문제 : 설탕 배달

https://www.acmicpc.net/problem/2839

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

적은 개수의 봉지로 배달을 하기 위해서 5kg과 3kg중 최대한 5kg으로 담을 수 있도록 선택해야 합니다.

 

1. 가장 큰 봉지 크기인 5kg 선택하고, 부분 문제로 나눕니다.
2. 선택한 5kg의 봉지로 담을 수 있을만큼 담고, 남은 무게를 다음 단계로 넘깁니다.
3. 남아 있는 무게는 1kg ~ 4kg까지 존재할 수 있습니다. 각 남은 무게에서 5kg을 빼서 3kg의 배수로 만들 수 있는지 확인합니다.
4. 1kg이 남은경우 5kg + 1kg = 6kg, 2kg이 남은 경우 5kg + 5kg + 2kg = 12kg, 3kg이 남은 경우 3kg, 4kg이 남은 경우 5kg + 4kg = 9kg으로 만들어 준 뒤, 3kg 봉지에 넣어줍니다.

11kg을 예시로 들자면, 11kg은 5kg 2봉지에 담길 수 있습니다. 그러고 나면 1kg이 남게 됩니다.

5kg에 담은 설탕을 빼서 6kg으로 만들어 줍니다. 6kg은 다시 3kg 2봉지에 담을 수 있습니다. 따라서, 총 4봉지가 정답이 됩니다.

 

풀이 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        if(n == 3) {
            System.out.println(1);
            return;
        }

        if(n == 4 || n == 7) {
            System.out.println(-1);
            return;
        }

        if(n % 5 == 0) {
            System.out.println(n / 5);
        }else {
            int cnt = n / 5;
            if(n % 5 == 3) {
                cnt++;
                System.out.println(cnt);
            }else if(n % 5 == 2) {
                cnt+=2;
                System.out.println(cnt);
            } else {
                cnt--;
                cnt += (5 + n % 5) / 3;
                System.out.println(cnt);
            }
        }
    }
}

 

 

 

정리

• 무식하게 완전탐색 → 조건 처리 하면 될거같은데? 백트래킹  → 그래도 시간초과 날꺼 같아? DP → 배열에 다 못담을거 같은데.. 메모리 초과날꺼 같아? 그리디(정렬, 우선순위 큐)