[알고리즘 공부] 그리디 알고리즘

0. 개요

코딩 테스트 알고리즘 공부를 하다보면 가장 많이 나오는 알고리즘은 아마도 DP와 그리디일 것이다. 

이번주 알고리즘 공부 주제를 고민하다 어쩌면 다시 기초로 돌아가는게 좋겠다는 생각이 들었다.

항상 문제를 풀 때, 그리디.. 그럼 지금 이 상태에서 가장 최적의 해부터 하는건데... 하면서

머릿속으로는 알지만 정작 마주했을 때 어떻게 풀지 막막했던 적이 많이 있었다.

그래서 이번에는 다시 기초부터 쌓아보려고 한다.

1.  알고리즘 개요

 

그리디 알고리즘은 매 순간 가장 최선(최적)이라고 생각되는 선택을 하는 것으로,

최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론이다.

위의 예시 그림처럼, 그리디 알고리즘은 항상 최적의 값을 보장하지 않지만,

이에 근사한 값을 찾는 것을 목표로 하고 있다.

 

2. 알고리즘 구조

그리디 알고리즘은 모든 상황에 사용할 수 있는 알고리즘은 아니다.

그리디 알고리즘은 아래의 두가지 조건을 만족할 경우에만 사용할 수 있다.

 

1) 탐욕 선택 속성 (Greedy Choice Property)

- 각 단계에서의 최적의 선택이 전체 최적의 해로 이어져야 한다.

2) 최적 부분 속성 (Optimal Substructure)

- 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 한다.

 

두 가지 조건을 모두 만족하는 대표적이 예로 동전 거스름돈 문제를 들 수 있다.

거스름 돈을 줄 때, 가장 큰 단위의 동전부터 주어야(탐욕 선택 속성) 동전을 최소한으로 줄 수 있다. (최적 부분 속성)

 

3. 알고리즘 구현

그리디 알고리즘 역시 어떠한 형태가 있는 것이 아니기에 백준의 A와 B 문제에 대한 해답을 예시로 들어서 구현해보았다.

 

해당 문제에서의 핵심은 초기 문장에서 결론 문장을 만드는 순으로 접근하는 것이 아닌,

결론 문장에서 초기 문장으로 돌아가는 것을 핵심으로 잡아야 한다는 것이다.

 

이는 결론 문장에서 초기 문장으로, 즉 문장의 길이를 줄이는 방법이

두가지 방법(문자열 뒤의 A를 제거, 문자열을 뒤집고 앞에 있는 B를 제거) 뿐이라는 것 때문이다.

 

결론 문장에서 두가지 방법 중 가능한 하나의 경우를 선택하면 (탐욕 선택 속성)

초기 문장으로 가까워 질 수 있다는 것이다.

(초기 문장을 O, 결론 문장을 T라고 하였을 때, On은 On-1에서 두가지 방법중 하나를 선택한 결과만 올 수 있기 때문이다.)

 

아래는 위의 논리에 따라 구성한 결과 코드이다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool answerFound = false;
void Solution(string o, string t)
{
	if (o.size() == t.size())
	{
		if(o.compare(t) == 0)
			answerFound = true;
		return;
	}

	if (t[t.length() - 1] == 'B')
	{
		reverse(t.begin(), t.end());
		t.erase(t.begin());
	}
	else
	{
		t.pop_back();
	}

	Solution(o, t);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string o, t;
	cin >> o >> t;

	Solution(o, t);
	cout << (answerFound) ? "1" : "0";

	return 0;
}

 

4. 후기

개인적으로 그리디는 DP와 함께 항상 여기에 이 알고리즘을 쓰는게 맞나? 하는 의문이 드는 곤란한 문제들이다.

알고리즘 개념에 대해 공부해보았으니 여러 그리디 알고리즘을 풀어보면서 감을 익혀야겠다.

 

5. 참고 링크

https://velog.io/@vicpillon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-algorithm