탐욕법(Greedy Algorithm - 동전 교체, 체육복 대여 연습문제)

Greedy Algorithm : 

"매 선택에서 현재 당장 최적인 답"을 선택해 적합한 결과를 도출하는 알고리즘.

백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 한것으로 검증 완료한다.

 

당장의 선택에서 최적인 값을 구하기 때문에 속도가 매우 빠른 장점이 있지만,

전체로 봤을 때 최적값이 아닐 경우가 있다는 단점이 있다.

 

 

따라서 2가지 조건을 만족시키는 경우에 사용하는것이 좋다.

1. Greedy Choice Propety(탐욕 선택 속성) : 이전의 선택이 이후에 영향을 주지 않음.

2. Optimal Substructure(최적 부분 구조) : 부분 문제의 최적결과가 전체에도 그대로 적용.

   (Dynamic Programming과 연관이 있음.)

 

 

 

https://www.youtube.com/watch?v=CxBYY7XTQvI 

 

---

 

Greedy 예시) 동전 교체 예제

 

가장 적은 갯수로 710원을 만들기

 

- 매개변수 : [10, 100, 500]

- 목표 : 710원 만들기

 

500 X 1개 -> 잔돈 210원 ( 가장 큰 동전을 이용하여 남은액수를 최대한 줄인다.)

100 X 2개 -> 잔돈 10원

  10 X 1개 -> 잔돈 0원

 

정답 : 4개 (Local Minimun)

 

Greedy 예시의 오류)

 

- 매개변수 : [10, 30, 40, 50] 

- 목표 : 70원 만들기

 

50 X 1개 -> 20원

10 X 2개 -> 0원

 

정답 : 3개

 

하지만, 30 X 1 과 40 X 1 을 이용하면 2개로 정답추출이 가능하다. 

정확한 풀이를 위해서는 Dynamic Programming에 의한 풀이가 필요하다. 

 

핵심은 매개변수로 사용되는 변수들 중 큰 단위가 항상 작은 단위의 배수일 때 Greedy 알고리즘을 사용하는 경우에 대한 정당성이 확보된다.

---

 

Greedy 예시) 체육복 대여 예제(프로그래머스)

https://programmers.co.kr/learn/courses/30/parts/12244

프로그래머스

 

1. 여벌을 최대한 빌려주기

- 여벌의 체육복을 최대한 빌려준 뒤 체육복을 가진 학생수를 구하자

 

Solution

1. Set의 HashSet이용

HashSet : Set 인터페이스에서 구현하는 클래스로 순서가 유지되지 않고, null허용, 중복을 허용하지 않음.

- HashSet에 배열을 넣는다.

- HashSet.contains를 이용하여 중복 검출 및 HastSet.remove를 이용하여 중복값 제거.

public int solution2(int n, int[] lost, int[] reserve) {
        int answer = 0;
        Set<Integer> reservset = new HashSet<>();
        Set<Integer> lostset = new HashSet<>();

            for(int resv : reserve) {//배열을 HashSet에 넣기
                reservset.add(resv);
            }

            for(int los : lost) {//도난된 사람 중 여분이 있는 학생만 HashSet에 넣기
                if(reservset.contains(los)) {
                    reservset.remove(los);
                } else {
                    lostset.add(los);
                }
            }

            for(int i : reservset) {//여분 학생이 빌려줄 수 있는 사람 찾기
                if(lostset.contains(i-1)) {
                    lostset.remove(i-1);
                } else if(lostset.contains(i+1)) {
                    lostset.remove(i+1);
                }
            }
        return n-lostset.size();
    }

 

배열을 활용해서 푸는 방법이 있는데,

임의의 배열인 학생번호 배열을 생성해서 체육복이 있으면 +1, 도난당했으면 -1로 배열에 초기화 한 후

순서대로 앞뒤에 -1이 있으면 0으로 만들고 +1을 0으로 변경 후 0 이상인 학생들만 추려내는 방식의 풀이법이 있다.

 

이 풀이법이 아마 알고리즘에 더 적합한 풀이법이라 생각된다.