코딩테스트가 중요해진 시점에 저도 좀 더 열심히 취업의 벽을 뚫기 위해
알고리즘 문제 해결 전략 1권을 정독하면서 정리 중입니다.
탐욕법? 그리디? RL강화학습의 엡실론 그리디? 단순히 해보고 정확한 답이 안나오는거아닌가? 애매모호해서 정리해보려고 합니다.
탐욕법은 모든 경우를 탐색하지않고 각 단계마다 가장 좋은 방법만을 선택하는 방법이라고 생각하면 될 것 같습니다. ~당연한 소리~
탐욕법에서 가장 중요한 점은 우리가 정한 방법이 정당한 방식인지 정당성 증명이
가장 중요합니다.
- 최적해 중 우리가 선택한 방법이 포함될 수 있는지!?
간단히 책 예제 하나를 보이면서 정리해보겠습니다.
회의실 예약 문제
회사에 회의실이 하나 밖에 없는데, n(<=100)개의 팀이 각각 회의하고 싶은 시간을 제출했다고 합시다.두 팀이 회의실을 같이 쓸 수는 없기 때문에 이 중 서로 겹치지 않는 회의들만을 골라내서 진행해야합니다. 최대 몇개나 선택할 수 있을까요?
흔히 나오는 activity selection problem 문제입니다.(scheduling problem)
완전 탐색으로 풀지, Greedy로 풀지는 입력의 범위를 바탕으로 판단해보면 되겠습니다.
스케쥴링 문제는 완전탐색으로 힘든 경향이 있습니다. 특정 일을 할지 말지
결정하는 문제라 (on/off) => O(2^n) 정도의 복잡도가 나오기 때문입니다.
문제의 목적이 최대한 많은 회의를 넣는 것이 목적이기 때문에 범위(시작시간, 끝나는시간)를 기준으로 생각해야합니다.
회의가 끝나는 시간이 빠른 순으로 겹치지않게 회의를 넣는 방법을 이용하면 최적의 해를 구할 수 있습니다. 정말 그럴가요?
증명을 해봅시다. 만약 최적해가 우리의 방식을 따르지않고 존재할 때를 가정해봅시다. 그 때 맨 처음 회의보다 더 빨리 끝나는 회의를 넣을 수 있다면 결과는 어떨가요?
최적해(최대 회의 수)는 변함이 없거나 늘어나겠죠?(그 사이에 넣을 수 있는 회의가 있다면 최적해는 증가합니다.)
이런 식으로 그리디 알고리즘은 증명가능하다면 좋은 방법론이 될 것 같습니다.
증명자체가 어려운 문제도 많죠. 다음 포스트에서 더 확인해보겠습니다.
