장난감

최소, 최대힙에 대해 설명하기 전에

이진힙에 대해 설명을 하자면 

트리로 만든 Heap 인데 완전이진트리여야한다는 조건이 붙는다.

이진 힙을 List로 생성해보자

1번 째 줄은 Index, 두번 째 줄은 원소 값이다.

여기서 부모, 자식간의 관계를 수식으로 나타낼 수 있는데

위와 같은 공식이 나오게 된다.

최소힙

최소힙은 부모가 자식보다 더 작은 값을 지니는 힙을 말한다.

최대힙

최대힙은 부모가 자식보다 더 큰 값을 지니는 힙을 말한다.

위에 있는 사진이 최대힙이다.

힙정렬

힙정렬의 알고리즘을 보자면

1. 정렬되지 않은 n개의 데이터를 입력 받는다.

2. 해당 데이터를 최대힙으로 구성한다.

3. root를 다른 list의 맨 끝으로 뺀다.

2,3번 반복

시간 복잡도는 O(n log n)이다.

트리의 순회

트리의 순회에는 3가지 방법이 존재한다.

1. 전위 순회

F->B->A->D->C->E->G->I->H

살펴보자면 Root 노드부터 왼쪽->오른쪽으로 탐색을 시작한다.

F를 방문 한 뒤, 왼쪽 자식인 B를 방문한다.

B의 왼쪽 자식인 A를 방문한 뒤, A는 자식이 없으므로 B의 오른쪽 자식 D를 방문한다.

D의 왼쪽 자식인 C를 방문 한 뒤, C는 자식이 없으므로 E로 넘어간다. E도 자식이 없으므로 

Root의 왼쪽 자식을 탐색한다.

2. 중위 순회

A->B->C->D->E->F->G->H->I

왼쪽 -> Root -> 오른쪽으로 탐색을 진행한다.

Root인 F의 왼쪽 자식인 B에는 또 왼쪽 자식이 존재하므로 A를 방문한다. 

A는 자식이 없으므로 A의 부모인 B를 방문. B의 오른쪽 자식인 D에는 왼쪽 자식 C가 존재한다.

C는 자식이 없으므로 C를 방문한 뒤, 부모인 D를 방문, 다음 E를 방문한다.

-반복

3. 후위 순회

A->C->E->D->B->H->I->G->F

왼쪽 -> 오른쪽 -> Root로 탐색을 진행한다.

귀찮다. 안적을래.

트리. Tree

자료구조에서 트리는 나무를 거꾸로 표현한 것 처럼 생겼다고 해서 트리라고 이름이 지어졌다.

트리는 뿌리(root)인 노드를 Level 1로 지칭하며 시작하며 뿌리 노드를 기준으로

자식 노드를 연결시켜 가지처럼 뻗어나가는 구조이다.

트리는 여러가지 종류가 있는데 대표적으로 Binary Tree, Normal Tree가 있다.

여기서 Binary Tree는 탐색, 힙 등 광범위하게 사용된다.

배우기 전에 용어를 정리해보자.

Root, 뿌리.

뿌리(Root)는 트리의 최상위에 존재하는 노드이며 Level은 1로 고정이다.

위 Tree에서 시초가 되는 '2'노드가 Root, 뿌리 노드이다.

(위 그림에서 '2'노드가 두번 나오는데, 가장 상위에 있는게 뿌리 노드이다.)

Child, 자식

Child, 자식노드는 어떠한 노드에 종속되어 있는 노드로

뿌리 노드를 기준으로 자식노드는 '7', '5'노드이다.

Parant, 부모

Parant, 부모노드는 자기 자신 노드 아래에 자식 노드가 있다면

해당 노드는 부모 노드가 된다.

예를 들어 '9' 노드의 부모는 '5'이다.

* 같은 부모를 가진 노드의 집합을 형제 노드라고도 칭한다.

Degree, 차수

Degree, 차수는 해당 노드에 연결된 자식 노드의 개수를 뜻한다.

