[코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 5장 그리디 알고리즘

5.1 들어가며

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

- 주어진 문제가 그리디 방식을 사용하기에 적합한지 판단하기 위해 사용되는 최적 부분 구조 속성과 그리디 선택 속성이 있다.

---

5.2 기본적인 그리디 알고리즘

- 그리디 방식으로 해결할 수 있는 대표적인 두 문제인 최단 작업 우선 스케줄링과 분할 가능 배낭 문제가 있다.

5.2.1 최단 작업 우선 스케줄링

- 여러 개의 작업(Job)이 대기하고 있을 때, 각 작업의 실행 시간(작업 시간)이 주어진다. 모든 작업을 한 번씩 실행할 때, 평균 대기 시간을 최소화하려면 어떤 순서로 작업을 실행해야 할까?

- 그리디 전략으로는 항상 실행 시간이 가장 짧은 작업부터 선택한다. 현재 시점에서 가장 빨리 끝낼 수 있는 작업을 먼저 처리하면 전체 대기 시간이 줄어든다.

 

5.2.2 연습 문제 24: 최단 작업 우선 스케줄링

- ...

---

5.3 배낭 문제

- 0-1 배낭 문제라고도 부르는 일반 배낭 문제는 NP-완전 문제로 알려져 있어서 다항 시간 솔루션을 사용할 수 없다. 그러나 0-1 배낭 문제를 조금 변경한 분할 가능 배낭 문제는그리디 방식으로 해결할 수 있다.

 

5.3.1 0-1 배낭 문제

- 0-1 배낭 문제(0-1 Knapsack Problem)는 고전적인 조합 최적화 문제로, 제한된 자원(배낭의 무게 한도) 안에서 최대의 가치를 얻기 위해 어떤 물건을 선택할지 결정하는 문제이다.

 

5.3.2 분할 가능 배낭 문제

- 일반 배낭 문제가 NP-완전인 것과 달리 분할 가능 배낭 문제는 간단한 솔루션이 존재한다. 각 물건을 단위 무게당 가격을 기준으로 정렬하고, 그리디 방식에 따라 단위 무게당 가격이 높은 순서로 물건을 선택한다.

 

5.3.3 연습 문제 25: 분할 가능 배낭 문제

- ...

 

5.3.4 실습 문제 11: 작업 스케줄링 문제

- ...

 

5.3.5 그리디 알고리즘의 요구 조건

- 최적 부분 구조와 그리디 선택이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.

• 최적 부분 구조 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말한다.
• 그리디 선택 : 주어진 문제 P에 대한 지역적 최적 솔루션을 반복적으로 선택하여 전체 최적 솔루션을 구할 수 있을 경우, 문제 P가 그리디 선택 속성을 갖는다고 말한다.

5.3.6 최소 신장 트리 문제

- 최소 신장 트리 문제는 다음과 같이 정의할 수 있다.

"정점의 집합 V와 가중치를 갖는 에지의 집합 E로 구성된 그래프 G = <V, E>가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하시오."

 

- 최소 신장 트리 T를 구하는 그리디 알고리즘은 다음과 같다.

1. 그래프 G의 모든 에지를 최소 힙 H에 추가한다.
2. H로부터 에지 e를 하나 꺼낸다. 당연히 e는 모든 에지 중에서 가장 가중치가 작은 에지이다.
3. e의 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있다. 그러므로 이런 경우에는 e를 버리고 2단계로 이동한다. ->  그래프 에지 정보를 저장할 자료 구조가 필요하고, 새로운 에지를 추가할 때 사이클이 발생하는지를 판단하는 기능이 필요한데, 이 문제는 디스조인트-셋 자료 구조를 사용하여 해결할 수 있다.
4. 최소 신장 트리 T에 e를 추가하고, 2단계로 이동한다.

- 이 알고리즘은 2단계부터 4단계까지를 반복하면서 가장 작은 가중치의 에지를 찾고, 이 에지에 의해 사이클이 발생하지 않으면 해당 에지와 양 끝 정점을 최종 솔루션이 추가한다.

- 이 알고리즘은 매 반복마다 최소 에지 가중치를 선택하기 때문에 그리디 방식이라고 할 수 있다.

- 이 알고리즘은 1956년에 발표되었으며, 크루스칼 최소 신장 트리 알고리즘이라고 부른다.

 

- 위의 알고리즘이 제대로 동작하지는 알려면 최적 부분 구조와 그리디 선택 속성을 갖는지 확인해야 한다.

   - 최적 부분 구조 : 귀류법을 사용하여 최적 부분 구조 속성을 증명해보겠습니다. 이를 위해 MST 문제가 최적 부분 구조 속성을 가지지 않는다고 가정하겠습니다. 즉, 최소 신장 트리가 더 작은 최소 신장 트리의 집합으로 구성되지 않는다고 가정하겠습니다.

1. 그래프 G의 정점으로 구성된 최소 신장 트리 T가 있다고 가정하겠습니다. T에서 에지 e를 하나 선택하여 제거합니다. e를 제거하면 T가 더 작은 트리인 T1과 T2로 나눠집니다.
2. MST 문제가 최적 부분 구조 속성을 갖지 않는다고 가정했으므로 T1보다 작은 가중치를 갖는 신장 트리 T1이 존재해야 합니다. 이 신장 트리 T1과 T2를 에지 e로 연결한 새로운 신장 트리를 T이라고 하겠습니다.
3. T의 전체 가중치가 T의 전체 가중치보다 작기 때문에 처음에 T가 최소 신장 트리라고 가정했던 가설이 틀리게 됩니다. 그러므로 MST 문제는 최적 부분 구조 속성을 만족해야 합니다.

   - 그리디 선택 : MST 문제가 그리디 선택 속성을 갖는다면 정점 V와 연결된 에지 중에서 최소 가중치 에지는 반드시 최소 신장 트리 T에 속해야 합니다. 귀류법을 사용하여 이 가설을 증명할 수 있습니다.

1. 정점 V에 연결되어 있는 에지 중에서 최소 가중치를 갖는 에지를 (U, V)라고 가정하겠습니다.
2. 만약 (U, V)가 T에 속하지 않는다면 T는 V와 연결되어 있는 다른 에지를 포함해야 합니다. 이 에지를  (X, V)라고 가정하겠습니다. (U, V)가 최소 가중치 에지이기 때문에 (X, V)의 가중치는 (U, V)의 가중치보다 커야 합니다.
3. T에서 (X, V)를 제거하고 (U, V)를 추가할 경우, 전체 가중치가 더 작은 트리를 얻을 수 있다. 이는 T가 최소 신장 트리라는 가정에 위배됩니다. 그러므로 MST 문제는 그리디 선택 속성을 만족해야 합니다.

-  최소 신장 트리 T를 구하는 그리디 알고리즘의 3단계로 e의 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있다. 그러므로 이런 경우에는 e를 버리고 2단계로 이동한다. ->  그래프 에지 정보를 저장할 자료 구조가 필요하고, 새로운 에지를 추가할 때 사이클이 발생하는지를 판단하는 기능이 필요한데, 이 문제는 디스조인트-셋 자료 구조를 사용하여 해결할 수 있다.

 

5.3.7 디스조인트-셋 자료 구조

 - 디스조인트-셋 또는 유니옹-파인드 자료 구조는 트리 형태의 원소로 구성된 포레스트이다.

   - 각각의 원소는 숫자 ID에 의해 표현되며, 랭크와 부모에 대한 포인터를 가진다.

   - 디스조인트-셋 자료 구조가 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성되며, 각각의 원소는 하나의 트리를 나타낸다.

 

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

• make-set(x) : 이 연산은 x를 ID로 갖는 원소를 디스조인트-셋 자료 구조에 추가한다. 새로 추가한 원소의 랭크는 0이고, 원소의 부모 포인터는 자기 자신을 가리키도록 설정한다.
• fine(x) : 이 연산은 원소 x에서 시작해서 부모 포인터를 따라 반복적으로 이동하여 트리의 루트를 반환한다. 참고로 루트 원소의 부모는 루트 자신이다.
• union(x, y) : 두 개의 원소 x와 y에 대해 union() 연산을 수행하면 먼저 x와 y의 루트를 찾는다. 만약 두 루트가 같다면 이는 x와 y가 같은 트리에 속해 있음을 의미하며, 이 경우에는 아무런 작업도 하지 않는다. 만약 두 개의 루트가 서로 다르면 높은 랭크 루트를 낮은 랭크 루트의 부모로 설정한다. union(x, y) 연산을 거듭할수록 더 많은 트리가 병합되어 전체 트리 개수는 줄어들고, 대신 각 트리의 크기는 점점 거대해지게 된다. 

- 크루스칼 알고리즘의 사이클 발생 여부를 검사하기 위해 디스조인트-셋의 union(x, y) 연산을 활용할 수 있다.

   - 에지 양 끝의 정점에 대해 union(x, y) 연산을 수행하여 실제로 두 트리가 병합하면 해당 에지를 MST에 추가한다. 만약 X와 Y의 루트가 같으면 두 정점을 잇는 에지에 의해 사이클이 발생한다는 의미이다. 그러므로 이 경우에는 union(x, y) 연산은 아무 작업 없이 그대로 종료하고, 해당 에지를 MST에 추가하지 않는다.

 

5.3.8 연습 문제 26: 크루스칼 MST 알고리즘

 - 디스조인트-셋 자료 구조를 사용하지 않는 크루스칼 알고리즘의 시간 복잡도는 O(E log E)이다. 여기서 E는 그래프에서 에지 개수를 의미한다.

   - 그러나 디스조인트-셋 자료 구조를 사용하면 전체 복잡도가 O(Ea(V))로 줄어들며, 여기서 a(v)는 아커만 함수의 역함수이다. 아커만 함수의 역함수는 로그 함수보다 훨씬 느리게 증가한다. 그러므로 정점 개수가 작은 그래프에서는 두 구현의 성능 차이가 작지만, 정점이 많은 그래프에서는 큰 성능 차이가 발생할 수 있다.

---

5.4 그래프 컬러링

- 그래프 컬러링 문제는 다음과 같이 정의된다.

"주어진 그래프 G에서 서로 인접한 정점끼리 같은 색을 가지지 않도록 모든 정점에 색상을 지정해야 한다."

- 스도쿠 퍼즐은 다음 과정을 통해 그래프 컬러링 문제로 모델링할 수 있다.

• 각각의 셀을 그래프 정점으로 표현한다.
• 같은 행, 같은 열, 3x3 블록 안에 있는 모든 정점기리 에지를 연결한다.
• 생성된 그래프 G에 대해 그래프 컬러링을 수행하면 입력 스도쿠 퍼즐의 해답을 구할 수 있다.

 

5.4.1 연습 문제 27: 그리디 그래프 컬러링

- 그래프 컬러링의 평가는 얼마나 적은 수의 색상을 사용했는가에 의해 결정된다. 가능한 적은 수의 색상을 사용하는 최적의 그래프 컬링 방법 찾기는 NP-완전 문제이지만, 그리디 방식이 유용한 근사치를 제공하곤 한다.

 

5.4.2 실습 문제 12: 웰시-포웰 알고리즘

- 차수가 높은 정점부터 차례대로 그래프 컬러링을 수행하는 것은 웰시-포웰 알고리즘이라고 하며, 다음 순서를 따른다.

1. 모든 정점을 차수에 대한 내림차순으로 정렬하고 배열에 저장한다. // 차수 : 정점에 연결된 간선의 개수
2. 정렬된 배열에서 색상이 지정되지 않은 첫 번째 정점을 선택하고, 이 정점과 연결된 모든 정점을 조사하여 아직 사용되지 않은 색상을 해당 정점에 저장한다. 이 색상을 C라고 지칭하겠다.
3. 정렬된 배열에서 색상이 지정되지 않은 정점을 모두 찾고, 만약 이 정점의 이웃이 C 색상을 가지고 있지 않다면 해당 정점에 C 색상을 지정한다.
4. 배열에 색상이 지정되지 않은 정점이 남아 있다면 2단계로 이동한다. 남아 있는 정점이 없다면 종료한다. 이때까지 정점에 지정된 색상이 최종 결과이다.

---

5.5 나가며