구사과

(Different Class, 1995)

Problem : 사이클이 없는 유향 그래프 G = (V, E)가 주어졌을 때, 모든 정점을 덮는 최소 개수의 Path를 구하라.Solution : Path에 집착하면 안된다. 간선들로 풀어서 생각하자. Path 상의 간선이 X개면 N - X개의 Path로 커버 가능하니 선택된 간선의 개수를 최대화하면 된다. 간선을 최대화 할 때 제약 조건은 : 각 정점의 indegree에 선택된 간선이 오직 하나, outdegree 오직 하나인 형태로 구성되어야 한다는 것이다.이제 각 노드를 두개로 쪼개자. 하나는 indegree, 하나는 outdegree를 상징한다. 실제 그래프 상의 간선을 저 안에 잘 박아두면 이분 그래프가 생기니 이제 최대 매칭을 구한다. O(VE). https://en.wikipedia.org..

(Goo, 1990)lyrics : http://www.azlyrics.com/lyrics/sonicyouth/tunicsongforkaren.html 카렌 카펜터즈의 죽음이 꽤 유명한 이야기기는 하지만, 그의 생전 노래와 비교해 보면 참 충격적인 tribute이다. Goo 앨범 전체를 두고 봐도 참 우울한 노래. 이 글을 같이 읽어보는 것도 재밌을 것. http://dangerousminds.net/comments/kim_gordons_open_letter_to_karen_carpenter