[Algorithm] 탐욕 알고리즘 (Greedy Algorithm)

1. 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘은 선택의 순간마다 그 이후를 고려하지 않고, 현 시점에서 가장 최적인 방법을 선택하는 알고리즘을 말한다.

순간마다 최적인 방법을 선택하기 때문에 항상 최적의 결과값을 배출하진 않는다.

 

그러나 다른 알고리즘보다 평균적으로 속도가 빠르고, 어느 정도 최적에 근사한 답을 알려준다.

 

 

2. 문제 : 회의실 배정 

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하 면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중 단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 즉, 회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)이다.

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;
}

let arr = [[1, 4], [2, 3], [3, 5], [4, 6], [5, 7]];
console.log(solution(arr));

 

위 문제는 끝나는 시간을 기준점으로 잡고 정렬한 후 문제를 풀어야 한다. 

 

만일 시작시점을 기준으로 정렬한다면, 시작시점만 빠르고 끝시점이 늦는 경우 최선의 방법이 되지 못한다.

즉 반례가 있는 것이다. 

끝시점이 빨라야 다음 회의를  빠르게 시작할 수 있기 때문에 끝시점을 기준으로 잡는 것이 좋다.

 

그리고 끝 시점이 같은 경우에는 시작시점으로 정렬해준다.

끝 시점이 같으면 시작 시점이 빠를수록 더 많은 회의를 진행할 수 있기 때문이다. 

 

정렬한 후에는 현재 현재 회의의 시작 시점이 이전 회의의 끝 시점과 같거나 느리경우, 카운트를 추가해준다. 

 

meeting.sort((a, b) => {
    if (a[1] === b[1]) return a[0] - b[0]
    else return a[1] - b[1]
})

 

처음엔 sort를 이용해서 meeting을 정렬해준다.

끝시점이 같다면 시작시점을 기준으로, 그렇지 않다면 끝시점을 기준으로 정렬해준다. 

 

let et = 0;
for (let x of meeting) {
    if (x[0] >= et) {
        answer++;
        et = x[1]
    }
}

 

이제 for문을 이용해 현재 회의의 시작 시점(x[0])이 이전 회의의 끝 시점(et)보다 크거나 같을 경우 answer에 카운트를 더해준다.

그리고 et라는 변수를 만들어서 현 시점의 끝 시점을 계속해서 갱신시켜준다. 

 

---

 

처음 이 문제를 접했을 때 어떻게 찾아야 할지 감이 안왔다..

그래서 그리디가 뭔지 찾아보고 문제를 풀어봤는데 어떻게 풀어야 할지 모르겠더라ㅠㅠ

나름대로 문제를 이해해보고 고민해서 풀긴했는데 제대로 풀지 못한 느낌?

 

결국 강의 설명을 듣고 풀어봤는데 강의를 들을때는 이해가 가지만 어떻게 접근해야 하는지를 모르겠더라

처음에 접근할 때 최대한 문제를 이해하고, 최적의 접근 방법을 찾는수밖에 없는거 같다ㅠㅠ

뭐 어쩌겠어.. 문제 많이 풀어봐야지..

 

그리고 문제를 읽으면서 어떻게 접근할지 직접 손으로 적어보는게 좋은것 같다.

안풀리거나 헷갈리다가도 직접 손으로 풀면 은근 해결되는 경우가 있더라..

이 문제도 강의듣고 엥? 이랬는데 손으로 적으면서 이해해보니까 오.. 했다ㅋㅋㅋ