알고리즘을 공부하던중 재미있는 알고리즘을 발견해서 공부해보았다.

그것은 허프만 알고리즘.

허프만 알고리즘 Huffman

사용하는 빈도수의 따라 bit를 할당

자주쓰이는 문자에 가장 작은 bit를 할당

예를들어

HAN HA

이라는 문자열을 받으면

가장 많이 사용된 ‘H’에 0이라는 1bit를 부여하고

A에게 10, N에는 11을 할당한다.

(0)(10)(11) (0)(10)

당연히 중복된 문자가 많기 때문에 용량이 클수록 압축률은 올라간다.

코드부분

FileStream 부분

.txt 파일을 읽어 드리는 FileStream부분이다.

Header h = Compressor.Compress(bytes); 압축과정을 거친 후

h.Write(bf); 출력

압축과정

딕셔너리에 추가하면서 문자중복이라면 nVal(빈도수 )을 증가 시킨다.

노드를 만들어주는 과정 노드 빈도수의 합을 가지고 트리구조를 만듬

코드할당 부분 (01010) 왼쪽은 '0' 오른쪽 '1'

출력 코드 부분은 생략

보헤미안 랩소리 노래 앞부분을 txt파일에 넣음

빈도 수

사실 노래앞부분만 넣었을 경우 내용이 짧기 때문 압축이 되지 않았다. 

같은 문자를 여러번 복사해야 헤더가 물고있는? 문자들이 많이지기 때문에 압축률이 올라간다.

Linked List 링크드 리스트(연결리스트)

연결리스트는 노드와 링크로 구성이 된다. 

노드 : 실제의 정보를 담고 있는 하나의 단위

링크 : 인접 노드의 위치를 저장하고 있어 연결 리스트의 순서를 유지할 수 있게 하는 연결 고리

배열과 차이점

-배열과는 다르게 동적인 자료구조 => 메모리절약

배열은 여분의 공간을 마련해야 하지만 연결리스트는 필요할 때만 메모리를 할당 할 수 있다.

-배열은 연속된 공간을 차지 하는데, 연결리스트는 동적으로 수시로 할당 해제 되기 때문에 메모리의 연속된 공간을 차지하지 못한다. 순서도 제대로 되어 있지 않다.(이런 연결 리스트의 순서를 유지시켜 주는 것은 링크(Link)에 의해서 가능해진다.)

-자료 순서의 재배열이 편하다. (링크가 가리키는 방향만 바꿔주면 된다) 

연결리스트 종류

단순연결리스트

단순 연결 리스트는 정보를 저장하는 노드와 바로 다음의 노드를 가리키는 링크 하나로 구성 되어 있다.

제일 처음의 노드는 누가 가리켜 줄 것인가라는 문제 때문에 사용자에게 알려진 연결 리스트의 입구인 머리가 필요하다. 이 머리는 일반적으로 전역 변수로 선언이 되어 모듈 내의 어떤 부분에서도 접근 가능하도록 개방되어 있고, 소멸되지 않는다. 그리고 연결리스트의 제일 마지막 노드는 항상 무엇인가를 가리켜야 하는데 특별히 마지막을 나타내는 꼬리 노드를 만들어서 마지막 노드임을 표시하게 한다.

스택기반 노드 구현 연습

Node클래스 

연결리스트 초기화

노드 삽입

노드 삭제

원하는 노드 찾기

이중연결 리스트

이중 연결리스트는 단순 연결리스트와 함께 가장 많이 사용된다.

단순 연결리스트가 다음의 노드를 가리키는 하나의 링크를 가져서 바로 전의 노드를 알 수 없던 단점에 비해서,

 이중 연결 리스트는 다음의 노드를 가리키는 링크와 전의 노드를 가리키는 링크 두가지를 가져서 바로 전의 노드에도 접근할 수 있다. 

노드 클래스

단순노드와 다르게, 노드의 이전 노드를 가리키는 prev가 추가 됨.

노드생성

머리와 꼬리를 전역변수로 선언하여 공간을 할당하며 노드를 따라 이동하다가 연결 리스트의 외부로 벗어나어는 일을 방지하기 위해서 머리와 꼬리는 자기 자신을 가리키도록 설정한다.

노드 삽입

t노드 앞에 k값을 갖는 노드를 삽입한다.

노드찾기

노드삭제

정렬된 순서로 노드삽입

Stack 스택

스택,큐,트리와 같은 자료 구조는 자신이 행위적 측면을 포함하는 구조이다.

스택은 밑이 막힌 긴 통이라 생각하고 입,출구가 하나인 과자통을 생각하면 쉽다(프링글스)

 먼저 들어간 것은 가장 나중에 빠져 나오게 된다. (후입선출)LIFO

반대로 가장 늦게 들어간 데이터가 가장 먼저 빠져나가게 되는 것이다.

스택에는 구현방법이 배열구현과 리스트구현 두가지가 있다.

배열은 처음 배열의 크기를 설정해두고 시작해야 하기 때문에 나중에 배열의 크기를 변경 할 수 없는 반면에 리스트구현은 동적인 할당을 통해서 구현되기 때문에 연결리스트로 구현 하는것이 유연하다.

배열로 구현한 스택구조가 더 빠르다고 하는데 하드웨어가 발단된 지금에서는 별 차이가 없다.

그렇기에 이번 학습일지에도 리스트를 이용한 스택구현을 연습!

입출구가 하나이기 때문에 연단순결리스트로 쉽게 구현이 가능하다.

Node클래스

PUSH 데이터 노드 삽입

연결리스트를 이용 할 경우 TOP이라는 변수의 역할은 머리 노드가 대신한다.

머리노드의 다음 노드가 스택의 상단이 되는 것이다.

POP데이터 노드 삭제

