Baekjoon Training / Algorithm-Greedy / #1439

 

 

---

#1439

 

 

 

 

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int zero;
int one;

int main() {
	string input_binary;
	cin >> input_binary;

	for (int i = 0;i < input_binary.size();i++) {
		if (input_binary[i] != input_binary[i + 1]){
			if(input_binary[i]=='0') zero++;
			else one++;
			}
	}

	cout << min(zero, one);

	return 0;
}

 

 

 

Greedy Algorithm이란?

 

: 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법으로, 최적해를 구하는 데에 사용되는 근사적인 방법이다.

 

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달한다.

 

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만, 그리디 알고맂므을 적용할 수 있는 문제들은 지역적으로 최적이면서도 전역적으로도 최적인 문제들이다.

 

 

 

 

 

Greedy-algorithm 문제 해결 방법

1. Selection Procedure ( 선택 절차 ) : 현재 상태에서의 최적의 해답을 선택한다.
2. Feasibility Check     (적절성 검사) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. Solution Check         ( 해답 검사 ) : 원래의 문제가 해결되었는지 검사하고,
                                                            해결되지 않았다면 선택 절차로 돌아가서 위 과정을 반복한다.

 

 

 

Greedy-algorithm 적용 조건

조건 1, 탐욕적 선택 속성 ( Gredy Choice Property ) 
: 앞의 선택이 이후의 선택에 영향을 주지 않는다.

조건 2, 최적 부분 구조 ( Optimal Substructure ) 
: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.