그리디 알고리즘을 쌈싸먹어 보자!
그리디 알고리즘
특징
- 결정해야 할 때 그 순간 제일 좋다고 생각되는 걸 선택하면서 답을 찾는 알고리즘
- 즉 그 순간엔 최적이라도, 최종적으로는 답이 최적이 아닐 수 있다
유형
- 거스름돈 문제
- 동전도 지페도 아주 많을 때, N원을 최소 개수의 지폐, 동전을 이용해서 거슬러주려면 어떻게 해야 하는가?
- 가장 큰 액면가를 가진 지폐 / 동전부터 거슬러주자!
- 즉, 지금 순간에 제일 최적인 걸 골라야 할 때 사용하는 알고리즘...! 🤔
문제 예제 (1) : 백준 동전 0
https://www.acmicpc.net/problem/11047
내 풀이
- 가치의 합은 최대인데, 사용해야 하는 동전 개수는 최소
- 즉 K원을 만들기 위해 숫자를 쪼갰을 때 가장 적게 쪼갤 수 있는 기준(배수)를 찾아야 한다.
- 주어진 동전의 가치가 오름차순이니까, 뒤에서부터 내려와야 한다.
- 뒤에서 내려오면서 만약 현재 동전 가치가 K보다 크다면 넘기고, 작다면 쪼개는 과정을 반복하면 될 듯?
// DESCRIBE: 동전 개수 찾기
for (int i = N-1; i >= 0; i--) {
if (array[i] <= K) {
answer += (K/array[i]);
K %= array[i];
}
}
- 옹ㅎㅎ 맞았다
해설
- (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
- 요 조건 덕분에 그리디 알고리즘이 성립하게 된다
- 돈을 1원짜리로 전부 바꾼 다음, 그 다음 동전의 가치가 항상 이전 동전의 배수를 만드는지 확인해서 항상 성립하는지 확인하자.
문제 예제 (2) : 백준 회의실 배정
https://www.acmicpc.net/problem/1931
내 풀이
- 이 문제가 그리디 유형인걸 어떻게 알 수 있을까?
- N개 중 어떤 것을 선택하느냐에 따라 결과가 달라지는 문제다.
- 즉 일종의 거스름돈 문제인거지..!
- 거스름돈은 최대 액면가를 가진 동전/지폐부터 골랐다면, 이 문제에서는 어떤 회의를 우선적으로 골라야 할까?
- 평범하게 생각해보면 회의 시간이 짧거나, 일찍 시작하는 회의를 고르면 될거다. 하지만 시작 시간을 기준으로 잡으면 안된다. 다음 회의랑 겹칠 수 있으니까!
- (1 4, 3 5, 0 6이 있을 때 시작 시간 기준으로 잡으면 1 4, 0 6이지만 종료 시간을 고려하면 겹치는 회의다)
- 따라서 종료 시간을 기준으로 잡고, 시작 시간이 앞에서 잡은 종료 시간보다 같거나 큰 경우를 우선적으로 고르면 될거다
- 위의 흐름에서, 회의를 선택하는 기준은 (1) 회의 종료 시간이 빠르면서 (2) 전체 회의 시간이 짧은 친구를 우선적으로 골라내야 한다.
- 그럼 어케 풀까?
- 일단 회의 종료 시간을 기준으로 입력 회의들을 오름차순 정렬한다.
- 첫번째 인덱스부터 시작해서, 만약 다음 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 같거나 큰 경우만 카운트한다.
- 이렇게 하면, 만약 시작 시간이 동일하더라도 종료 시간이 더 빠른 친구가 먼저 선택되니까 굳이 회의 전체 시간을 따로 계산해 줄 필요가 없다!
- 테케에서 (5,7) (5,9)가 해당. 시작 시간이 동일하다고 가정했을 때, 종료 시간을 기준으로 오름차순 정렬했으니 자연스럽게 전체 회의 시간이 짧은 (5, 7)이 카운트된다.
// DESCRIBE: 종료 시간 기준으로 오름차순 정렬. 만약 동일하다면 시작 시간 오름차순으로
Arrays.sort(array, (o1, o2) -> {
if(o1[1] == o2[1]) {
return o1[0] - o2[0];
}else {
return o1[1] - o2[1];
}
});
// DESCRIBE: 현재 인덱스의 시작 시간이 이전 인덱스의 종료 시간보다 크거나 같다면 카운트
int prevEndTime = array[0][1];
for (int i = 1; i < N; i++) {
if (array[i][0] >= prevEndTime) {
result += 1;
prevEndTime = array[i][1];
}
}
- 맞았다! (2차원 배열 정렬 연습 좀 해야할듯^^^^)
해설
- 오 회의 시간이 짧은 경우는 아예 기준이 될 수 없구나..!
- 기준 세우고 반례 고민하는 연습을 해야 할 것 같다.
- 나는 풀 때 어? 정렬해두고 보니 회의 시간 짧은건 따로 계산 안해도 되네? 하고 풀었는데, 사실은 아예 고려하면 안되는 대상이었던 것..! 🤔
- 이건 맞은게 아니라 틀렸다고 봐야 할 것 같다. 걍 얻어 걸린거니까... 😇
문제 예제 (3) : 백준 ATM
https://www.acmicpc.net/problem/11399
내 풀이
- 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값 = 누적합이 최소
- 즉 돈을 뽑는데 걸리는 시간이 작은 사람 순으로 고르면 된다.
- ex. 3 1 4 3 2 -> 3 + (3+1) + (3+1+4) + (3+1+4+3) + (3+1+4+3+2) = 39
- ex. 1 2 3 3 4 -> 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 32
- 입력값을 오름차순으로 정렬하고, 이후 누적합을 구하자.
// DESCRIBE: 오름차순 정렬
Arrays.sort(array);
// DESCRIBE: 누적합 구하기
int waitTime = 0;
int totalWaitTime = 0;
for (int i = 0; i<N; i++) {
waitTime += array[i];
totalWaitTime += waitTime;
}
- 맞았다 ^~^
해설
- 오름차순 = 비내림차순으로 정렬! 동일한 접근
- (증명) 오름차순으로 정렬하고 결과값(S)을 구했을 때, 인덱스를 바꿔서 다시 계산(S')해보면 값이 같거나 커지게 된다.
- (증명) S-S' = (i-j)(pj-pi)
- (i-j)가 <= 0 이므로 항상 음수가 된다. 즉 S'는 언제나 S보다 같거나 크다.
- 따라서 오름차순으로 정렬하는게 최적해가 된다.
- 우억 이렇게 증명할 생각은 안하고 그냥 냅다 응 당연히 오름차순이지~ 하고 풀었는데.. 이렇게 풀면 이제 실전에서 테케에 갈려나가는거겠지?! 🔨
- 구상한 풀이를 먼저 증명한 후 구현하는 연습이 필요하다! 그냥 이럴 것 같아~ 하고 풀지 말자!