그리디 알고리즘 시리즈

그리디 알고리즘을 조금 깊게 공부해보면 좋을 것 같아서 정리해보았다. 공부를 하면서 범위가 넓어지면서 시리즈로 나누어서 정리해보았다. 시리즈 1을 작성하면서 나도 많이 공부하게 되었고, 기본이 많이 부족하다는 것을 느꼈다. 역시 기본으로 돌아가서 기본이 충실한 사람이 되어야겠다. 내실을 튼튼히 해야만 흔들리지 않을 것 같다.

시작하겠다.

그리디 알고리즘이란?

그리디 알고리즘은 '가장 좋아 보이는' 해답을 선택하는 알고리즘이다. 즉 그리디 방법은 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 것이다.

다음의 그림은 서울역에서 영등포역까지 가는 최단 경로를 보여준다. 여기 경로상에 있는 임의의 두 지점을 선택할 경우, 이 두 지점의 최단 이동 거리는 처음에 구한 전체 최단 경로를 따라 이동함으로써 구할 수 있다.

사실 전체 최단 경로는 해당 경로상에 존재하는 다수의 지점 사이클 최단 거리 경로로 모두 연결한 것으로 볼 수 있다. 그렇기 때문에 어느 두 지점 사이의 최단 경로를 구하기 위하여 다음과 같은 방법을 사용할 수 있다. 즉, 출발 지점에서 아직 방문하지 않은 가장 가까운 지점까지의 경로를 찾고, 이를 목적 지점에 다다를 때까지 반복하는 것이다. 거의 모든 지도 Saas 서비스의 지도에서 사용되는 다익스트라의 기본 개념이다.

하지만 그리디 접근 방식은 너무 단순하다. 그렇기 때문에 몇몇 알고리즘 문제에서만 적용할 수 있다. 그 예로 앞서 살펴 보았던 DP편에서 최소 동전 교환 개수를 구하는 문제에서는 그리디 방법으로 최적해를 도출하지 못했었다.

그리디 방법이 단순하긴 하지만 이를 통해 문제에 대한 해결 방법을 떠올리는 것은 매우 중요하고 좋은 초석이 될 수 있다고 확신한다.

최단 작업 우선 스케쥴링

사람들이 화장실 앞에서 볼 일을 보기 위해 줄을 서는 것을 생각해 보자. 사람들마다 정량적 사용하는 시간이 정해져 있고 그 값이 각각 상이하다고 한다. 사람들은 인내심을 발휘해서 볼 일을 조금 더 참더라도 전체 평균 대기시간이 줄어드는 것을 선택한다고 했을 때, 대기 순서를 어떻게 변경해야 할까?

처음 대기열 순서

위의 순서로 따져 보았을 때, 평균 대기 시간은 15.25분이다.

가장 작은 평균 대기 시간을 만드는 것은 상식적으로 생각해보면, 가장 적게 볼 일을 하는 사람부터 볼 일을 보는 것이다. 그렇기 때문에 볼일 시간이 가장 작은 순서대로 정렬을 하면 된다.

최소 대기 시간 대기열 순서

평균 대기 시간은 8.8분이다. 퍼포먼스 측면으로 볼 때 두 배 이상의 성능 향상을 보인다.

배낭 문제

배낭에 넣은 물건들의 가치의 합이 최대가 되도록 하는 문제이다.

NP-Complete 문제

일반 배낭 문제는 NP-Complete 문제이다.(0-1 배낭 문제) 그렇기 때문에 다항 시간 솔루션을 사용할 수 없다.

여기서 NP란 Non-deterministic Polynomial의 약자로, 다항 시간에 비결정론적으로 해결 가능한 문제들의 집합을 말한다.

0-1 배낭 문제

물건들의 집합 S와 각 물건의 무게 w와 가치 v가 주어졌을 때, 배낭의 용량이 W를 넘지 않으면서 배낭에 넣을 수 있는 물건들의 가치의 합이 최대가 되도록 하는 문제이다.

