백준-그리디 알고리즘

1. 그리디(Greedy Algorithm)

최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 '각 단계에서 최적이라고 생각되는 것을 선택' 해 나가는 방식이다. 이 방법을 통해 최종적인 해답에 도달한다.
이때, 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 '근사한 값'을 목표로 한다.
다이나믹 프로그래밍(DP)과는 최적 부분 구조 문제를 푼다는 점에서 차이가 있다. DP가 하위 뭄ㄴ제에 대한 최적의 솔루션을 찾은 다음, 이를 이용한 전역 최적 솔루션을 찾는 것이라면, 그리디는 각 단계마다 지역 최적해를 찾는 문제로, 문제를 더 작게 줄여나가는 형태이다.

2. 예제: 백준 1541번

입출력1

입력: 55-50+40
출력: -35

입출력2

입력: 00009-00009
출력: 0

3. 해결

n = input()
m = n.split('-')

answer = 0
x = sum(map(int, (m[0].split('+'))))
if n[0] == '-':
    answer -= x
else:
    answer += x

for x in m[1:]:
    x = sum(map(int, (x.split('+'))))
    answer -= x
print(answer)

4. 풀이(예시)

1. 입력 받기

n = "55-50+40"

2. '-'로 분리

m = ['55', '50+40']

3. 결과 변수 초기화

answer = 0

4. 첫 번째 부분 계산

x = sum(map(int, ('55'.split('+')))) # 55
if n[0] == '-':
    answer -= 55 # 첫 부분은 '-'로 시작하지 않음
else:
    answer += 55 # answer = 55

5. 나머지 부분 계산

for x in ['50+40']: # 나머지 부분은 '50+40'
    x = sum(map(int, ('50+40'.split('+')))) # 50 + 40 = 90
    answer -= 90 # answer = 55 - 90 = -35

6. 결과 출력

print(-35) # 최종 결과는 -35