그리디 알고리즘이란
- 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서
‘가장 큰 순서대로’,‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다.- 이에 따라 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄서 출제된다.
문제가 주는 힌트를 잘 살펴보자.
직접적으로 설명을 안하더라도, 가장 큰 순서대로, 가장 작은 순서대로 등의 기준을 주는지 살펴보자.
그리디 알고리즘의 정당성
- 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서
큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. - 만약 동전 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우에는 그리디 알고리즘으로 해결 할 수 없으며, 다이나믹 프로그래밍으로 해결할 수 있다.
그리디 알고리즘 문제는 그리디 알고리즘을 사용하면 최적해가 나올 수 있는 문제이어야 한다.
그리디 알고리즘 파악하기
- 어떤 코테 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해보자.
- 탐욕적인 해결법이 없다면, 동적 프로그래밍이나 그래프 알고리즘으로 문제를 해결할 수 있는지 고민하자.
1️⃣ 거스름돈
[그리디 알고리즘의 정당성 확인]
1. 그리디 알고리즘을 사용하면 최적해를 구할 수 있는가? ← O
2. 값들이 서로 영향을 주지 않는가? ← O
핵심 풀이
타로가 1000원을 지불하는데 이 때 물건 값을 제하면, 거스름돈을 받을 돈이 나오게 된다.
이 때 가장 적은 개수의 잔돈을 구하는데, 그리디 알고리즘을 사용할 수 있다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int inputNum = Integer.parseInt(br.readLine());
int n = 1000 - inputNum;
int cnt = 0;
int[] yens = {500, 100, 50, 10, 5, 1};
for (int i = 0; i < yens.length; i++) {
int coin = yens[i];
cnt += n / coin;
n %= coin;
}
System.out.print(cnt);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}2️⃣ 큰 수의 법칙
[그리디 알고리즘의 정당성 확인]
1. 그리디 알고리즘을 사용하면 최적해를 구할 수 있는가? ← O
2. 값들이 서로 영향을 주지 않는가? ← O
핵심 풀이
주어진 조건에서 가장 큰 수를 만들어야 한다.
그리고 이는 당연하게 주어진 숫자 중 가장 큰 수를 많이 더하는게 유리하다.
소스코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int result = 0;
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int maxNum = arr[n - 1];
int secMaxNum = arr[n - 2];
int maxTryCnt = m - (m / k);
int secTryCnt = m - maxTryCnt;
result += maxNum * maxTryCnt;
result += secMaxNum * secTryCnt;
bw.write(result+"\n");
br.close();
bw.close();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
3️⃣ 숫자 카드 게임
[그리디 알고리즘의 정당성 확인]
1. 그리디 알고리즘을 사용하면 최적해를 구할 수 있는가? ← O
2. 값들이 서로 영향을 주지 않는가? ← O
핵심 풀이
굳이 배열에 저장할 필요 없이, 각 행마다 매번 가장 최소 숫자를 비교 해주어 값을 저장 하면 된다.
소스코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 행
int m = Integer.parseInt(st.nextToken()); // 열
int minNum = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
minNum = 10001;
for (int j = 0; j < m; j++) {
minNum = Math.min(minNum, Integer.parseInt(st.nextToken()));
}
}
bw.write(minNum+"\n");
br.close();
bw.close();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
4️⃣ 1이 될 때까지
[그리디 알고리즘의 정당성 확인]
1. 그리디 알고리즘을 사용하면 최적해를 구할 수 있는가? ← O
2. 값들이 서로 영향을 주지 않는가? ← O
핵심 풀이
최소 횟수를 위해서는 2번 N을 K로 나누는 횟수가 많을 수록 유리하다.
그렇기에 N을 K로 최대한 나눌 수 있게 지원한다.
소스코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 수
int k = Integer.parseInt(st.nextToken()); // 나누는 수
int cnt = 0;
while (true) {
if (n < k) break;
if (n % k != 0) {
n -= 1;
cnt += 1;
} else {
n /= k;
cnt += 1;
}
}
cnt += (n - 1);
bw.write(cnt+"\n");
br.close();
bw.close();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
5️⃣ 동전 0
[그리디 알고리즘의 정당성 확인]
1. 그리디 알고리즘을 사용하면 최적해를 구할 수 있는가? ← O
2. 값들이 서로 영향을 주지 않는가? ← O
핵심 풀이
동전의 가치가 오름차순으로 주어지기 때문에 이를 맨 뒤 인덱스부터 사용하면 내림차순과 마찬가지이다.
동전 개수의 최솟값을 구하기 위해서는 가장 큰 수들로 나눠야 한다.
소스코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken()); // 개수
int k = Integer.parseInt(st.nextToken()); // 주어진 원
int cnt = 0;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
for (int i = 1; i <= n; i++) {
int num = arr[n-i];
if (k < num) {
continue;
}
if (k <= 0) {
break;
}
cnt += k / num;
k %= num;
}
bw.write(cnt+"\n");
br.close();
bw.close();
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
Hello, World! \n