[자료구조]

1. 스택

2. 큐

3. 덱(Deque)

4. 링크드 리스트

5. 상호배타적 집합(disjoint set)

6. 세그먼트 트리

 

--------------------------------

1. 스택

- FILO (First In Last Out). 

- stl의 stack 클래스 사용하면 간단 사용 가능.

   push, top, pop, empty, size

- 알고리즘 문제풀이에 사용되는 스택은, 배열로 쉽게  구현해도 됨 (사용될 최대 크기가 결정되어 있기에)

  int st[1001],top=0;

  st[++top] = 1; //push(1)

  int a = st[top]; //top()

  top--;  //pop

  st[top--]; //top() and pop()

  if(top==0) //empty

 

2. 큐

- FIFO (First In First Out)

- stl의 queue클래스 사용하면 간단 사용 가능

  push, front, pop, size, empty /

- push는 rear쪽으로, pop은 front쪽으로. 

 

- 알고리즘 문제 풀이용 큐는 쉽게 구현가능. 그러나, 스택보다는 복잡(front와 rear의 포인터가 마냥 증가하지 않도록 조치 필요)

#define SIZE 1000

int q[SIZE], s = 0, e = 0;

void push(int a) {

          e = (e + 1) % SIZE;         

          q[e] = a;         

}

 

int front() {

         if (s == e) return -1;

         return q[s];

}

 

void pop() {

         if (s == e) return;

         s = (s + 1) % SIZE;

}

 

int size() {

         return e - s;

}

 

3. 덱(Deque)

- Double ended queue

- stl의 deque사용하면 간단

  push_front, push_back, pop_front, pop_back, front, back, size, empty, at

 (인덱스로 접근가능한 at 함수 있는게 특이)

 

- 문제풀이에서 직접 구현할 때는, 데이터크기의 두 배정도로 배열 잡아두고, 가운데를 중심으로해서, rear 인덱스는 증가, front인덱스는 감소하게해서 구현,

 

4. 링크드 리스트

양방향 Linked List를 구현해보면, 단방향은 그대로 해결

 

구조체 정의

struct List{

List* prev;

List* next:

int num;

}

 

기본 구조

- head가 존재. 초기상태는,

  . head->num=1

  . head->prev = head->next = head  //자기자신을 가리킴. head 하나만 있는 상태

- head->prev는 항상 last(맨 마지막 노드)를 가리킴

- last->next는 항상 head를 가리킴

 

insert(x)

- 맨 마지막 last 다음에 삽입. 이 때 last는 head->prev 가 가리키고 있음

- 삽입시 해줘야 할 것은,

1)신규 노드 생성: f = new List(); //f: fresh

2)num 지정: f->num = x

3)신규노드의 prev 지정: f->prev = head->prev; //head->prev는 삽입되기 전 맨 마지막 노드를 가리키고 있음

4)신규노드의 next를 head로 지정: f->next=head

5)last였던 노드의 next 갱신: head->prev->next = f

6)헤드의 prev 갱신: head->prev=f

 

삽입과정을 그림으로 보면 다음과 같다. (1,2가 있는 상태에서 3이 삽입될 경우)

 

 

 

LIST *head=NULL;

         for (int i = 1; i <= N; i++) {

                  if (i == 1) {

                           head = new LIST();

                           head->number = i;

                           head->next = head;

                           head->prev = head;

                           continue;

                  }

 

                  LIST *fresh = new LIST();

                  fresh->prev = head->prev;

                  fresh->next = head;

                  fresh->number = i;

                  head->prev->next = fresh;

                  head->prev = fresh;

         }

 

 

 

삭제

헤드를 삭제해 나가는 방법

1)헤드를 가리키는 임시 노드 생성: List* tmp = head;

2)last->prev 갱신: head->prev->next = head->next

3)head바로 다음에 있던 노드의 prev 갱신: head->next->prev=head->prev

 

 

 

         for (int i = 1; i <= N; i++) {

                  printf("%d ", head->number);

 

                  LIST *tmp = head;

                  if (i != N) {

                           head->prev->next = head->next;

                           head->next->prev = head->prev;

                           head = head->prev;

                           for (int j = 1; j <= K; j++) {

                                   head = head->next;

                           }

                  }

                  delete tmp;

         } 

 

5. 상호배타적 집합(disjoint set)

3가지 기능으로 구성됨: init, find, merge

1. init

//모든 배열값에 대해 각기 다른 값 배정

for(int i=0;i<=N;++i) p[i]=i;

 

2. find(a)

//parent값이 자기 자신과 같으면, 그것을 리턴

if(p[a]==a) return a;

 

//경로 압축을 해야 속도 보장됨

p[a] = find(p[a]); //새로 찾은 값들을 root 바로 밑에 붙여서, 경로를 줄임

return p[a];

 

3. merge(a,b)

int pa = find(a);

int pb = find(b);

p[pa] = pb;

 

6. 세그먼트 트리

주어진 값들에 대해 최소/최대/합 을 log(n)시간에 구해준다.

그럴러면, 주어진 값들을 가지고 특정 구조로 만들어둬야 한다. 트리 구조로.

 

트리구조를 만들 때 아래 특성을 이용해서 만듬.

  - 2진트리의 부모의 인덱스가 i이면, 왼쪽 자식은 2*i, 오른쪽 자식은 2*i+1이 됨

    아래 트리에서 보면 6 = 2*3, 7=2*3+1

    1

2                  3

4        5         6        7

 

3가지 연산: 1)init  2)query 3)update 

 

*구간 합 Tree 예

-주어진 값: arr[1..n]

-트리 배열: tree[1..4n]  //n에 가장 가까운 2의 멱승으로 올림한 값이 정확. 대충은 4n

1)init: 주어진 배열을 가지고 tree를 형성해 둔다.

int init(node, s,e)

if(s==e) return tree[node]=arr[s]

int m = (s+e)/2

return tree[node] = init(2*node,s,m) + init(2*node+1,m+1,e) 

//만약 min tree라면 min( init(2*node,s,m), init(2*node+1,m+1,e)

 

2)query

ll query(node, s,e,i,j) //i~j까지의 합

if(i>e || j<s) return 0 //1. 범위 밖이면.

if(i<=s && j>=e) return tree[node] //2. i~j가 node가 표현하는 집합을 완전히 포함

int m = (s+e)/2

return query(2*node,s,m,i,j)  + query(2*node+1,m+1,e,i,j) //3. 왼쪽 재귀 + 오른쪽 재귀

 

3)update

void update(node,s,e,i,diff) //diff:i노드에 diff만큼 더한다. diff를 한 이유는, 관련노드들을 diff만큼 더해야기 때문. 

if(i<s || i>e) return;        //1. 범위 밖

tree[node] = tree[node] + diff; //2. if(s==e)이면 갱신만. 즉, leaf까지 내려온경우.

if(s != e)                    //3. if(s!=e)이면, 자신도 갱신하고, 자식 노드들도 갱신

int m = (s+e) / 2;

update(2*node,s,m,i,diff)

update(2*node+1,m+1,e,i,diff)

 

 

 

 

-끝-