[알고리즘] 백준 13904 과제 node.js (Greedy)

그리디 관련 문제를 풀다가 이상한 점을 발견했다.

오름차순 내림차순에 따라 정답이 맞고 틀렸기 때문이다.

 

https://www.acmicpc.net/problem/13904

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

1. 첫째 날에는 100점인 과제를 선택합니다.
2. 둘째 날에는 60점인 과제를 선택합니다.
3. 셋째 날에는 80점인 과제를 선택합니다.
4. 넷째 날에는 30점인 과제를 선택합니다.

-> 총 점수는 270이 되어야 하는데

 

내 잘못짠 코드는 출력이 240이 된다.

1. 첫째 날에는 100점인 과제를 선택합니다.
2. 둘째 날에는 60점인 과제를 선택합니다.
3. 셋째 날에는 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);

과제를 마감일이 늦은 순서대로 정렬한다.

마감일이 늦은 순서대로 과제를 처리한다.

같은 마감일에 있는 과제라면 더 높은 점수를 가진 과제가 선택되는 경향이 있다.

 

 

[탐욕 알고리즘 힌트]

1. 문제 설명: 문제가 각 단계에서의 최적해가 전체적인 최적해를 보장한다는 힌트를 제공하는 경우가 있습니다. 이는 탐욕 알고리즘의 특징 중 하나입니다.
2. 문제 유형: 일부 문제는 자연스럽게 탐욕 알고리즘을 적용하기에 적합한 형태를 가지고 있습니다. 예를 들어, 거스름돈 문제나 활동 선택 문제 등은 탐욕 알고리즘이 자주 사용되는 예시입니다.
3. 최적 부분 구조 (Optimal Substructure): 문제가 작은 부분 문제들로 분할되어 있고, 각 부분 문제의 최적해가 전체 문제의 최적해로 이어진다는 특성을 가질 때, 탐욕 알고리즘이 적용될 수 있습니다.
4. 특정 조건과 제약 조건: 문제에 특정한 제약 조건이 있거나 입력의 특성이 주어진 경우에 탐욕 알고리즘이 효과적일 수 있습니다.

 

 [탐욕 알고리즘 예시]

1. 최소 거스름돈 문제 (Greedy Change Making Problem): 이 문제에서는 거스름돈을 주는데 필요한 동전의 수를 최소화해야 합니다. 가장 큰 가치의 동전부터 차례대로 사용하여 거스름돈을 주는 방식입니다.
2. 최소 신장 트리 (Minimum Spanning Tree): 그래프에서 모든 노드를 연결하면서 가중치의 합이 최소가 되는 트리를 찾습니다. 프림 알고리즘과 크루스칼 알고리즘이 탐욕 알고리즘의 대표적인 예시입니다.
3. 최단 경로 문제 (Shortest Path Problem): 출발점에서 도착점까지의 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘이 이에 속합니다.
4. 작업 스케줄링 문제 (Job Scheduling Problem): 주어진 작업을 최적의 순서로 처리하는 문제입니다. 가장 일찍 끝나는 작업부터 처리하는 방식이 있습니다.
5. Fractional Knapsack Problem: 배낭에 담을 수 있는 무게가 제한되어 있을 때, 각 물건의 일부분을 담을 수 있는 경우의 배낭 문제입니다.
6. 활동 선택 문제 (Activity Selection Problem): 한 자원이 여러 활동에 동시에 참여할 수 없을 때, 최대한 많은 활동을 선택하는 문제입니다. 종종 각 활동의 종료 시간이 중요한 요소가 됩니다.

---

 

BOJ 13904 과제  탐욕 알고리즘인 이유

각 과제에는 점수와 마감일이 주어지고, 특정 기간 내에 최대 점수를 얻어야 한다는 등의 조건이 주어지면, 이는 탐욕 알고리즘을 고려할 수 있는 문제 특성이다.