나의 큰 O는 log x야

일반 편집거리 알고리즘은 한글에 부적합하다두 텍스트가 얼마나 유사한지를 판단하는데 편집거리 알고리즘이 널리 쓰입니다. 주어진 텍스트 A가 B로 바뀌기 위해서는 글자를 몇번 빼고 더하고 바꿔야하는지를 세는 방법인데요, 이미 이를 효율적으로 계산하는 코드들이 인터넷 상에 많지요. 다만 한글에 이를 그대로 적용하는데에는 애로사항이 있습니다. 로마자 알파벳은 입력하기 위해 사람이 누르는 자판과 실제 입력되는 글자가 같은 반면, 한글은 그렇지 않다는 것이지요. 한글을 입력하는데에는 대게 두벌식 자판을 이용해 자음/모음을 따로 입력하고, 이를 입력기에 합쳐서 글자를 만들어내는 과정을 거치게 됩니다. 따라서 "갔다"와 "갓다"는 실제로 Shift키 하나 차이나는 텍스트임에도 불구하고 실제 입력된 결과물은 전체 글자인..

프로그래밍 2016. 12. 26. 03:25

BCD는 이진화십진코드(2진수 4비트를 묶어서 10진수 한자리를 나타내는 코드)의 약자. 따라서 BCD는 십진수로 표현하기가 쉽다. 하지만 일반적인 2진수는 10진수로 나타내는게 쉽지가 않다. 그래서 사용하는 알고리즘이 시프트 더하기 3 알고리즘, (double dabble)알고리즘이다. 이 알고리즘은 간단하게 설명하면 다음과 같다. 일반 2진수 코드를 왼쪽으로 1비트씩 시프트한다. 4비트씩 묶어서 5 이상이 되는 자리에는 3을 더해준다. 모든 비트가 다 왼쪽으로 시프트 될때까지 위 과정을 반복한다. log2=약 0.3010 이므로 십진수 한자리를 표현하려면 약 3.33비트가 필요하다. 예를 들어 이진수 11001100을 BCD코드로 변환해보자. 대략 BCD코드가 3자리 필요할거다. 0000 0000 0..

프로그래밍/테크닉 2008. 7. 10. 10:29