후입선출이기 때문에 최상단 노드를 삭제한다.

머리노드의 다음 노드가 꼬리 노드이면 비어있는 스택이다. 

출력

POP하고 다시 출력

이진탐색트리(Binary Search Tree)

Queue 큐

큐는 스택과 다르게 앞뒤가가 뚫린 긴통이라고 보면 된다. 즉 입구와 출구가 다르다.

뒤에서 넣고 앞에서 꺼낸다. 그래서 먼저 들어간 것이 제일 먼저 나오는 FIFO구조이다.

큐를 조작하는 방법에는 put동작과 get동작이 있다.

put  : 뒤에서 넣음

get  :  앞에서 꺼냄

사진 : 위키백과

큐 구현방법에는 배열구현과 연결리스트 구현이 있다. 

큐노드 클래스

큐 초기화(이중연결 리스트)

Put

K의 값은 가지는 노드를 만들어 꼬리의 앞에 삽입한다. 

Get

큐가 비었는지 확인하고(머리노드 다음이 꼬리이면 꺼낼 노드가 없다)

C++같은 메모리 직접 관리가 가능한 언어는 당연히 메모리를 삭제했으니 메모리해제과정이 필요하다.

출력

확인

맨처음 put한 데이터가 맨 위에있다.

Get테스트

이진트리 구현

순회종류의 맞게 출력결과를 보기 위해 테스트해봤다.

트리는 목적/구성에 따라 맞는 순회방법을 결정해주어야한다.

테스트예제

레벨그림

결과

트리

어떤 요구조건을 만족하는 정점과 선분들의 비어있지 않는 집합

정점은 또한 노드라고도 표현한다.

노드 : 동그라미 하나하나 트리의 요소를 나타냄

루트노드 : 부모노드의 최상단

단말노트 : 자식이 없는 노드

서브트리 : 트리안에 존재하는 트리

트리의 높이 : 가장 최상단부터 레벨을 1,2,3이라 매긴다.

트리의 성질

트리에는 어떤 두 노드를 연결 하는 경로는 한개다. (부모-자식간 양방향의 경로가 있어도 경로는 한개)

어떤 두 노드는 최소 공통 선조를 지님.

루트가 최소공통선조가 되거나 근의 자식들중의 부분트리에 두 노드가 속하게 되므로 최소 공통선조는 항상 존재

각 노드가 최소공통 선조에 이르는 경로를 연결하면 두 노드간 최소 경로가 된다.

이진트리(Binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 가지는 트리 구조로,

 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

이진트리 순회방법

목적/구성에 따라 순회하는 방법이 다르다.(기준은 루트노드 기준)

1. 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

F, B, A, D, C, E, G, I, H (root, left, right)

2. 중위순회(Inorder) - 왼쪽서브트리 -> 루트 -> 오른쪽서브트리

A, B, C, D, E, F, G, H, I (left, root, right)

3. 후위순회(Posterorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

A, C, E, D, B, H, I, G, F (left, right, root)

Tree구조

naver

트리는 2차원적 비 선형구조이다. 

나무의 모양을 거꾸로 뒤집어 놓은 모양이다. 

뿌리가 가장 위에 있으며 가지(link)들은 밑으로 벌어지며 향한다.

트리구조에서 쓰는 용어

트리의 성질

-나무 구조에서 한 노드에서 다른 노드로 가는 경로는 유일하다.

(나무를 타는 경로가 중복되지않고, 되돌아감이 없다면)

나무구조의 임의의 두 노드는 최소 공통 선조(두 노드가 갖는 가장까운 부모 노드)를 갖는다. 

-N개의 노드를 갖는 나무는 N-1개의 링크를 가진다.

트리구조는 뿌리 노드를 제외하고 모든 노드가 자신의 선조를 향해 하나의 링크를 갖는다.

그래서 N개의 노드를 가진 나무는 N-1개의 링크를 가진다

-꽉 찬 이진트리는 레벨이 d라고 할때 노드의 수는 N이 다음과 같은 조건을 만족한다.

재귀호출

자기자신을 호출한다.

재귀적으로 문제를 해결함은 또 문제를 점점 더 작은 단위로 쪼개어 해결함을 의미한다.

잘못된 재귀 호출

문제 해결에 변화없는 호출

무한루프 -> 시스템 내부의 스택에 복귀주소와 인자를 저장해야 하기 때문에

스택에는 자료가 쌓인다.

재귀 호출의 요건

1. 거듭제곱을 구하는 재귀 함수

N의 거듭 제곱은 N!이라고 표현한다.

ex) 4를 넣었을때

4 x(3 x(2 x(1 ))) = 24

//0! 되면 재귀함수 탈출

2. 피보나치 수열 구하는 재귀 함수

한 함수 내에서 한번만 이루어져야 하는 것은 아니다.

한 함수 내에서 두 번 혹은 그 이상도 자기자신을 호출할 수 있다.

3. 하노이의탑

세 개의 기둥과 서로 다른 크기의 N개의 원반으로 구성된다. 이 원반들은 세 개의 기둥 중의 하나에 반드시 꽂혀 있어야하며, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없다.

즉 원반은 아래에 가장 큰 것이 와야하며, 자신보다 큰 원반은 자기 위에 놓을 수 없다.

N이 3일때

1. 기둥 1의 원반을 기둥 3으로 옮긴다

2. 기둥 1의 원반을 기둥 2로 옮긴다.

3. 기둥 3의 원반을 기둥 2로 옮긴다.

4. 기둥 1의 원반을 기둥 3으로 옮긴다.

5. 기둥 2의 원반을 기둥 1로 옮긴다.

6. 기둥 2의 원반을 기둥 3으로 옮긴다.

7. 기둥 1의 원반을 기둥 3으로 옮긴다.

재귀적 표현

1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

<결과>