안녕하세요.
이번 포스팅 부터 약 2-3회에 걸쳐 그리디 알고리즘(greedy algorithm)에 대해서 알아보겠습니다.
내용에 대해 궁금한 점이나 피드백은 언제든지 댓글을 남겨주세요 :)
1. 그리디 알고리즘(Greedy algorithm)
우리는 지난 포스팅에서 동적 프로그래밍(Dynamic programming)에 대해서 알아 보았습니다.
단순히 모든 경우에 대해서 반복적으로 재귀호출을 통해서 탐색을 하는 Brute force의 방식보다, 각각의 경우에 대해 테이블을 만들어 필요할 때마다 테이블 값을 이용하는 동적 프로그래밍은 보다 좋은 시간복잡도를 나타냈습니다.
하지만, 어찌되었든 간에 동적 프로그래밍 또한 탐색에 있어서 모든 경우에 대해서 탐색을 진행합니다. 이는 결국 필요하지 않은 케이스조차 검색하는 비효율적인 면을 갖고 있습니다.
헌데 어떤 문제들에서는 더 간단하고 보다 효율적인 알고리즘으로도 탐색을 할 수 있습니다.
일반적으로, 최적화 문제에서는 각 단계마다 여러 가지 경우 중에서 좋은 것을 택해야 합니다. 이러한 최적화 문제에서 동적 프로그래밍을 사용한다면 지나치게 많은 탐색을 하게 될 수 있습니다.
따라서 우리는 탐욕 알고리즘, 그리디 알고리즘을 사용합니다.
그리디 알고리즘(Greedy algorithm)은 각 단계에 있어서 가장 좋은 것을 선택합니다. 그리고 그러한 선택은 전체적으로 최적해로 안내하게 될거라는 바람에서 지속됩니다.
우리는 앞으로 그리디 알고리즘이 최적해를 제공할 수 있는 최적화 문제에 대해 알아볼 것입니다.
그리디 알고리즘이 언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있습니다.
2. 활동 선택 문제(Activity Selection Problem)
활동 선택 문제란, 예를 들어, 한번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다.
영어로 나와있는 바와 같이 문제를 가정하고 진행합니다.
특정 활동 ai가 있으며, si는 활동의 시작시간, fi는 활동이 끝나는 시간입니다. 그리고 ai, aj 활동이 각각 존재할 때, 두 활동의 활동시간이 서로 겹치면 안됩니다.
추가적으로, 주어지는 활동들은 끝나는 시간이 단조 증가하는 형태로 정렬된 상태입니다.
이제 아래의 활동들을 바탕으로 활동 집합을 고려해 보겠습니다.
위의 테이블을 보았을 때, a3, a9, a11은 함께 스케줄로 짤 수 있는, 즉 양립할 수 있는 활동들 입니다.
하지만 a1, a4, a8, a11 이라는 집합도 양립 가능하며 이러한 집합이 크기가 더 크기 때문에 최대 크기의 부분집합은 a1, a4, a8, a11이 됩니다.
이제 이러한 문제를 단계에 거쳐가며 탐색해보도록 하겠습니다.
3. 활동 선택 문제의 최적 부분 구조
활동 ai가 종료한 후에 시작하고, 활동 aj가 시작하기 전에 종료하는 활동들의 집합을 Sij로 나타냅니다.
Sij에 들어 있는 상호 양립 가능한 최대 크기의 집합을 찾기를 원하며, 그러한 최대 크기의 집합은 활동 ak를 포합하는 Aij라고 가정하겠습니다.
최적해 Aij에 ak를 포함하면 결국 두개의 부분 문제가 남게 됩니다. 하나는 Sik이며 다른 하나는 Skj입니다.
그렇다면, Aik = Aij ∩ Sik이고 Akj = Aij ∩ Skj 입니다. 이렇게 하면 Aik는 Aij에서 ak가 시작하기 전에 끝나는 활동들을 포함하고 Akj는 Aij에서 ak가 끝난 후에 시작하는 활동들을 포함하게 됩니다. 따라서 Aij = Aik U {ak} U Akj이고 Sij에 들어 있는 상호 양립 가능한 활동들의 최대 크기 집합 Aij는 |Aij| = |Aik| + |Akj| + 1 개의 활동들로 이루어 집니다.
이런 방식의 최적 부부 구조는 활동 선택 문제를 동적 프로그래밍을 사용해 풀수도 있음을 보여줍니다. 만약 집합 Sij를 위한 최적해의 크기를 c[i,j]로 나타낸다면, 다음과 같은 재귀방정식을 가지게 됩니다.
하지만 앞서 말한바와 같이 이러한 동적 프로그래밍 방식은 모든 부분 문제를 풀어봐야 한다는 단점이 있습니다.
4. 그리디 선택하기
활동 선택 문제에 있어서 그리디 선택을 한다는 것은 무엇을 의미할까요?
아마, 가능한 활동시간 내에서 최대한 많은 활동을 할 수 있도록 활동들의 집합을 고르는 것을 의미할 것 입니다.
위에서 동적 프로그래밍 방식은 모든 부분 문제를 풀어봐야 한다는 단점을 언급하였습니다. 그렇다면 그리디 선택은 어떤 장점을 가질까요?
그리디 선택은 처음 개요에서 설명드렸듯이, 동적 프로그래밍에서 필요하지 않은 케이스 조차 탐색하는 불필요한 탐색시간을 없애고, 각 단계에서 최적의 선택을 함으로써 시간적으로 효율적인 것을 볼 수 있습니다.
그렇다면 활동 선택 문제에서의 그리디 선택은 어떻게 될까요?
바로, 제일 먼저 종료되는 활동을 선택하고, 해당 활동과 양립할 수 있는 활동들의 subproblem에서 또 다시 제일 먼저 종료되는 활동을 선택합니다. 이런식으로 반복하면 최대한 많은 활동들을 선택할 수 있습니다.
왜 그렇게 될까요? 간단하게 말해서, 제일먼저 끝나는 활동을 선택했을 때, 남은 subproblem에서 최대한 많은 활동을 고를 수 있기 때문입니다.
이러한 그리디 선택은 다음 그림에서 확인할 수 있습니다.
이러한 그리디 알고리즘을 수도 코드로 나타내면 다음과 같습니다.
먼저, 재귀적 그리디 알고리즘 입니다.
주어진 수도코드를 분석해보면, 전체 시간복잡도는 O(n)으로써 동적 프로그래밍에 비해 효율적인 탐색시간을 나타냅니다.
그리고 이번에는 반복 순환 그리디 알고리즘 입니다.
해당 수도코드의 시간복잡도 또한 O(n)입니다.
추가적으로 궁금한 사항이나 내용에 대한 피드백은 언제든지 댓글을 이용해주세요:)
'Algorithm > 알고리즘 이론' 카테고리의 다른 글
| 알고리즘_시간복잡도, 공간복잡도, Big-O 표기법 (1) | 2019.02.09 |
|---|---|
| 알고리즘 #11_ KNN 최근접 이웃 알고리즘이란? (2) | 2018.06.30 |
| 알고리즘 #9_ 최적 이진 검색 트리(BST: Binary Search Tree) (0) | 2017.12.10 |
| 알고리즘 #8_ 최장 공통 부분 수열(LCS: Longest Common Subsequence) (0) | 2017.12.04 |
| 알고리즘 #7_ 동적 프로그래밍: 동적 프로그래밍의 요소 (1) | 2017.11.18 |