SLENDER ANKLES's 개발블로그

허프만 코드 알고리즘은 압축 알고리즘 중의 하나이다.

알집 역시 허프만 코드 알고리즘으로 한 번 압축하고 난 후에, 

Lempel이라는 알고리즘으로 한 번 더 압축한다고 한다. 

그만큼 실제로도 허프만 코드 알고리즘은 압축 알고리즘에서 중요하다는 말!

허프만 코드 알고리즘에 대해서 소개

자주 쓰이는 문자에 작은 bit를 비교적 덜 쓰이는 문자에 큰 bit를 할당해서 문자열을 전체적으로 압축하는 

개념이다.

예를 들어, AABBAC에서 

A => 3번

B => 2번

C => 1번

출현한다. 

가장 많이 사용하는 A에는 0을,

그 다음 B에는 01, C에는 11을 부여해

A(0)A(0)B(01)B(01)A(0)C(11)로 만든다.

=> 000101011

영문자 하나는 1byte이기 때문에 6byte가 사용되었다. (6 * 8 =  48 bit)

압축된 허프만 코드는 9bit가 된다. 

9/48 = 0.18     => 20%로 압축된다!

허프만 코드의 작동 방법?

예를 들어, CDDCACBCBCCCBBCDA라는 문자열이 있다.(총 17byte)

1) 빈도수 검사

2) 빈도수 대로 정렬(Repeat 1/2)

3) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

4) 빈도수 대로 정렬(Repeat 1/2)

5) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

6) 빈도수 대로 정렬(Repeat 1/2)

7) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

8) 트리 완성!

허프만코드 작성

가장 윗 트리에서 빈도수가 큰 트리에 0을 작은 트리에 1을 부여

위(최상위) 트리 노드를 기준으로 비트를 참조한다.

부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉, 

D => 000

A => 001

B => 01

C => 1 

디코드 하는 방법?

호프만 트리를 타고 내려가면서 문자를 만나면 치환을 한다.(복호화 과정)

1000000100110110111101011000001

최상위 노드를 기준으로 비트의 수를 따라가며 알파벳을 만날 때까지 따라간다.

1(C)/000(D)/000(D) ..........

=> CDDCACBCBCCCBBCDA 가 된다!

참조 http://wooyaggo.tistory.com/95

앞써 설명했던 최소 비용 스패닝 트리를 구하는 알고리즘 2번째, 크루스칼 알고리즘이다.

크루스칼 알고리즘 역시 Greedy 알고리즘의 방법으로 구한다. 

크루스칼(Kruskal) 알고리즘

로직은 다음과 같습니다.

1. 비용을 기준으로 간선을 적은 것부터 큰 것 순으로 정렬한다.

2. 적은 비용의 간선부터 하나씩 그린다.(사이클을 만들게 되는 간선은 그리지 않는다)

3. 모든 정점이 선으로 연결될 때까지 2의 과정을 계속한다.

1) 그래프가 주어집니다.

2) 가중치가 낮은 엣지들 순으로 정렬합니다.

3 - 1) 가중치가 낮은 엣지들을 순으로 엣지를 선택해줍니다.

3 - 2) 사이클이 발생하면 사이클 중에 가장 가중치가 높은 선을 선택하지 않고 넘어갑니다.

4) 모든 노드들이 엣지로 연결되면 최소 비용 스패닝 트리가 완성됩니다. 

엣지의 개수는 (노드의 개수 - 1)입니다.

최소 비용 스패닝 트리

그래프의 서브 그래프 중에 모든 vertex를 가지고 있고, edge를 가지는 것을 스패닝 트리라고 한다.

가중치가 있는 그래프에서 이러한 스패닝 트리 중에서 최소 비용인 것을 최소 비용 스패닝 트리라고 한다. 

신장 트리의 중요한 요건

하나, 순환이 되어서는 안 된다.

잠시만!!

