그리디

그리디 알고리즘

그리디 알고리즘은 각 단계(부분 문제)에서 가장 최선의 선택을 하는 알고리즘 설계 기법이다.

그리디 알고리즘은 어떠한 공식 없이 창의력을 요구하는 유형이다. 그렇기에 문제를 풀기 위한 최소한의 아이디어를 떠올려야 할 필요가 있다.

그리디 알고리즘은 탐욕 선택 속성, 최적 부분 구조 특성을 가지는 문제들을 해결하는 데 강점이 있다.

예를 들어 서울부터 대구까지 가는 경로 3개가 각각 200, 250, 300km이고, 대구에서 부산으로 가는 경로 2개가 각각 100, 150 이라면 서울에서 대구 까지의 최소 거리인 200, 대구에서 부산으로 가는 최소 거리인 100을 골라 최종적으로 최소 거리 300을 구하는 것이 최적 부분 구조 문제를 해결하는 것이다.

예시) 백준 #1439 뒤집기

이 문제는 0과 1로만 이루어진 수열을 구간을 정하여 뒤집어 모든 숫자가 같게 하는 최소 횟수를 구하는 문제이다.

#include <iostream>
using namespace std;
string s;
int main() {
	int n, c1 = 0, c0 = 0;
	cin>>s;
	n = s.length();
	
	//첫번째 값 확인
	if(s[0] == '0') c0 = 1;
	else if(s[0] == '1') c1 = 1;
	
	//값이 바뀔 때 마다 이전 숫자의 카운트 올리기
	for(int i = 0 ; i < n ; i++) {
		if(s[i] != s[i+1] && s[i] == '0') c0++;
		else if(s[i] != s[i+1] && s[i] == '1') c1++;
	}
	cout<<min(c0,c1);
}

위와 같이 수열의 수가 바뀔 때 마다 그 전의 수의 카운트를 올린 뒤 그의 최솟값을 출력하면 된다.

예를 들어 수열이 11001101 이라면

c1 = 3, c0 = 2 가 나와 최소한의 뒤집는 횟수는 2가 되게 된다.