- 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법.
- 최적해를 구하는 데에 사용되는 근사적인 방법이다.
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
- 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.
- 하지만 이 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
그리디 알고리즘 문제 해결 방법
- 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답을 선택
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사(Solution Check): 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정들을 반복
그리디 알고리즘을 적용을 위한 2가지 조건
- 그리디 알고리즘이 잘 작동하는 문제는 대부분
greedy choice property(탐욕스런 선택 조건)과optimal substructure(최적 부분 구조 조건)이라는 두 조건을 만족해야 한다.
- 탐욕스런 선택 조건 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조 (Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
이러한 조건이 성립하지 않는 경우에는 그리디 알고리즘은 최적해를 구할 수 없다. 하지만, 이러한 경우에도 그리디 알고리즘은 그사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
어떤 특별한 구조가 있는 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 그리디 알고리즘의 활용도가 높다.
그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 일정 수준의 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이로 인해 근사 알고리즘으로 활용할 수 있다.
그리디 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.
근사 알고리즘 (Approximation Algorithm) 이란?
어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 말한다. 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 일정 수준 이상으로 보장된 근사해를 계산할 수 있다.
그리디 알고리즘의 적용
그리디 알고리즘을 적용하는 문제이다. 백준 1080번이 그리디 알고리즘을 이용한 문제이다. 1080 - 행렬
문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
알고리즘 적용
배열의 (0, 0) 지점부터 (n - 3, m - 3) 지점까지 A행렬의 모든 칸을 순회한다. 순회하면서 B행렬과 다를 경우, 문제에서 주어진 반전 연산을 실행한다. 순회가 끝나면 두 행렬을 비교, 같으면 연산 횟수를 다르면 -1을 출력한다.
그리디 알고리즘을 이용한 풀이이고 이 외에 최적해는 존재하지 않는다.니한 번의 연산으로 3 * 3 크기의 부분 행렬이 모두 반전되므로 한 칸을 바꾸기 위해서라면 오른쪽, 아래, 오른쪽 아래 대각선 3번을 다 바꿔줘야 하는데 이보다 더 적은 연산으로 바꿀 수 있는 방법이 없기 때문이다.
코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int answer = 0;
vector<vector<int>> A, B;
void getMatrix(vector<vector<int>>& mat) {
for (int x = 0; x < n; x++) {
vector<int> temp;
for (int y = 0; y < m; y++) {
char input;
cin >> input;
temp.push_back(input - '0');
}
mat.push_back(temp);
}
}
void flip(int x, int y) {
if (x + 2 < n && y + 2 < m) {
for (int dx = 0; dx < 3; dx++) {
for (int dy = 0; dy < 3; dy++) {
A[x + dx][y + dy] = A[x + dx][y + dy] ^ 1;
}
}
answer++;
}
}
bool equals() {
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (A[x][y] != B[x][y]) return false;
}
}
return true;
}
int main(void) {
cin >> n >> m;
getMatrix(A); getMatrix(B);
for (int x = 0; x < n - 2; x++) {
for (int y = 0; y < m - 2; y++) {
if (A[x][y] != B[x][y]) flip(x, y);
}
}
if (equals()) cout << answer << endl;
else cout << -1 << endl;
return 0;
}