해나의 컴공생존기

1. Problem Definition J1, J2,...,JN 이라고 표기되는 N개의 job이 있다. 각 J는 (D,P) 로 쓰이는데, D는 deadline이고 P는Profit 이다. 1시간 단위의 타임슬롯이 있고 모든 일은 1시간이 소요된다 ex) (2,2) , (1,3), (1,1) 또, 이 문제는 아래의 가정을 따른다. 모든 deadlines은 N이하라고 가정한다. (N보다 크면 N으로 생각해도 됨) Job들은 내림차순으로 정렬되어있다. Deadline 이후의 일은 안나온다고 가정한다. 직관적으로 보면, 이익이 큰 것부터 최대한 뒤쪽에 배치하는 것이 효율적인 것을 알 수 있다. 최대한 뒤쪽에 두는것이 다른 Job들에게 방해가 될 가능성이 적어보이기 때문이다. 이것도 Greedy 알고리즘이다. 2...

1. Kruskal Algorithm 크루스칼 알고리즘의 기본 아이디어는 가장 작은 weight의 edge부터 하나씩 추가하는것이다. 단 사이클이 생기면 버리고 다음 weight의 edge를 확인한다. 위으 그림으로 예를 들어보겠다. 가장 작은 비용을 가진 edge는 1노드와 6노드를 잇는 10짜리 노드이다. 이것을 선택한다. 그 뒤로도 작은 순서대로 선택한다. 10, 12, 14, 16 이 다음으로 비용이 적은건 18이지만 18을 선택하면 사이클이 생기기에 그 다음인 22를 선택한다. 위와같이 사이클이 생기지 않게 작은 것들만 골라 spanning tree가 만들어지게 하면 된다. 증명 (proof by induction) 증명하기 전에 몇가지 가정을 이해해야한다. Tmst는 많은 정답 Edge set..