트리에서 가장 큰 차수가 트리의 차수가 된다.

Level(Depth), 깊이, 레벨

Level, 혹은 Depth은 트리의 깊이 혹은 레벨을 뜻 한다.

위 그림에서는 최대 4 Level 혹은 4 Depth을 가지고 있다. 

트리의 최상 지점부터 1Level, 1 Depth으로 시작한다.

Height, 높이

트리에서 최대 Level 혹은 Depth을 의미한다.

해당 트리는 4의 높이를 가진다.

Stack과 Queue는 자료구조를 공부 했다면 100% 이해를 하고 넘어가야한다.

스케줄링, 알고리즘 등 많은 곳에서 쓰이는데 일단 개념부터 살펴보자.

Stack과 Queue는 뭘까?

두 자료구조 모두 데이터가 쌓이는 방식, 혹은 구조를 뜻한다.

역시나 글로는 이해가 잘 안될 것 같아 아래에 각각에 대한 설명과 사진을 첨부 했다.

1. Stack, 스택

Stack. 채우다. 쌓다 라는 뜻을 가진 단어이다.

자료구조에서도 마찬가지로 데이터를 순차적으로 쌓아준다.

또한 데이터를 빼낼 때는 마지막에 들어온 데이터부터 내보낸다.

즉, 후입선출( 혹은 선입후출 )의 구조를 지니게 된다.

쌓는 과정을 push, 빼내는 과정을 pop이라고 한다.

단점을 살펴보자면 Low level(먼저 들어온 데이터)의 데이터를 가져가려고 하면 

위에 존재하는 High level(나중에 들어온 데이터)의 데이터를 다 빼야지 가져갈 수 있다.

또한 스택의 크기를 동적으로 변경하지 않는 한 Overflow( 데이터가 들어갈 공간이 모자른 현상 )이 일어날 수 있다.

2. Queue, 큐

앞에서 봤던 Stack은 출구와 입구가 같다면, Queue는 출구와 입구가 별도이다.

따라서 들어왔던 것은 입구로 나가지 못하므로 늦게 들어오면 늦게 들어올 수록 나가는 속도는 늦어진다.

즉, 선입선출( 혹은 후입후출 )의 구조를 가지게 된다.

데이터를 넣는 것을 Enqueue, 데이터를 제거하는 것을 Dequeue라고 한다. ( 책마다 다를 수 있다. )

단점을 찾아보자면

Queue는 Dequeue를 실행하면 데이터를 당겨와야한다.

1->2->3->4 순으로 데이터가 들어왔다고 하면 Queue의 상태는 아래와 같다.

rear [4]-[3]-[2]-[1] front

이 때 Dequeue를 실행한다면 아래와 같이 변경 된다.

rear [4]-[3]-[2]-[null] front

만약 재배치를 해주지 않는다면 Dequeue를 충분히 많이 실행 했을 시

Enqueue를 하면 Overflow가 나타나게 된다.

rear [4]-[null]-[null]-[null] front

위와 같은 Queue가 구성되면 rear쪽이 비어있지 않다고 판단하여 Overflow를 내뱉는다.

실제로는 3 size나 비어있는데도.

따라서 재배치가 필요하다.

위와 같은 queue를 선형 큐라고 하고, 이 단점을 보완한 것이 원형 큐, 환영 큐 라는 것이다.

남는 메모리 공간을 없애기 위해서 rear과 front를 가르키는 변수를 추가해서 활용도를 높이는 방식인데, 

단점이라면 10 size를 가진 원형 Queue는 실제로 11 size을 지녀야되서 1 size가 낭비된다. ( full 과 empty를 구분하기 위한 공간 )

1size는 mod연산을 하면서 남는 공간이라고 생각하면 된다.

큐가 꽉 차있는 것을 판별하려면 

(rear+1) % Queue_Size == front 를 이용하면 된다.

원형 큐에 대한 내용은 따로 포스팅 해야겠다.

여기 가면 설명이 잘 되있으므로 참고해도 좋을 듯 하다.

