thoughts/Computer Science 썸네일형 리스트형 Paths, Trees, and Flowers presentation Matching in graphs is a subset of edges with no shared endpoints. and a maximum matching is a matching of maximum size among all matchings in a given graph. Edmonds represented the first such algorithm in his famous paper "Paths, Trees, and Flowers" in 1965. 더보기 Ternary Search Ternary Search(터너리 서치)는 함수의 최대나 최소점을 찾는 알고리즘으로 바이너리서치와 그 동작방법이 비슷하다. 터너리 서치로 최대점을 찾을 수 있는 함수는 최대점을 기준으로 왼쪽은 단조증가 오른쪽은 단조감소 해야한다. 마찬가지로 최소점을 찾을 수 있는 함수는 최소점을 기준으로 왼쪽은 단조감소 오른쪽은 단조증가 해야한다. 다시말해 지역 곡소점이나 극대점이 반드시 하나 존재해야 하고 이 점이 전역 최대나 최소점이 되어야 한다. 최대점을 찾아보자 a < b 인 두 점 a, b 가 있고 함수 f(x)의 최대점이 a와 b사이에 있다고 했을 때 a < a' < b' < b 인 a'과 b'을 잡을 수 있다. 이때 f(a') < f(b') 이라면 [a, a'] 구간은 단조증가하고 이 구간에 f(b') 보다.. 더보기 External Path Length IPL(Internal Path Length): Binary Tree의 각 노드의 depth의 합 EPL(Extend Path Length): Extended Binary Tree에 새로 추가된 노드들의 depth의 합 위 그림에서 왼쪽의 트리가 원래의 Binary Tree이고 오른쪽의 트리가 Extended Binary Tree이다. 오른쪽의 트리에서 동그라미로 그려진 노드가 Internal이고 네모로 그려진 노드가 External노드, 즉 원래의 Tree를 Extended Binary Tree로 만들기 위해 추가된 노드들이다. IPL은 동그라미로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값이 11이 된다. EPL은 네모로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값은 25이다.. 더보기 이전 1 다음