최소 비용 스패닝 트리는 실제로 어디에 쓸 수 있을까? 맹목적으로 알고리즘을 배우고 외우는 것 보다 어디에 쓰일 수 있는지에 대해서 알면 좀 더 필요서이 생길 것 같다. 

필요한 상황에 대해서 한 번 예를 들어보겠다. 우리가 위치기반 서비스를 통해 가장 서울 지역 관광 명소를 현재 위치를 기반으로 최소의 거리 비용으로 돌 수 있는 서비스를 만들고 있다고 쳐보자.

위의 경우에 우리는 최소의 비용으로 관광지를 모두 돌 수 있는 알고리즘이 필요하다. 이러한 상황에서 최소 비용 스패닝 트리 알고리즘을 적용 해 볼 수 있을 것이다.

최소 비용 스패닝 트리를 구하기 위한 몇 가지 용어들에 대해서 알아두어야 한다.

트리(tree)정점 : 지금까지 만든 트리에 속하는 정점

주변확인(fringe) 정점 : 트리에는 속하지 않고, 트리에 속한 정점과 인접한 정점

미확인(unseen) 정점 : 나머지 정점들

프림(Prim) 알고리즘

모든 정점을 미확인 정점으로 초기화한다.

임의의 정점 s를 출발정점으로 한다. 

s에 인접한 모든 정점을 주변 정점으로 둔다. 

while(주변 정점이 있으면)

{

트리 정점 t와 주변 정점들 사이의 최소 가중치를 가진 에지 tv를 선택한다.

v를 트리 정점으로 둔다. 에지 tv를 트리에 추가한다.

v에 인접한 모든 미확인 정점을 주변정점으로 한다. 

}

다음의 그래프를 통해 prim알고리즘을 통해 greedy한 방법으로 최소비용스패닝트리를 구하는 과정을 설명하겠다.

이진탐색

이진탐색이란 한 번 비교를 거칠 때마다 탐색 범위가 반(1/2)으로 줄어드는 탐색 방법입니다. 순차탐색에 비해 얼마나 빠른 알고리즘이냐면 70억 명 중에서 특정한 정보를 탐색하려 할 때, 순차 탐색은 평균적으로 35억 번을 비교하고, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다.

이진 탐색 과정

1~7까지 정렬되어 있는 수에서 5를 찾는 과정이다.

1~7까지의 정렬된 수가 주어짐

1) mid 값 = (0 + 6) / 2 = 3 

[3]의 값인 4보다 찾고자 하는 값이 큼

2) 인덱스 4~6까지 검색, mid값 = 5

[5]의 값인 6보다 찾고자하는 값이 더 작음

3) 4 ~4까지 검색, mid 값 = 5

찾고자하는 값을 찾음

총 3번의 비교 연산이면 원하는 값을 찾을 수 있음!

이진 탐색의 성능

데이터 집합의 크기를 n으로 두고, 반복 횟수를 k로 둔다면 아래와 같은 수식이 만들어 진다.

n x (1/2)k = 1

n x 1/2k = 1

n = 2k

k = log2n

이진 검색의 구현

Iterative한 구현

recursive한 구현

쉘정렬(Shell Sort)

쉘 정렬은 삽입정렬의 단점을 보완하기 위해 만든 정렬 방법이다.

“삽입 정렬을 하기 전에 미리 정리를 해놓자!”

어떻게 정리를 한단 말인가?

삽입 정렬은 모든 원소에 대해서 검사를 하지만, 쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고, 그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다.

간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다.

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같은 수들이 있다. 간격을 5, 3, 1로 놓고 삽입 정렬을 시작할 것이다.

1) 간격이 5일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43

위와 같다.

묶음 1 : 45, 44, 77 => 44, 45, 77

묶음 2 : 39, 33, 68 => 33, 39, 68

묶음 3 : 98, 28, 11 => 11, 28, 98

묶음 4 : 15, 40, 43 => 15, 40, 43

묶음 5 : 52, 38 => 38, 52

각 묶음으로 정렬을 수행 한다.

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

2) 간격이 3일 경우, 같은 묶음 끼리 같은 색으로 표시해보면

