프로그래머스 LV1 체육복(탐욕법 greedy)

프로그래머스 LV1 체육복(탐욕법 greedy)

2021, Apr 02    

프로그래머스 lv1 체육복(탐욕법: greedy)

그리디 알고리즘은 “매 선택에서 가장 최적인 답을 선택 하여 결과를 도출”하는 방법이다.

마시멜로 실험에서 예시를 설명할 수 있는데, 눈 앞에 마시멜로를 두고 15분을 참으면 2개를 먹을 수 있다고 하자.

지금 당장은 눈 앞에 있는 마시멜로를 먹는 것: 현재 가장 최적의 답 탐욕법

그러나 15분을 참으면 마시멜로 두개를 먹을 수 있었다는 점에서 ‘최적의 해‘는 아니었다.
즉 매 선택 순간마다 최적의 해를 찾는 그리디 알고리즘이 최종 결과 또한 최선의 결과가 나온다는 보장은 없다.(100% 최적해를 보장해주지 않는다)

그리디 알고리즘은 어떨때 가장 잘 작동하는가?

  • 탐욕 선택 속성(greedy choice property)
  • 최적 부분 구조(optimal substructure)
    특성을 가지는 문제들을 해결하는데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값 이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.(출처:나무위키 그리디 알고리즘)

풀이

# 다른 사람 풀이
def solution(n, lost, reserve):
    set_reserve=set(reserve)-set(lost)
    set_lost = set(lost)-set(reserve)
    for i in set_reserve:
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
    return n-len(set_lost)

if __name__ == "__main__":
#     n, lost, reserve = 5, [2,4], [1,3,5] #return = 5
    n, lost, reserve =  5, [2,3, 4], [3] #return = 4
#     n, lost, reserve = 3, [3], [1] #return = 2
    print(solution(n, lost, reserve))

위 코드에서 배울 점

list - list 연산은 가능하지 않지만
set()-set() 으로 집합간에 차집합은 계산이 가능하다.
중복이 없다고 써져있는 문제의 조건들로 인해 이런식으로 계산해도 된다는 부분이 있었던 것임.

# 다른 사람풀이 2

def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

리스트 컴프리헨션으로 코드를 짰다.

여기서 배울 점

  1. 리스트 컴프리헨션
  2. for loop 으로 나온 요소를 변수 지정 후 if 문으로 하나씩 체크
  3. 리스트에서 특정 요소 빼는 코드 list.remove(factor)

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges