
프로그래머스 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)
리스트 컴프리헨션으로 코드를 짰다.
여기서 배울 점
- 리스트 컴프리헨션
- for loop 으로 나온 요소를 변수 지정 후 if 문으로 하나씩 체크
- 리스트에서 특정 요소 빼는 코드
list.remove(factor)
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges