[Algorithm] Greedy 1

 

 

 

 

Greedy algorithms

 

최적화 문제에서 DP의 방식은 간혹 너무 많은 자원을 낭비하거나 비효율적일 수도 있다. DP는 항상 최적의 경우를 찾아주지만, 꼭 그러한 방식을 따르지 않아도 최적의 경우를 찾는 경우는 상당히 많다. 바로 sub-problem의 문제에 대한 해답이 전체 문제에 대한 해답으로 이어지는 경우인데, 이렇듯 지역적으로 최적화된 선택이 전역적으로도 최선의 선택을 만드는 경우, 또 그 선택들이 항상 순간마다 Best 해 보이는 것을 고르는 경우라면 우리는 이것을 그리디 알고리즘이라고 명명한다.

 

그리디 알고리즘에는 대표적으로 Minimum-spanning tree와 Dijkstra 알고리즘이 있으며, 이는 앞으로 차차 다룰 예정이다. 이에 앞서 그리디 알고리즘의 대표 문제로 거론되는 건 바로 스케줄링이다. 시작 시간과 끝나는 시간이 정해진 여러 프로세스들을 어떤 방식으로 선택해야 가장 많은 프로세스를 끝낼 수 있을까?

 

 

위 표는 각 프로세스의 시작 시간과 끝나는 시간을 끝나는 시간의 오름차순으로 정렬한 표이다. 1번을 선택하게 되면 4 이후의 프로세스를 고를 수 있으므로 시작 시간이 4 이상인 4, 6, 7,... 등을 고를 수 있을 것이다. 찾아보면 알겠지만 $a_{i}$를 프로세스라고 한다면 얻을 수 있는 정답 집합 중 하나는 $\{a_{1}, a_{4}, a_{8}, a_{11}\}$이 될 것이다.

 

사실 그리디 알고리즘은 그 개념 자체로는 상당히 간단해보이고 무식해 보이나, 이를 증명하는 과정은 나름 논리적이고 명확한 면이 있다.

만약 우리가 $S_{ij}$라는 프로세스의 집합들 중에서 가장 많은 겹치지 않는 프로세스의 집합인 $A_{ij}$를 찾고 싶다고 해보자. 그리고 그 안에는 $a_{k}$라는 프로세스가 포함되어 있다.

만약 $a_{k}$ 가 포함되어 있다면, 우리는 이를 기준으로 좌/우의 집합을 나누고, 또 그 안에서의 가능한 프로세스를 골라주는 방식으로 sub-problem을 만들어 낼 수 있을 것이다.

$$ A_{ij} = A_{ik} + a_{k} + A_{kj} $$

 

The optimal substructure of the activity-selection problem

 

우리는 결국 최대 프로세스의 개수를 구하는 것이 목적이므로, 위 식처럼 집합이 아닌 프로세스의 개수로도 나타낼 수 있다. $c[i,j]$가 i와 j사이의 최대 프로세스의 개수라면,

$$ c[i,j] = c[i,k] + c[k,j] + 1 $$

로 나타낼 수 있다. 만약 우리가 $a_{k}$를 포함한 최적화된 솔루션을 알지 못한다면,

 

\begin{equation}
c[i, j] = \begin{cases} 
0 & \text{if } S_{ij} = \emptyset, \\
\max_{a_k \in S_{ij}} \{ c[i, k] + c[k, j] + 1 \} & \text{if } S_{ij} \neq \emptyset.
\end{cases}
\end{equation}

 

우리는 위와 같은 방식으로 모든 프로세스를 비교해야 할 것이다. 여기다가 DP를 쓴다면

 

1. 재귀 + 메모이제이션 (memoization)

2. Bottom-up

 

둘 중 하나를 써야 할 텐데, 만약 우리가 모든 sub-problem을 풀어야 할 필요 없이 우리의 최적화된 솔루션에 한 가지 선택을 추가할 수 있다면? 그렇다면 모든 선택들을 고민할 필요가 없다. 사실 우리는 그냥 한 가지 선택만 하면 될 것이다. 그것이 바로 greedy choice이다.

 

Making the greedy choice

 

그래서 다시 본론으로 돌아가자면 그리디 선택 (greedy choice)이 뭘까? 그것은 바로 우리의 선택으로 인한 남은 자원들이 최대가 되게 하는 것이다. 그렇게 되게 하기 위해선, 스케줄링할 때 가장 일찍 끝나는 프로세스를 고르면 된다. 그것이 바로 남은 자원들이 최대가 되는 경우이기 때문이다. 이것에 대한 증명은 기회가 된다면 추가로 작성하도록 하겠다.

 

Greedy algorithm

스케줄링이 그리디 알고리즘에 따라 실행되는 과정을 나타낸 그림이다. 내가 방금 마친 프로세스의 종료 시점보다 시작 시점이 앞에 있는 경우는 고려 대상이 아니다. 그리고 그다음으로 일찍 끝나는 녀석들 중에 하나를 골라주는 방식으로 진행해 주면 된다.

 

현재 고른 프로세스의 종료 시점이 다음 프로세스를 고르는 데에 필요한 정보가 되므로, 이는 재귀나 반복문을 통해 구현할 수 있다. 의사 코드는 다음과 같다.

Recursive

Iterative

스케줄링에서 우리는 종료시점의 오름차순으로 정렬해 주는 것을 제외한다면, 모든 프로세스를 한 번씩 방문하므로 $\Theta(n)$의 시간 복잡도를 갖게 된다. 재귀와 반복문 중 뭐가 유리할까? 정답은 항상 같다. 오버헤드!