[Python] 탐욕 알고리즘(greedy algorithm)
탐욕 알고리즘(greedy algorithm)
코딩 테스트를 준비하다가 어떤 문제를 greedy algorithm을 통해 풀었다는 글을 읽고
공부해보았다. 간단히 정리하면 현재 선택할 수 있는 경우의 수 중 가장 좋은 것을 고르는 것
이라고 할 수 있겠다.
https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
zerocho님의 블로그를 통해 공부했고 해당 코드가 javascript여서 python으로 다시 짜보았다.
activity = [[1,1,3], [2,2,5], [3,4,7], [4,1,8], [5,5,9], [6,8,10], [7,9,11], [8,11,14], [9,13,16]] def activitySelection(act): result = [] sortedAct = sorted(act, key=lambda x: x[2]) last = 0 for i in sortedAct: if last < i[1]: result.append(i) last = i[2] print("선택된 Activity: ", result) result = list(map(lambda x: x[0], result)) return result print("선택된 Activity Number: ", activitySelection(activity))
코드 Gist: https://gist.github.com/ChungminPark/0fe9939e08fbdf34871e6cbf1f67160c
0 comments