이번 포스팅에서는 Optimal Binary Tree 에 대해서 알아보도록 하겠습니다. Optimal Binary Tree에 대한 설명에 들어가기 앞서, Binary Search Tree 에 대해 짚고 가겠습니다. Binary Search Tree (BST) : Binary search 를 가이드 해주는 binary tree Binary Search Tree 의 각 Node 에는 array 의 Element 가 대응되며, 이것을 특별히 Key라고 합니다. (Tree 안에서 key의 값은 서로 다르다 가정합시다. 즉, Element 는 모두 distinct 합니다.) Non-Leaf Node k (= key 값이 k인 non-leaf node)는 다음과 같은 property 를 갖습니다. k의 left s..

앞선 Dijkstra 알고리즘이나, Bellman-Ford 알고리즘은 하나의 Source 에서 다른 모든 vertex 들 간에 shortext path를 구하는 알고리즘입니다. 이와 같은 문제를 single-source shortest path problem 이라고 합니다. 단일 source 가 아닌 임의의 모든 두 vertex u, v 에 대해 u에서 v로의 shortest path를 구하는 문제를 all-pairs shortest path problem 이라고 합니다. Directed Graph G = (V, E) 가 (undirected graph의 경우 bellman-ford 알고리즘과 같은 방법으로 directed graph로 변환하여) negative cycle이 없는 경우 G에서 all-pa..

Shortest Path 를 구하는 대표적인 Alogorithm 으로는 Dijkstra Algorithm 이 있었습니다. Dijkstra 알고리즘의 key lemma 는 다음과 같았습니다. Dijkstra Algorithm 에서 (아직 방문 안 한 vertex 들 중) vertex s 에서부터의 shrotest path 길이가 가장 짧은 vertex 를 v라 하면 그 길이는 실제 s에서 v로의 shortest path 길이와 같다. 위 key lemma 는 weight 가 negative 인 edge 가 존재할 경우 성립하지 않습니다. 그 이유는 다음과 같습니다. 그렇다면 negative edge 가 있는 경우에도 동작하는 Shortest path 를 구하는 Algorithm은 무엇이 있을까요? The ..

저번에 다룬 Problem 개념을 재정의하겠습니다. Problem Instance 는 일종의 binary string 이라고 생각할 수 있습니다. (Instance 가 Binary Code로 전환되었다고 생각합시다.) Problem 을 다음과 같이 재정의하도록 하겠습니다. Problem : 어떤 조건을 만족시키는 ( = YES 라 답하는 ) Problem Instance 들의 set. 그러므로, Problem 에 속한 Instance 는 모두 YES Instance가 됩니다. 어떤 Problem X 에 대해 어떤 mapping A 가 임의의 s ∈ X 에 대해 A(s) = YES이고, 역도 성립할 경우 A를 Problem X를 해결하는 Alogrithm 이라고 합니다. 이제 NP - Completenes..