0x02.알고리즘(3):스택&큐&트리

3.스택(stack)

 

스택은 메모리관련 개념으로 많이 접할 수 있다. 스택의 어원은 건초더미로 알려져 있는데, 농부들이 건초들을 한 곳에 모을 때 차곡차곡 쌓이는 모습과, 그것들을 사용하기 위해 위에서부터 조금씩 덜어가는 모습을 본따 지었다고 한다. 속된 말로, 빨리 들어온 놈보다 늦게 들어온 놈이 먼저 선택된다는 뜻이다. 이 성질을 유식한 말로 LIFO(Last-In-First-Out)이라고 하기도 한다.

 

스택은 연산 시 중간 결과를 잠시 기록할 때 주로 사용되는데, 다음은 스택이 산술식을 계산하는 과정이다. 아래에서 사용된 방식은 역 폴란드(Polish Postfix) 표기방식인데, 이는 연산자들이 자신의 피연산자들의 직후에 위치하도록 하는 방법으로, 데이터가 숫자이면 스택에 추가하고, 연산자이면 스택의 상위 두 개의 데이터를 사용하여 연산을 수행한다.

 

 

스택을 구현하기 위해서는 다음과 같은 스택함수들을 사용하여야 한다.

 

push                     스택에 데이터 추가

pop                      스택에서 데이터 가져오기

clearstack               스택 초기화

 

위의 함수들은 다음과 같이 정의하여 사용할 수 있다.

 

int clearstack(){

   sp=0;

   return(sp);

}

 

void push(int val){

   sp++;

   if(sp>=size) call error;

   stack[sp]=val;

}

 

void pop(int val){

   sp--;

   if(sp<0) call error;

   return(stack[sp--]);

}

 

 

 

 

4.큐(queue)

 

이번에 다룰 내용은 스택과 더불어 많이 활용되는 큐이다. 큐는 스택과 달리 먼저 들어온 놈이 먼저 나가는 구조이다. 가장 쉬운 예로, 예매를 하기 위해 줄을 서서 기다리는 경우를 들 수 있다. 이 성질을 FIFO(First-In-First-Out)이라고 한다. 큐는 순서대로 작업을 처리하는 알고리즘을 작성할 때 주로 사용된다.

 

큐에서 사용되는 함수는 다음과 같다.

 

inqueue              큐에 데이터를 추가

dequeue             큐에서 데이터를 가져옴

 

참고적으로 큐에는 데크(deque)라는 변형된 구조가 존재하는데, 이는 큐와 달리 처음과 끝 양쪽으로 데이터를 삽입과 삭제할 수 있다. 즉, 큐의 성질이 양 끝에 복수 적용된다고 이해하면 된다.

 

 

 

 

5.트리(tree)

 

트리는 그림으로 이해하는 것이 가장 쉬웠기에 다음과 같이 그림판으로 그림을 그려보았다.

 

 

가장 꼭대기 즉, 나무의 개념으로 뿌리에 해당하는 것을 루트라고 하고, 위쪽에 있는 노드를 부모노드, 아래에 위치한 노드를 자식노드라고 한다. 즉 루트의 입장에서 보았을 때 두 개의 자식 노드가 있는 것이고, 그들의 입장에서는 한 개의 부모 노드가 있는데 그 노드가 루트인 것이다. 이 방식은 세부적으로 나눌 수 있다는 장점이 있기에 분류법에 주로 사용된다.

 

위 그림처럼 부모가 두 자식노드를 가지는 것을 이진트리라고 하는데, 구조체를 다음과 같이 선언할 수 있다.

 

struct node{

   int element;

   struct node *left, *right;

}

 

트리를 코딩하다 보면 자식노드의 수의 제한에 따른 문제가 발생한다. 위와 같이 이진트리의 경우, 자식노드를 두 개 이상으로 지정하지 못하는 문제가 발생하기 때문이다. 그래서 트리를 만들 때는 해당 노드의 자식노드들을 하나의 리스트에 연결하고 본인은 그 리스트의 첫 번째만 지정하는 방식을 사용한다. 즉 어느 한 노드를 기준노드라고 가정하면, 이 노드는 두 개의 포인터를 가지게 된다. 하나의 포인터는 위에서 말한 것처럼 자식노드들의 리스트의 첫 번째를 가리키는 포인터이고, 나머지 하나는 자기가 속해있는 리스트의 다음 요소를 가리키는 포인터이다.

 

그림으로 설명하자면, 전자는 자신의 왼쪽 자식노드를, 후자는 같은 항렬의 오른쪽 노드를 가리키는 것이다. 이로 인해, 자식노드의 개수와 상관없이 각 노드들은 두 개의 포인터만 활용하면 된다.

 

트리 방식에서 사용하는 탐색 방법에는 다음과 같이 세 가지가 존재한다.

 

⑴ 전위 탐색(preorder)

    임의의 노드를 탐색하기 위해 부모노드에서 자식노드 순으로 조사하는 방법

 

포인터 p : 탐색 대상인 노드를 가리키는 포인터 값

 

void preorder(struct node *p){

   if(p){

       something(p->element);

       preorder(p->left);

       preorder(p->right);

  }

}

 

그림을 기준으로 a->b->d->e->c->f->g

 

 

⑵ 중위 탐색(inorder)

    이진트리에서 임의의 노드를 탐색하기 위해 왼쪽 자식노드를 조사하고 본인을 조사하는 방법. 본인을 조사한 후에는 나머지 자식을 조사함

 

void inorder(struct node *p){

   if(p){

       something(p->left);

       preorder(p->element);

       preorder(p->right);

   }

}

 

그림을 기준으로 d->b->e->a->f->c->g

 

 

⑶ 후위 탐색(postorder)

    자식노드들의 탐색이 끝난 후에 부모노드를 탐색하는 방법

 

void postorder(struct node *p){

   if(p){

       something(p->left);

       preorder(p->right);

       preorder(p->element);

   }

}

 

그림을 기준으로 d->e->b->f->g->c->a