[TIL] 탐욕 알고리즘 - Greedy Algorithm

탐욕 알고리즘

• 최적의 해에 가까운 값을 구함
• 매 순간 최적이라고 생각되는 경우
• 근사치 추정에 활용 -> 반드시 최적의 해를 구하는 것은 아님

 

 

관련 문제

1541번: 잃어버린 괄호 (acmicpc.net)

1541번: 잃어버린 괄호

식을 입력받아 괄호를 적절히 사용하여 값을 최소로 만드는 문제이다.

이 문제에서는 최소의 값을 구하는 것이 최적의 해를 구하는 것이므로 그리디 알고리즘을 사용하여 해결한다.

 

문제를 분석해보았을 때

- 다음 + 연산이 나올 경우 괄호를 사용하면 최소값을 구할 수 있으므로 이를 이용한다.

split()을 사용하여 - 를 기준으로 값을 입력받고 만약 중간에 + 연산이 있다면 그들의 합을 먼저 계산한다.

 

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

num=[]		# - 연산을 할 수를 담는 리스트

for i in n:
    cnt=0
    s = i.split('+')	#	+ 연산을 먼저 계산
    for j in s:
        cnt+=int(j)
    num.append(cnt)

start = num[0]
for i in range(1, len(num)):
    start -= num[i]

print(start)

 

 

백준에서 여러 문제를 풀어봤는데 생각보다 쉽지 않았다.

적응되려면 더 다양한 문제를 많이 풀어봐야 할 것 같다.