[최컴특] 3. 컴퓨터 이론

문제 1.

alphabet의 크기가 A이고, 길이가 n인 수열을 가능한 적은 메모리로 저장하기. 단 access는 arraylist처럼 $O(1)$이어야 함.

문제 해결을 위해 n = 3, A가 10인 상황으로 생각해보자. (alphabet = {0, 1, ..., 9})

해결책 1.

각 integer에 대해 4비트로 저장. (일반적인 방법).

0 = 0000, 1 = 0001, ... 9 = 1001

수열 [0, 3, 6]을 저장하려면 [0000, 0011, 0110]로 저장되므로 총 메모리는 12 bits만큼 들어간다.

또한, 4비트 단위로 끊어 읽으면  access를 $O(1)$로 할 수 있다.

해결책 2.

가능한 모든 수열에 대해 순서대로 숫자를 부여함.

n = 3으로 가정하면 가능한 수열의 개수는 총 10^3개이다.

[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], ..., [9, 9, 8], [9, 9, 9]

10^3개의 수열에 전부 숫자를 부여해본다. [0, 0, 0]은 0, [0, 0, 1]은 1, [9, 9, 9]는 999, 이런 식으로

수열 [0, 3, 6]을 저장하려면 부여된 숫자 36을 저장하면 된다.

36을 이진수로 변환하면 100100이므로 총 메모리는 6 bits만큼 들어간다. 6 bits 이득

일반화하면 공간복잡도가 $O(n \log A)$.

n = 3, A = 10인 상황에서는 해결책 2가 메모리 측면에서 더 이득이다.

그러나 숫자를 통으로 들고 있으므로 access가 $O(1)$로는 불가능하다.

 

위 두 가지 해결책의 장점만 취한 방법이 2010년 발표되었다.

 

---

문제 2-1.

두 String이 얼마나 가까운지 나타내는 척도 "Edit distance"를 구해보자.

 

연산은 총 세 가지이다.

Insertion: S1의 임의의 위치에 symbol 하나를 추가 (ex. MONDT -> MONEDT)

Deletion: S1의 임의의 symbol 하나를 제거 (ex. MONEDT -> MONED)

Substitution: S1의 임의의 symbol하나를 변경 (ex. MONED -> MONEY)

 

Edit distance 재정의

String S1에 위의 세가지 연산을 최소한 몇 번 수행해야 S2로 만들 수 있는가?

해결책 1-1.

$O(n^2)$으로 해결.

DP로 해결할 수 있다.

문제 2-2.

$O(n^2)$보다 더 빠른 알고리즘은 존재하는가? 존재하지 않는다면 증명 가능한가?

해결책 2-1.

SETH가 거짓이 아니라면, $O(n^{2-\epsilon})$보다 빠르게 "edit distance"를 구할 수는 없다.

 

• $O(n^{2-\epsilon})$: $O(n^2)$보다 아주 미세하게 빠를 수 있음
• SETH: 3이상의 k에 대해 k-SAT을 해결하는데 대략 2^n시간이 필요
• k-SAT: CNF의 절 내의 변수가 k개인 경우. (ex. 3-SAT: (x1 U x2 U x3) n (x4 U x5))

---

문제 3-1.

Optimal binary search tree를 구성할 수 있는가?

가령 1, 2, 3으로 BST를 구성할 때, 2를 검색한다면

왼쪽의 BST는 search cost가 2지만,

오른쪽의 BST는 search cost가 1이다.

왼쪽은 Optimal하지 않다.

해결책 1-1.

정석적으로 BST를 구성하는 방법.

트리를 구성하는 시간복잡도는 $O(n\log n)$이다.

search cost는 Optimal과 $O(\log n)$만큼 차이난다. (트리 구성 시간복잡도와 search cost는 별개다.)

optimal하지 않다.

해결책 1-2.

Tango tree를 사용하는 방법

트리를 구성하는 시간복잡도는 $O(k \log \log n)$이다.

search cost는 Optimal과 $O(\log \log n)$만큼 차이난다.

정석적인 방법보다는 낫지만 여전히 optimal하지 않다.

결론

그렇다면 optimal한 tree를 찾는 것은 불가능한가?

-> 아직 미해결 문제.

문제 3-2.

그렇다면 offline으로 optimal한 BST를 구성할 수 있는가?

offline: 어떤 노드를 검색하는 횟수 f를 알고 있다고 가정

해결책 2-1.

DP를 사용하여 $O(N^2)$에 Optimal BST를 구성할 수 있다.

그러나 시간 복잡도가 너무 높다.

해결책 2-2.

Splay tree를 사용하여 $O(n \log n)$에 BST를 구성할 수 있다.

search cost는 Optimal과 $O(1)$만큼 차이난다.

시간 복잡도도 준수하고 cost도 Optimal과 비슷하다.