1. 그리디 알고리즘이란?
그리디 알고리즘은 욕심쟁이 알고리즘이라고도 불리는데 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다.
이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.
그리디 알고리즘이 항상 최적해를 보장해주진 못하지만 몇몇 경우에 있어선 아주 효율적으로 최적해를 구할 수 있다.
1 - 1) 대표문제 1
function solution(meeting){
let answer = 0;
meeting.sort((a, b) => {
if (a[1] === b[1]) return a[0] - b[0];
else return a[1] - b[1];
})
let et = 0;
for (let x of meeting) {
if (x[0] >= et){
answer++;
et=x[1];
}
}
return answer;
}
1 - 2) 대표문제 2
function solution(arr) {
let answer = Number.MIN_SAFE_INTEGER;
let timeLine = [];
for (let i = 0; i < arr.length; i++) {
timeLine.push([arr[i][0], "s"]);
timeLine.push([arr[i][1], "e"]);
}
timeLine.sort((a, b) => {
if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt();
return a[0] - b[0];
});
let cnt = 0;
for (let x of timeLine) {
if (x[1] === "s") cnt++;
else cnt--;
answer = Math.max(answer, cnt);
}
return answer;
}
'Computer Science > 코딩테스트 문제 모음' 카테고리의 다른 글
Binary Search (0) | 2021.07.26 |
---|---|
정렬 (0) | 2021.07.24 |
스택/큐 자료구조 문제 (0) | 2021.07.23 |
Hash Map (0) | 2021.06.14 |
Sliding Window Algorithm (0) | 2021.06.14 |