⊙ 동전 바꾸기!
이건 Greedy Algorithm을 설명하기 위해서 가장 많이 사용되는 예제인데, 1000원을 동전으로 바꿀 때, 가장 적은 수의 동전으로 바꿀 수 있는 경우는? 당연히, 500원짜리 2개이다. 900원을 동전으로 표현하면, 500원짜리 1개와 100원짜리 4개가 될 것이다. 여기에서는 Greedy algorithm을 사용하여, 가장 큰 동전부터 뽑아내면 된다.
⊙ Suffix Dictionary
Prefix Dictionary와 반대되는 개념으로, 각각의 phrase들의 suffix가 dictionary 내의 다른 phrase를 이루고 있는 dictionary이다.
Suffix Dictionary를 이용한 encoding 방법의 예를 들어보자. ∑={a,b,c}인 D={abc, bc, c, a, b, d, dac, ac}라는 suffix dictionary가 있고, 이것들은 각각 {0,1,2,3,4,5,6,7}로 encoding한다. 이때, D에 있는 모든 phrase들의 suffix는 다른 phrase의 suffix라는 것을 알 수 있다.
그러면 이 때, T=abcabdaccd 라는 입력값이 주어졌을 때, 가장 짧은 codeword를 얻을 수 있는 방법은? 정답은 바로, Greedy Algorithm을 이용하는 것이다. 단, 여기에서는 모든 codeword가 같은 수의 bit를 가진다는 것이다. 여기에서는 총 8개가 필요하므로, 3bit면 되겠다. 저 T를 가장 짧게 encoding하면, O=034625이다. (prefix와는 경우가 다르다. prefix에서는 greedy algorithm을 적용할 수 없다.)
이건 Greedy Algorithm을 설명하기 위해서 가장 많이 사용되는 예제인데, 1000원을 동전으로 바꿀 때, 가장 적은 수의 동전으로 바꿀 수 있는 경우는? 당연히, 500원짜리 2개이다. 900원을 동전으로 표현하면, 500원짜리 1개와 100원짜리 4개가 될 것이다. 여기에서는 Greedy algorithm을 사용하여, 가장 큰 동전부터 뽑아내면 된다.
⊙ Suffix Dictionary
Prefix Dictionary와 반대되는 개념으로, 각각의 phrase들의 suffix가 dictionary 내의 다른 phrase를 이루고 있는 dictionary이다.
Suffix Dictionary를 이용한 encoding 방법의 예를 들어보자. ∑={a,b,c}인 D={abc, bc, c, a, b, d, dac, ac}라는 suffix dictionary가 있고, 이것들은 각각 {0,1,2,3,4,5,6,7}로 encoding한다. 이때, D에 있는 모든 phrase들의 suffix는 다른 phrase의 suffix라는 것을 알 수 있다.
그러면 이 때, T=abcabdaccd 라는 입력값이 주어졌을 때, 가장 짧은 codeword를 얻을 수 있는 방법은? 정답은 바로, Greedy Algorithm을 이용하는 것이다. 단, 여기에서는 모든 codeword가 같은 수의 bit를 가진다는 것이다. 여기에서는 총 8개가 필요하므로, 3bit면 되겠다. 저 T를 가장 짧게 encoding하면, O=034625이다. (prefix와는 경우가 다르다. prefix에서는 greedy algorithm을 적용할 수 없다.)
