9. 그리디(greedy) 알고리즘

p. 196~197(10일차)

강의: 06-1

---

1. 그리디 *항상 최선의 수를 선택 => 최선의 해를 찾기

 

- 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정

 

 ✔ 과정

1)  해 선택: 현재 상태에서 가장 최선이라고 생각하는 해를 선택

2)  적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

3)  해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사

     * 3)에서 전체 문제를 해결하지 못한다면 1)로 돌아가서 반복한다.

---

✔ 백준 11047번  - 동전 개수의 최솟값 구하기 *대표적인 그리디알고리즘 문제

 

✔ 문제 분석

* K원을 만드는 데 필요한 동전 개수의 최솟값을 출력

- 1번째 줄에 'N: 동전의 총 종류'과 'K: 만들고자 하는 가격의 합'가 주어짐

- 2번째 줄에: 'A: N개의 줄에 동전의 가격'이 오름차순으로 주어짐

 

=> 그리디 알고리즘 사용 : 동전의 개수가 적으면 적을 수록 좋기 때문에

  즉, 최대한 큰 금액인 동전으로 구성

 

 

 ✔ 문제 풀기

* 주의사항: 잘 따지지 않으면 반례가 생김 ! => 최적의 해가 보장되는 알고리즘이 아님

 ✔ 코드 작성

1. 화면을 통해 데이터를 받아야 함 (Scanner, nextInt())

2. 1에서 받은 데이터를 넣을 '동전개수, 목표금액, 동전배열' 객체 생성

    몫을 저장할 count(동전수) 객체 생성 (int 이름 = 0;)

3. 큰 동전부터 순회하며 K와 값을 비교할 구현부 작성 (for, if)

    count(동전 수) += K/현재 동전 *몫을 동전수에 저장, 4200/1000 = 4.2 (4저장)

    K(목표금액) = 목표금액%현재동전  *1.에서 나누고 남은 값, 4200-4000 = 200(K에 저장) 

4. count(동전수) 출력 (sout)

import java.util.*;

public class Main {
public static void main(String[] args) {

//값을 받고 동전수, 목표금액, 동전배열 각 객체에 값을 넣음
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = new int[N]; // 동전의 종류 개수
for(int i = 0; i<N; i++) { //동전 수 만큼 증가하는 숫자들 반복
A[i] = sc.nextInt(); // 증가한 수를 A배열에 삽입
}

// 그리드 알고리즘 사용, 큰 동전 먼저 사용하기
int count = 0; // 동전수 추가할 객체 생성
for(int i = N -1 ; i >=0; i--) { //N-1(배열 중 가장 큰 동전) ~ 0까지 감소
if(A[i] <= K) {
count += (K/A[i]); // count에 사용한 동전 수 저장
K = K % A[i] ; // 남은 목표값을 K에 저장
}
}
System.out.println(count);

}
}