🧐 문제 풀이
그리디 알고리즘... 을 알고싶어서 푼 문제입니다!
그리디 알고리즘?
일단 한 줄로 정리한다면
현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘 이라고 합니다.
최선의 선택?
각각 상황에서 '최적'이라고 생각하는 방법을 선택합니다.
위 그림에서는 각 노드에서 가장 큰 수를 택할 때가 최적의 경우가 되겠죵?
그리디 알고리즘 조건
1. 탐욕 선택 조건
각 단계에서 '최선의' 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우
탐욕적인 선택은 항상 안전하다는 것이 보장되어야 합니다. 어떤 선택으로 전체 문제에 대한 최적해를 반드시 도출할 수 있어야 합니다.
2. 최적 부분 구조 조건
전체 문제의 최적해가 '부분 문제의 최적해로 구성' 될 수 있는 경우
전체 문제의 안에는 여러 단계가 존재하고,이 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 합니다.
문제 예시
- 거스름돈 문제
- 거슬러야 할 동전의 수를 최소로
- 가장 큰 단위부터 거슬러주고 나머지를 그 다음 단위의 돈으로 거슬러줍니다. - 활동 선택 문제
- 시간표 짜기- 회의실 시간 분배
- 가장 많은 수업 , 가장 많은 회의
- 회의실 시간 분배
회의실 배정
그래서 오늘 볼 문제도 그리디 알고리즘을 이용해서 푸는 문제입니다.
간단하게 말하자면 회의 시간에 따라 회의를 적절하게 배치하여 가장 많은 수의 회의를 하는 결과를 도출해내면 됩니다!
가장 많은 회의를 하기 위해서 우선 회의 시간을 정렬을 해주어야 합니다.
- 시작 시간이 빠른 순서대로
우선 시작시간이 빠른 애 부터 넣어줘야 뒤에도 맞춰서 넣어줄 수 있기 때문입니다.
저는 이 조건만 고려했기 때문에 틀렸었습니다.
- 종료 시간이 빠른 순서대로
최대한 많은 회의를 할 수 있도록 하는게 목표입니다.
시작 시간이 같은 경우가 존재할 수도 있습니다.
이 경우 종료 시간이 빠른 회의를 선택해야 뒤에 다른 회의들을 할 수 있습니다.
정렬은 두 가지 다 이용해서 해줘야 하는데 우선순위를 잘 두어야 합니다!
우선 종료시간이 빠른게 우선입니다!
종료시간이 같을 경우 시작시간이 빠른 것을 택해주면 됩니다!! <= 이것 때문에 계속 틀렸습니다..ㅠ
📝 결과 코드
const filePath = process.platform === "linux" ? "/dev/stdin" : "./test.txt";
const input = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n");
let N = Number(input.shift());
let meeting = [];
for (let i = 0; i < N; i++) {
meeting.push(input.shift().split(" ").map(Number));
}
meeting.sort((a, b) => a[1] - b[1] || a[0] - b[0]);
let temp = 0;
let ans = 0;
for (let j = 0; j < N; j++) {
if (temp <= meeting[j][0]) {
ans++;
temp = meeting[j][1];
}
}
console.log(ans);
참고블로그