조선 시대의 보부상을 떠올려보자. 매출의 일정 비율이 항상 이익으로 떨어지는데, 이익을 극대화 하려면 비싼 물건들을 가지고 다니면서 팔아야하지만 보부상이 사용할 수 있는 배낭은 오래되어 무게가 10kg이 한계다. 그렇다면 어떤 물건들을 가지고 다니면서 팔아야 이익이 극대화 될까?

일반 배낭 문제의 예

전체 무게 8을 맞추기 위해서 O1, O3, O5을 넣으면 가치의 합이 37이 되는 반면, 위의 테이블에서 전체 무게 8을 맞추기 위해서 O1, O2, O5, O6을 넣으면 가치의 합이 40이 된다. 결과적으로 40이 최대가 된다.

분할 가능한 배낭 문제

일반 배낭 문제와는 반대로 물건의 일부만 담을 수 있고, 물건을 분할하는 것은 무제한으로 할 수 있다고 가정해보자.

실생활에서 예를 들어보면 리터당 파는 기름이나, 무게당 무게를 달아서 파는 고기, 곡식, 파우더 종류의 물건들이 있다. 배낭속은 엉망이겠지만, 원하는 양만큼 담을 수 있다.

앞서 배낭에 담을 수 있는 무게가 최대가 8일 때, 최대값은 40이었다. 무게당 가격도 함께 살펴보면 무게당 가격이 높은 순으로 매겨졌던 것을 볼 수 있다.

최소 신장 트리 문제

최소 신장 트리 문제는 그래프에서 모든 정점을 포함하는 트리를 찾는 문제이다. 트리는 사이클이 없는 그래프이며, 모든 정점을 포함하는 트리는 신장 트리라고 한다. 에지의 가중치 합 최소가 되는 신장 트리를 찾는 문제이다.

줄인 말로 MST라고도 한다. 가장 쉬운 예로 상수도관을 설계하는 것을 예로 들 수 있다. 상수도는 모든 집을 연결해야 하며, 각 집마다 연결하는 비용이 다를 수 있다. 그렇기 때문에 최소 비용으로 모든 집을 연결하는 이익이다.

아래의 그래프를 살펴보도록 하자.

에지와 가중치의 표현은 표로 대신하도록 하겠다. (추후에 작업 후 업데이트 예정)

싸이클이 없고 무방향이다.

이제 그리디 알고리즘으로 그래프에서 최소 신장 트리를 찾아보도록 하자.

1. 그래프에서 모든 에지를 최소힙에 넣는다.
2. 최소힙으로부터 에지를 하나씩 꺼낸다. 이때 에지의 가중치가 작은 것부터 꺼내진다.
3. 최소힙으로 부터 꺼낸 에지의 값이 이미 구성중인 트리에 있을 경우, 이로인해서 싸이클이 발생할 수 있기 때문에 해당 에지는 무시한다. 그리고 다시 2번으로 돌아간다.
4. 최소힙으로 부터 꺼낸 에지의 값이 이미 구성중인 트리에 없을 경우, 해당 에지를 트리에 추가한다. 그리고 다시 2번으로 돌아간다.

위의 방법을 반복해서 얻어진 에지와 정점은 최소 신장 트리를 구성할 수 있다. 매번 반복마다 최소 에지 가중치를 선택하기 때문에(최소힙) 그리디한 방식으로 볼 수 있다.

위 그래프의 최소 신장 트리 가중치의 정답은 가중치의 합이 14가 되는 것이고 연결된 에지는 위와 같다.

디스조인트-셋 자료 구조

디스조인트-셋 또는 유니온-파인드 자료구조는 트리 형태의 원소로 구성된 자료구조이다. 각각의 원소는 숫자 ID에 의해 표현되고, 랭크(Rank)와 부모에 대한 포인터를 가진다. 디스조인트-셋 자료구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되고, 각각의 원소는 하나의 트리를 나타내게된다.

디스조인트-셋 자료구조는 다음의 연산을 지원한다.

• makeSet(x)

• union(x, y)

• find(x)