개발자 노트

그리디 접근 방법은 매우 명쾌하다. 매 step마다, 매 스텝에서 최적인 해를 찾는 것이다. 그런데 알다시피 문제는 이것이 global optimization을 만족하냐는 것이다. 그렇다면 가장 중요한 부분은 그리디 알고리즘으로 구한 해가 global optimization이 될 것인지 증명하는 것이라 볼 수 있겠는데, 이를 다루는 강의는 찾아보기가 매우 힘들다. 그나마 겨우겨우 찾은 곳이 아래 링크. https://hyunw.kim/blog/2018/09/18/Algorithm_Analysis07_GreedyAlgorithm1.html Algorithm Analysis - Greedy Algorithm 1 Interval scheduling 문제를 the greedy stays ahead 방식으로 풀어..

class PQ: def __init__(self): self.pq = [-1 for _ in range(100)] self.length = 0 def push(self,item): self.length += 1 i = self.length p = i // 2 while i != 1 and item