그리디 알고리즘(Greedy Algorithm)
일명 탐욕,욕심쟁이 알고리즘
“매 선택에서 현재 당장 최적인 답을 선택하여 적합한 결과를 도출하는” 근시안적 문제 해결 방식이다.
매 순간마다 하는 선택은 지역적(그 순간에서)으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었을 때, 그것이 최적이라는 보장은 없다.
즉 그리디 알고리즘을 통해 최적 값을 구하기 위해서는 적용 대상 문제가 최적 부분 구조를 가지는 문제여야 한다.
조건
탐욕스런 선택 조건(greedy choice property)
앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조 조건(optimal substructure)
각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 알 수 있음
- 최적 부분 구조를 가지는 알고리즘으로는 분할 정복, 그리디, 동적 계획법이 있다.
이러한 조건이 성립하지 않는 경우에는 그리디 알고리즘으로 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능하며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우로 구한 해(solution)또한 어느 정도까지 최적해에 가까운지 보장하려면 엄밀한 증명이 필요하다.
어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이러한 구조를 매트로이드라고 한다고 한다.
대표적인 그리디 알고리즘 문제로 동전 거스름돈 문제가 있는데, 그리디 알고리즘을 통해 나온 해가 최적해임을 보장하기 위해서는 각 동전의 가치가 배수 관계여야 한다.
이에 대해 설명해주는 문제는 다음과 같다.
예시 문제
문제 링크 : 백준 1439 뒤집기
문제
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
- 전체를 뒤집으면 1110011이 된다.
- 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
풀이
목표는 다솜이가 해야하는 행동의 최소 횟수를 출력하는 것이다.
공유하는 방식 외에도 다양한 풀이가 있으나, 그나마 greedy 하다고 생각하는 풀이를 공유해보겠다.
단순하게 생각해 보았을 때, 0으로 이루어진, 1로 이루어진 각 부분을 counting하여 가장 개수가 적은 숫자를 모두 뒤집는다면, 가장 적은 횟수(최적)로 뒤집을 수 있을것으로 생각된다.
1
2
3
4
5
6
import re #정규표현식 작성을 위한 패키지
from collections import Counter
input_string = input()
compressed_string = Counter(re.sub(r'(.)\1+', r'\1', input_string)) #정규 표현식을 통해 10001을 101로 변환 가능
# 변환된 문자열을 Counter에 넣어 각 숫자의 개수를 count
print(min(compressed_string['0'],compressed_string['1'])) #0의 개수, 1의 개수 중 가장 적은 것을 출력