44, 33, 11, 15, 38, 45, 39, 28, 40, 52, 77, 68, 98, 43

묶음1 : 44, 15, 39, 52, 98 => 15, 39, 44, 52, 98

묶음2 : 33, 38, 28, 77, 43 => 28, 33, 38, 43, 77

묶음3 : 11, 45, 40, 68 => 11, 40, 45, 68

각 묶음으로 정렬을 수행한다.

15, 28, 11, 39, 33, 40, 44, 38, 45, 52, 43, 68, 98, 77

3) 간격이 1일 경우

보통의 삽입 정렬을 수행한다.

그렇다면 간격은 어떻게 설정하나?

간격을 어떻게 설정하는지에 따라서 성능에 중요한 영향을 끼친다. 배열의 길이를 토대로 잡는다면

첫 번째 간격을 N/2, 두 번째 간격을 N/4 ... 등으로 잡는 방법이 있다.

시간 복잡도?

삽입정렬의 O(n^2)보다는 우수하지만 가장 효율적인 정렬 알고리즘의 O(nlogn)에는 미치지 못한다.

O(n^(4/3)) 정도이다. 또한 increments sequence를 어떻게 하느냐에 따라 성능이 좌우되는데 sequence가 좋지 않는 최악의 경우 복잡도는 O(n^2)가 되어 버린다.

퀵정렬(Quick Sort)

데이터 집합 내에서 한 피벗 값(pivot value)을 고른 다음 그걸 기준으로 두 개의 부분집합으로 나눈다.

한 쪽 부분집합에는 피벗 값보다 작은 것만, 다른 부분 집합에는 큰 것만 넣는다. 더 이상 쪼갤 부분집합이 없을 때

까지 각각의부분집합에 대해 피벗/쪼개기 작업을 재귀적으로 적용한다. 그렇게 하고 나면 최종적으로 정렬된 데이

터 집합이 만들어진다.

퀵정렬의 효율

퀵정렬은 어떤 피벗 값을 고르는지에 따라 성능이 결정된다. 가장 이상적인 피벗 값 은 전체 데이터를 절반씩으로

쪼갤 수 있는 값이다. 피벗 값을 고르고 배열을 쪼갤 때마다 각 원소에 대해 상수 시간 연산을 적용해야 한다. 각 

원소마다 이 작업을  몇 번씩 할까? 최선의 경우는 재귀호출이 이뤄질 때마다 부분 리스트의 크기가 절반씩으로 

줄고, 부분 리스트의 크기가 1이 되면 재귀호출이 끝난다.즉 각 원소에 대해 상수 시간 연산을 하는 횟수 n, n을 

1이 나올 때까지 반복해서 2로 나누는 횟수, 즉 log(n)이다. n개의 원소에 대해 log(n)번씩 연산을 수행하므로 최선

의 경우 복잡도는 O(n log(n))이다. 

하지만 피벗을 잘못 고르면 어떠게 되나?

최악의 경우라면 데이터 집합의 최소값을 피벗 값으로 고를 것이고, 그러면 한쪽 부분집합은 빈 집합이고 다른 집

합에는 n-1개 (피벗 값을 제외한 나머지)가 들어간다. 그러면 재귀호출 횟수가 O(n)이고(균형 전혀 잡히지 않은 

트리는 연결 리스트와 똑같아지는 것과 마찬가지), 최악의 경우 복잡도는 O(n^2)이 된다. 이는 선택 정렬이나 삽입 정렬과 마찬가지 속도다. 

어떻게 구현하나?

삽입정렬

한 번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새 원소를 제 위치에 삽입하는 식으로 정렬된 배열을 

만든다.

삽입정렬의 효율

삽입 정렬은 최선의 경우, 즉 리스트가 이미 정렬돼 있을 때, O(n)이다.

이미 정렬된 리스트에 새 원소를 추가할 때는 삽입 정렬이 매우 효율적이다. 

