Greedy 탐욕법
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
- 정당성 분석이 중요하다.
- 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.
- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
- 그러나 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 추론할 수 있어야 풀리도록 출제된다.
거스름돈 문제 예시
손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수 구하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Main {
public static void main(String[] args) {
int n = 1260;
int cnt = 0;
int[] coinTypes = {500, 100, 50, 10};
for (int i = 0; i < 4; i++) {
cnt += n / coinTypes[i];
n %= coinTypes[i];
}
System.out.println(cnt);
}
}
|
큰 수의 법칙 문제 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1 = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st1.nextToken());
int m = Integer.parseInt(st1.nextToken());
int k = Integer.parseInt(st1.nextToken());
int[] arr = new int[n];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st2.nextToken());
}
// 최댓값 구하기 stream
// int max1 = Arrays.stream(arr).max().getAsInt();
// 궁금해서 찾아본 배열 역순 정렬 stream
// int[] sortedArr = Arrays.stream(arr).boxed()
// .sorted(Collections.reverseOrder())
// .mapToInt(Integer::intValue)
// .toArray();
// int max1 = sortedArr[0];
// int max2 = sortedArr[1];
Arrays.sort(arr);
int max1 = arr[arr.length-1];
int max2 = arr[arr.length-2];
int result = 0;
result += (m / (k+1) * k) * max1;
result += (m - (m / (k+1) * k)) * max2;
System.out.println(result);
}
|
숫자 카드 게임 문제 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st1 = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st1.nextToken());
int m = Integer.parseInt(st1.nextToken());
int[] minInEachMArr = new int[n];
StringTokenizer st2;
for (int i = 0; i < n; i++) {
st2 = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
int nextNum = Integer.parseInt(st2.nextToken());
if (j == 0) {
minInEachMArr[i] = nextNum;
} else if (nextNum < minInEachMArr[i]){
minInEachMArr[i] = nextNum;
}
}
}
int maxInArr = Arrays.stream(minInEachMArr).max().getAsInt();
System.out.println(maxInArr);
}
|
1이 될 때까지 문제 예시
- input
-
output
- (1) N에서 1을 뺀다 (2) N을 K로 나눈다 두 과정을 선택해서 수행했을 때 N이 1이 될 때까지의 수행 횟수 최솟값
- 해결방법: 최대한 많이 나누기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.inputStream());
// 공백을 기준으로 구분하여 입력 받기
int n = sc.nextInt();
int k = sc.nextInt();
int result = 0;
while(true) {
// n이 k로 나누어지는 수가 될 때까지 빼기
int target = (n / k) * k; // k로 나누어 떨어지는 가장 가까운 수를 찾는다.
result += (n - target); // (1) 실행 횟수를 result에 더해준다.
n = target;
if (n < k) break; // 더 이상 나눌 수 없을 때 반복문을 탈출한다.
result += 1; // (2) 실행 횟수를 result에 더해준다.
n /= k;
}
// 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1) * k;
System.out.println(result);
}
}
|
reference
[이것이 코딩 테스트다 with Python] 12강 그리디 알고리즘 개요
