허프만 코드와 데이터 압축 컴퓨터는 문자를 그대로 이해하지 못한다. 따라서 문자를 컴퓨터가 이해할 수 있도록 숫자로 바꾸어주어야 한다. 문자를 숫자로 변환하는 것을 '인코딩' 숫자에서 다시 문자로 변환하는 것을 '디코딩' 이라고 한다. 예를 들어 아래와 같은 규칙의 코드 표가 있다면 a,b,c,d 4개 문자로 구성된 아래 문자열을 그 아래처럼 인코딩할 수 있다. 13자리 문자열이 26자리 bit 리스트로 인코딩되었다. Prefix-Free code 문자열을 인코딩할 때 사용하는 코드 표는 다른 규칙의 코드표를 사용해도 된다. 이런 코드 표를 사용하더라도 문제없이 인코딩과 디코딩이 가능하다. 이때, 각각의 bit 가 선택됨에 따라 어떤 문자를 가리키게 되는지를 이진트리로 나타낼 수 있는데 위와 같이 나타난..
동적 계획법은 어떤 값을 구할 때 반복적으로 이미 구했던 값을 사용하는 경우, 이 값을 미리 기록해두었다가 활용하는 방법의 알고리즘이다.동적 계획법은 대체로 재귀 형태의 점화식을 가지는 문제를 해결하는데 유용하게 사용할 수 있다. 이항 계수이항계수는 nCk 조합의 경우의 수를 구하는데 사용된다. 이항 계수의 값은 위와 같이 계산한다.이때 이항 계수 nCk 를 각각의 값에 따라 쭉 표를 그리듯 그리면 아래와 같이 그려진다. 이 삼각형을 가리켜 '파스칼 삼각형' 이라고 한다.파스칼의 삼각형에 따르면 이항 계수는 아래와 같은 성질을 지닌다. 이항계수의 값이 다른 이항계수의 값을 이용해 재귀적으로 표현됨을 알 수 있다.이 공식을 그대로 함수로 옮기면def binom(n,k): i..
분할 정복은 말 그대로 주어진 문제를 분할하고, 분할한 조각을 정복(해결) 하는 방식으로 해결한다. 그리고 이 과정은 재귀적으로 발생한다. 지난 글에서 정리한 피보나치 수열도 그 값을 구할 때 '재귀'를 주요 아이디어로 활용하였듯, 분할 정복도 다른 관점에서 재귀를 활용하는 알고리즘이다. 이제부터 다양한 분할 정복 알고리즘과 그들의 시간복잡도를 구해본다. 카라츠바 곱셈 계산 (Karatsuba Method) 일반적인 곱셈 계산 곱셈은 덧셈의 반복이므로, 먼저 덧셈을 하는 과정을 생각해보자. 1234와 5678을 더한다면 일반적으로 아래와 같은 과정으로 진행된다. 두 피연산자는 정렬되어있어 i번째 자릿수는 같은 열에 위치한다. 각 자리수를 더해 만약 올림(carry)이 발생한다면, 다음 자리수에 넘겨 함께..
지수 base convention 알고리즘에서 제일 중요한 지수의 base 는 '2' 이다. 따라서 앞으로 아래와 같은 컨벤션으로 로그를 작성한다. 여기에 더해 log x 는 밑이 10인 로그를 의미한다. Ceiling, Floor 만약 문맥상 반드시 정수가 와야하는데, Ceiling, Floor 기호가 빠져있다면, 어떤 나눗셈에 대해 Floor 가 적용된 것으로 본다. “For the number of inputs n, the running time T(n) = 2T(n/2) + 1.” 라는 문장의 의미는 “ · · · , T(n) = 2T(⌊n/2⌋) + 1.” 라는 의미와 같다. Notation big-O 는 g(n) 이 f(n) 보다 항상 크거나 같다. 즉, g(n)이 f(n)의 최악이다. big..