그러나 평균 및 최악의 경우에는 O(n^2)이기 때문에 무작위로 정렬된 많은 데이터를 처리하기에는 좋은 알고리즘은 아니다.

선택정렬

배열(또는 리스트)의 첫 번째 원소에서 시작하여 배열 전체를 훑으면서 가장 작은 키를 가지는 원소를 찾아서 첫 번째 원소와 맞바꾼다. 두 번째 원소로 넘어감녀서 마지막 원소에 이르기까지 같은 작업을 반복한다. 

선택정렬의 효율

비교 횟수를 따져보면 첫 번째 원소를 맞바꿀 때 (n-1)번의 비교, 그 다음 두 번째 원소에서 (n-2)번의 비교,

.... 1번의 비교가 수행되며, (n-1) + (n-2) + ... + 1 이므로 n(n+1)/2임을 알 수 있다. 

따라서 선택 정렬의 알고리즘의 최선, 평균, 최악 모두 O(n^2)이다. 

버블정렬이란?

인접한 두 수의 크기를 비교해 뒤로 큰 수(오름차순) 또는 작은 수(내림차순)를 뒤로 보내는 정렬 방법입니다.

시간복잡도는?

시간복잡도는 O(N^2)입니다. 모든 수에 대해서 N번만큼 비교를 하기 때문입니다. 

최악의 경우? O(N^2) 

최선의 경우? O(N^2)

보통의 경우? O(N^2)

공간복잡도는?

정렬을 위해 입력받은 배열 이외에는 특별한 저장공간을 할당할 필요가 없습니다. 

그래서 기존의 입력되는 배열인 N개만 필요하므로 O(N)입니다.

어떻게 구현하나?

재귀호출이란 무엇인가?

자신 자신을 호출하는 형태의 함수를 말한다.

어디에 쓰이는가?

같은 로직을 반복적으로 호출하는 작업에 많이 쓰인다. 정렬이나, 검색, 그래프의 종주에 보통 쓰인다.

재귀 함수는 어떻게 구성되는가?

재귀 호출은 자기 자신을 호출하여 하위 작업을 수행하게 되는데, 재귀 함수를 분석하고 설계하다보면 자기 자신을 호출하지 않고도 답이 나오는 하위 작업이 있다. 이를 base case라고 한다. 

쉽게 설명하자면 "Factorial에서 n이 1일 때는 1을 리턴해준다."

재귀 알고리즘에는 재귀 케이스(recursive)와 기본 케이스(base case)로 나뉜다. 이 두 개를 어떻게 잘 설계할 수 있는지 생각해보면 된다.

재귀 함수의 장점은 무엇인가?

재귀 함수는 보통 코드를 간결하게 만들어준다.

예를 들어 보겠다. 

팩토리얼을 구현하는  재귀적인 방법과  반복적인 방법이다.

재귀 함수의 단점은 무엇인가?

보통 팩토리얼과 같은 경우에 간단한 로직을 실행하는데 드는 비용보다 재귀함수를 스택에 쌓고 호출하는데 드는 시간적 비용이 더 많이 든다. 그래서 반복적인 루틴을 사용하는 코드보다 재귀적인 루틴을 사용하는 코드가 더 시간이 오래 걸린다.

보통 재귀함수로 실행 할 수 있는 로직은 반복적인 코드로도 만들 수 있다. 

재귀함수를 통해서 간결하게 코드를 만들 수 있는 예 - 이진 검색

예) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 있을 때 9를 몇 번만에 찾을 수 있을까?

이진 검색을 위와 같이 구현해봤다.

특정 범위의 시작과 끝, 또는 중간 값이 해당하는 값이면 탐색을 끝낸다. 

매번 인자에 재귀함수의 수행 횟수를 인자로 넘기는데, 답이 나오면 이 값을 리턴해주면 몇 번만에 검색 되었는지를 알 수 있다.

*참고 : 이진탐색의 시간복잡도와 특징*

이진 탐색(검색) 시간 복잡도 : Log(n)

특징 : 탐색 리스트가 정렬되어 있어야 된다는 점