알고리즘3 자료구조 리뷰

이런 알고리즘이 이런 자료구조를 쓴다~를 알기 위해서!

 

  

Array

연속된 주소, 동일한 type

갯수를 미리 잡아둬야 한다. 용량을 늘리려면 다른 메모리에 옮겨야 한다.

int A[10] 은 int가 4byte이므로 총 40byte

A:400

404

408

412

...

A[7] = 400 + 7*4 = 428 이런식으로 바로 찾아갈 수 있음

 

Search, Delete, Insert 입장에서 좋은 효율은 아니다.

sorting이 되어있다면 Binary Search O(log N)가능하다. 

 

 

Stack

insert / Delete만 제공한다. Search x

=Push O(1) / Pop O(1)

 

Last in, First out 나중에 들어간 게 먼저 나온다.

 

수식 계산에 사용

ex (3+7)*2 + (6-3)/5

 

(괄호)안에 있는 식을 먼저 계산하면 느리게 짤 수는 있다.

처음부터 돌고, 또 처음부터 돌고

(10) * 2 + (6-3) / 5

(10) * 2 + (3) / 5

...

 

스택을 이용하면 빠르게 만들 수 있다.

linkedlist로 만들 수 있지만

보통 배열과 포인터를 이용한다. (다음에 push될 자리를 stack pointer가 가르킨다.)

 

 

Queue

insert O(1) / Delete O(1)만 제공한다. Search x

 

First in, First out

 

큐때문에 어려운 문제를 풀 수 있는 경우는 많이 없다.

문제의 난이도를 해결하지는 않지만 성능에 영향을 끼친다.

 

배열+Head&Tail 사용

 

Stack과 Queue 모두 배열을 다 채우면 안된다. => 2,3배까지 느리지만 linkedlist를 사용하는 이유

 

 

LinkedList

노드 (메모리에 있는 한 단위) 

 

C에서는

struct x {

    int a;

    float f;

    x  *n;  (x에 대한 포인터 n) 

};

 

 

포인터는 주소가 저장되어 있는 공간이다.

 

Search해서 Delete를 할 수 있지만 느리다

 

 

Binary Search Tree

search, delete, insert 가 모두 빠르다.

 

search tree는 sorting해서 저장하는 방법

왼쪽은 (전부) root보다 작고, 오른쪽은  (전부) root보다 크다.

 

노드마다 key가 있다 (일차원적으로 정렬할 수 있는 값)

각각의 서브트리도 BST

 

 

ex 14를 찾아라

 

->

<-

->

not found

 

ex 7을 찾아라

<-

<-

->

7 found

 

값이 있다 없다 알 수 있는 것만으로 유용하다

 

재귀로 짜는 것이 가장 편하다.

 

 

 

모든 operate는 뭘하든 내려가기 떄문에 트리의 높이에 비레하다. 

이런 경우는 LinkedList와 같아지며 성능이 안좋음

 

 

 

Heap 

Heap Insert

(up heap) 가장 작은 값 확인.  간단하고 굉장히 빠르다.

child가 2개인데 어느 길을 따라가든 수는 커진다.

우선순위 큐를 이용한다. 제일 작은 걸 꺼내는 방식(루트엔 가장 작은 값이 위치한다.)

 

새로 추가한 값은 항상 맨 끝에 들어가며 위로 올라가며 자기 자리를 찾는 방식

 

 

a가 새로 추가된거라면,

a가 c보다 크면 그 자리에 있으면 되고 작으면 올리면 된다.

 

이런식으로 추가하면 힙은 전체가 조건을 만족한다.

 

Heap Delete

(down heap)

삭제하면 맨위 자리가 빈다. 맨 밑을 맨 위로 올린다.

자식노드 양쪽을 비교해서 아래쪽이 루트보다 더 작다면

더 작은 애를 위로 올린다.

모든 노드의 크기관게를 다 맞추기 위해 반복해서 따라 내려간다.

 

노드가 N개 있다면 O(log N)