[Algorithm] Greedy(그리디)

그리디란?

 

탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 시간적으로 매우 효율적이지만 모든 순간 답이 되는 방법은 아니다.

 

그리디의 특징

• 순간의 최적해가 전체 문제의 최적해가 되어야 한다.
• 입력 범위가 큰 경우가 많고 문제에서 요구하는 답에 '최소', '최대'란 말이 주로 들어간다.

그리디의 성립조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

---

문제 해결 아이디어 : 두 수에 대한 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱한다.

def solution(N):
    result = int(N[0])

    for i in range(1,len(N)):
        num = int(N[i])
        if num<=1 or result<=1:
            result+=num
        else:
            result*=num
    return result

print(solution('02984'))

---

출처 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2