그리디 관련 문제를 풀다가 이상한 점을 발견했다.
오름차순 내림차순에 따라 정답이 맞고 틀렸기 때문이다.
https://www.acmicpc.net/problem/13904
풀이 방법
주어진 과제들을 순서대로 정렬한 뒤, 각 마감일까지의 날짜 중에서 가장 높은 점수를 얻을 수 있는 과제를 선택하는 방식으로 탐욕적으로 접근하였다.
❌틀린 코드
let input = require("fs").readFileSync("예제.txt").toString().split("\n");
const N = parseInt(input.shift());
const homework = input.map((str) => str.split(" ").map(Number));
homework.sort((a, b) => a[0] - b[0]);
const visited = new Array(N).fill(false);
let total = 0;
for (let day = homework[N - 1][0]; day > 0; day--) {
let maxScore = 0;
let maxIndex = -1;
for (let i = 0; i < N; i++) {
if (!visited[i] && homework[i][0] >= day && homework[i][1] > maxScore) {
maxScore = homework[i][1];
maxIndex = i;
}
}
if (maxIndex !== -1) {
total += homework[maxIndex][1];
visited[maxIndex] = true;
}
}
console.log(total);
마감일이 빠른 오름차순으로 정렬하여 마지막 날을 homework[N-1][0]으로 하였고
마감일이 빠른 과제를 우선적으로 고려하며, 마감일이 빠른 순서대로 과제를 처리한다.
ㄴ 각 날짜에 최대 한 번의 과제만 선택할 수 있음.
이 코드는 각 날짜마다 최대 점수를 얻을 수 있는 과제를 선택하려고 하지만, 이는 최적의 해를 보장하지는 않음
[반례]
입력
6
2 100
2 50
2 60
1 20
3 80
4 30
출력 : 270
- 첫째 날에는 100점인 과제를 선택합니다.
- 둘째 날에는 60점인 과제를 선택합니다.
- 셋째 날에는 80점인 과제를 선택합니다.
- 넷째 날에는 30점인 과제를 선택합니다.
-> 총 점수는 270이 되어야 하는데
내 잘못짠 코드는 출력이 240이 된다.
- 첫째 날에는 100점인 과제를 선택합니다.
- 둘째 날에는 60점인 과제를 선택합니다.
- 셋째 날에는 80점인 과제를 선택합니다.
⭕수정 코드
let input = require("fs").readFileSync("예제.txt").toString().split("\n");
const N = parseInt(input.shift());
const homework = input.map((str) => str.split(" ").map(Number));
homework.sort((a, b) => b[0] - a[0]);
const visited = new Array(N).fill(false);
let total = 0;
for (let day = homework[0][0]; day > 0; day--) {
let maxScore = 0;
let maxIndex = -1;
for (let i = 0; i < N; i++) {
if (!visited[i] && homework[i][0] >= day && homework[i][1] > maxScore) {
maxScore = homework[i][1];
maxIndex = i;
}
}
if (maxIndex !== -1) {
total += homework[maxIndex][1];
visited[maxIndex] = true;
}
}
console.log(total);
과제를 마감일이 늦은 순서대로 정렬한다.
마감일이 늦은 순서대로 과제를 처리한다.
같은 마감일에 있는 과제라면 더 높은 점수를 가진 과제가 선택되는 경향이 있다.
[탐욕 알고리즘 힌트]
- 문제 설명: 문제가 각 단계에서의 최적해가 전체적인 최적해를 보장한다는 힌트를 제공하는 경우가 있습니다. 이는 탐욕 알고리즘의 특징 중 하나입니다.
- 문제 유형: 일부 문제는 자연스럽게 탐욕 알고리즘을 적용하기에 적합한 형태를 가지고 있습니다. 예를 들어, 거스름돈 문제나 활동 선택 문제 등은 탐욕 알고리즘이 자주 사용되는 예시입니다.
- 최적 부분 구조 (Optimal Substructure): 문제가 작은 부분 문제들로 분할되어 있고, 각 부분 문제의 최적해가 전체 문제의 최적해로 이어진다는 특성을 가질 때, 탐욕 알고리즘이 적용될 수 있습니다.
- 특정 조건과 제약 조건: 문제에 특정한 제약 조건이 있거나 입력의 특성이 주어진 경우에 탐욕 알고리즘이 효과적일 수 있습니다.
[탐욕 알고리즘 예시]
- 최소 거스름돈 문제 (Greedy Change Making Problem): 이 문제에서는 거스름돈을 주는데 필요한 동전의 수를 최소화해야 합니다. 가장 큰 가치의 동전부터 차례대로 사용하여 거스름돈을 주는 방식입니다.
- 최소 신장 트리 (Minimum Spanning Tree): 그래프에서 모든 노드를 연결하면서 가중치의 합이 최소가 되는 트리를 찾습니다. 프림 알고리즘과 크루스칼 알고리즘이 탐욕 알고리즘의 대표적인 예시입니다.
- 최단 경로 문제 (Shortest Path Problem): 출발점에서 도착점까지의 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘이 이에 속합니다.
- 작업 스케줄링 문제 (Job Scheduling Problem): 주어진 작업을 최적의 순서로 처리하는 문제입니다. 가장 일찍 끝나는 작업부터 처리하는 방식이 있습니다.
- Fractional Knapsack Problem: 배낭에 담을 수 있는 무게가 제한되어 있을 때, 각 물건의 일부분을 담을 수 있는 경우의 배낭 문제입니다.
- 활동 선택 문제 (Activity Selection Problem): 한 자원이 여러 활동에 동시에 참여할 수 없을 때, 최대한 많은 활동을 선택하는 문제입니다. 종종 각 활동의 종료 시간이 중요한 요소가 됩니다.
BOJ 13904 과제 탐욕 알고리즘인 이유
각 과제에는 점수와 마감일이 주어지고, 특정 기간 내에 최대 점수를 얻어야 한다는 등의 조건이 주어지면, 이는 탐욕 알고리즘을 고려할 수 있는 문제 특성이다.
'알고리즘' 카테고리의 다른 글
[알고리즘] 백준 11286 절대값 힙 node.js (heap) (0) | 2024.06.26 |
---|---|
[알고리즘]프로그래머스 - N으로 표현 <동적계획법(DP)> (0) | 2024.03.04 |
[알고리즘] 탐욕법(Greedy) (0) | 2024.02.06 |
[알고리즘] 완전탐색 예제 # 1 단순 브루트포스 (0) | 2024.02.05 |
[알고리즘] 완전 탐색 (0) | 2024.02.02 |