[하나라도 제대로] 그리디알고리즘(2)

1. 서론

강의링크: https://youtu.be/2zjoKjt97vQ

2. 본론

그리디 알고리즘은 '현재 상황에서 당장 좋은 것만' 고르는 방법을 의미한다.
코딩 테스트 문제에 기준에 따라 가장 좋은 것을 선택하는 알고리즘이므로 문제를 잘읽고 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 잡고 문제 풀이를 진행하자.

1) 예제문제: 곱하기 혹은 더하기

 

(1) 내코드

A. 0 혹은 1이면 곱셈보다는 덧셈이 유리
B. 문자열이 1개 밖에 없으면 자기 자신 리턴

def multiOrPlus(s):
    tmp = list(map(lambda x: int(x), list(str(s))))
    result = tmp[0]
    if len(tmp) == 1:
        return result
    else:
        for cur in range(1, len(tmp)):
            if result ==0 or result == 1 or tmp[cur] == 0 or tmp[cur] == 1:
                result = result + tmp[cur]
            else:
                result = result * tmp[cur]
    return result

print(multiOrPlus('567'))

정답!

(2) 모범답안

def multiOrPlus_dongbinna(s):
    tmp = list(map(lambda x: int(x), list(str(s))))
    result = tmp[0]
    for cur in range(1, len(tmp)):
        if result <=1 or tmp[cur]<=1:
            result += tmp[cur]
        else:
            result *= tmp[cur]
    return result

print(multiOrPlus('567'))

배울점

• 내 코드의 첫번째 if문에서 for문할때 어차피 돌지 않으므로 패스해도 됨.
• 0 또는 1 이 아니라 차라리 1보다 작을때가 더 깔끔
• result = result + tmp[cur] 가 아니라  result += tmp[cur] 와 같이 더 쉽게 쓸수 있다.

마무리

그리디 알고리즘, 2번째 문제  정답을 맞추기는 했으나, 코드 작성 효율성이나 코딩 속도면에서 부족하다 노력하자.