사진 출처 : 나무위키(큐)

정리를 하기 위해 포스팅을 한다.

Linked List에서는 크게 3가지 유형이 존재한다.

1.  Single

2. Double

3. Circle

첫 번째로 Single Linked List

n번 째 블럭이 n+1번 째 블럭을 찾을 수 있는 Link를 가지고 있는 Node의 집합체이다.

Single인 이유는 n+1번 째 블럭은 n 번 째 블럭을 찾을 수 있는 Link가 없기 때문이다.

네트워크로 따지면 단방향이라고 볼 수 있다.

두 번째로 Double Linked List

Signle과 다른 점은 n 번 째 블럭은 이웃한 블럭을 찾을 수 있는 Link를 지니고 있다.

네트워크로 따지면 양방향이다.

세 번째로 Circle Linked List

앞에서 본 Single, Double은 모두 Head와 Tail이 존재한다.(시작과 끝)

하지만 Circle Linked List는 Head와 Tail이 연결 되어있는 순환구조이다.

사진 출처 : https://ko.wikipedia.org/wiki/연결_리스트

알고리즘 수업시간에 배운걸 끄적인다.

고차 다항식 계산을 프로그램에 적용한다면

몇몇 사람들은 식 그대로 사용할 지도 모른다.

예를 들어서.. 10x^3+5x^2+3x+6 = y 라는 식이 존재한다고 하면

C언어 기준으로 

라고 작성할 수 있다.(일부는 라이브러리를 사용하여 제곱 계산을 할 수도 있겠지만..)

하지만 Horner's role을 사용하여 계산 횟수를 줄일 수 있다.

식을 묶어버린다면,

(10x^2+5x+3)x+6 

=((10x+5)x+3)x+6

으로 변한다.

식을 다시 작성해 본다면

요렇게 바뀐다.

첫 번째 코드는 연산이 곱셈 6번, 덧셈 3번

두 번째 코드는 연산이 곱셈 3번, 덧셈 3번

곱셈이 무려 3번이나 줄어들었다.

다익스트라 알고리즘(dijkstra's algorithm)

두 정점 사이간 최소 거리를 구하는 알고리즘의 일종.

간단히 이론적인 것을 설명하자면..

N개의 정점을 모두 돌아다니는데 N과 연결된 정점을 찾아 거리를 계산해주는 것이다.

Start(시작점), End(도착점)이 존재하는데 각 점과 Start의 거리의 초기 값은 inf(무한대)이고

정점을 찾아다니며 최소 거리를 갱신하는 것이다.

-실제로는 inf 값을 넣지않고 큰 값, 혹은 일정한 값을 넣는다.(음수도 가능?할지도)

예를 들어 

정점 5개가 존재하고 각 정점을 0~4로 이름을 매긴다.

각 정점 간 관계는 아래와 같다.

또한 각 정점 간 거리는 아래와 같다.

 Start가 0, End가 3이라 놓는다면

0은 1과 2밖에 연결이 안 되어 있으니, 탐색은 0->1, 0->2로 시작된다.

이때 0->1, 0->2는 0으로부터 각 정점간 최단 거리이므로 3, 2가 최단거리가 될 것이다.

또한 1은 2와 3이랑 연결이 되어있다.

이때 탐색 루트는 0->1->2 , 0->1->3이 되는 것인데

0->1->2 루트의 거리는 5이고 이전에 0->2는 2이므로 최단거리 갱신이 안된다.

0->1->3 루트는 첫 탐색이므로 7이 최단거리가 된다.

0->2->3, 0->2->4 탐색을 해보자.

0->2->3 루트는 이미 0->1->3으로 0->3간 최단 거리가 설정되있다. 

하지만 0->2->3 루트는 거리가 3이므로 기존에 7보다 작으므로 최단거리 갱신이 된다.

0->3까지 최단거리는 이로써 3이 된다.

원래는 C++, C는 우선순위 큐를 이용하여 작성해야만 변수가 사라진다.

지금은 C# 코드만 ..