이진 트리 기반의 탐색을 위한 자료 구조입니다.

여기서 탐색은 레코드 집합(자료 구조)에서 특정 레코드(자료)를 찾아내는 작업을 의미합니다.

레코드 마다 고유의 키(key)값을 가지고 있기 때문에 키 값을 가지고 탐색을 진행합니다.

 

정의 및 특징

이진 탐색 트리는 탐색을 위한 몇 가지 성질을 만족하는 트리를 의미합니다.

  • 모든 원소(노드)의 키 값은 유일하다.
  • 왼쪽 서브 트리의 키 값은 루트의 키 값 보다 작다.
  • 오른쪽 서브 트리의 키 값은 루트의 키 값 보다 크다.
  • 모든 서브 트리가 위와 같은 성질을 지닌다.

한마디로 표현하자면 한 노드는 왼쪽 자식 노드보다 큰 키 값을 가지고 오른쪽 자식 노드보다 작은 키 값을 가진다는 것입니다.

bst의 한 가지 예

 

이진 탐색 트리에는 크게 탐색, 삽입, 삭제 세 가지 연산이 필요합니다.

  • 탐색
    • 루트부터 시작해서 key 값을 비교해가며 원하는 key이 더 작으면 왼쪽 서브트리로 더 크면 오른쪽 서브트리로 이동합니다.
    • 두 갈래 중 하나를 선택해서 탐색하기 때문에 시간 복잡도는 O(logn) 입니다.
node* search(int key){
	node* p = root;
    
	while(p != NULL){
    	if(key < p->key){
        	p = p->left;
        }
        else if(key > p->key){
        	p = p->right;
      	}
        else if(key == p-> key){
        	return p;
        }
   	}
    
    return p;
}
        

 

  • 삽입
    • 탐색 한 후 마지막으로 NULL인 자리에 새로운 노드를 생성한 후 key값을 설정해서 연결해주면 됩니다.
insert(int key){
	node* new = new node;
    new->key = key;
    
    node* p = root;
    node* r;
    
    whlie(p != NULL){
    	r= p; // r은 p의 부모노드
        
    	if(key < p->key)
        	p = p->left;
        else if(key > p->key)
        	p = p->right;
        else 
        	break;
    }
    
    if(key < r->key)
    	r->left = new;
    else
    	r->right = new;
}

 

  • 삭제
    • 삭제 같은 경우가 가장 골치아픈 연산입니다. 
    • 세 가지 상황이 있습니다.
      1. 단말 노드(leaf node)를 삭제하는 경우
      2. 삭제하려는 노드가 한 쪽만 서브트리를 가지고 있는 경우
      3. 삭제하려는 노드가 두 쪽 모두 서브트리를 가지고 있는 경우
    • 단말 노드일 경우 탐색하여 NULL로 만들어주면 됩니다.
    • 하나의 서브트리만 가지고 있는 경우에는 그 서브트리의 루트를 대신 연결해주고 삭제를 진행하면 됩니다.
    • 두 개의 서브트리를 가지고 있는 경우 새로 루트가 될 후보는 두 개의 노드입니다.
      1. 왼쪽 서브트리의 가장 큰 값(가장 오른쪽의 노드)
      2. 오른쪽 서브트리의 가장 작은 값(가장 왼쪽의 노드)
      3. 이 두가지 이외의 값으로 삭제를 진행한다면 서브트리를 재구성 해야합니다.
      4. 예를 들어, 오른쪽 서브트리에서 가장 큰 값을 새로운 루트로 지정한다면, 오른쪽 서브트리의 모든 노드들을 왼쪽 서브트리로 옮겨야 합니다.
      5. 두 방향의 깊이를 비교한다면 더 깊은 쪽의 노드를 선택하면 좀 더 균형을 맞출 수 있습니다.

서브트리가 한 쪽에만 있을 경우
양쪽에 서브트리가 있을 경우

delete_node(int key){

    node* p = root;
    node* r;
    
    whlie(p != NULL){
    	r= p; // r은 p의 부모노드
        
    	if(key < p->key)
        	p = p->left;
        else if(key > p->key)
        	p = p->right;
        else
        	break;
    }
    
    if(p->left == NULL && p-> right == NULL){ // 단말 노드일 때
    	if(p->key == r->left->key)
        	r->left = NULL;
        else if(p->key == r->right->key)
        	r->right = NULL:
    }
    
    else if(p->left == NULL || p-> right == NULL){ // 하나의 서브트리
    	node* nroot;
        
        if(p->left == NULL)
        	nroot = p->right;
        else
        	nroot = p->left;
            
        if(nroot->key == r->left->key){
        	r->left = nroot;
        }
        else if(nroot->key == r->right->key){
        	r->right == nroot;
        }
        free(p);
    }
    
    else{ //양쪽에 서브트리, 오른쪽에서 후계자 찾기
        node* r = p->right;
        node* r_r; // 후계자의 부모노드 => 후계자가 단말노드이면 필요없지만 단말노드가 아닐 경우 필요합니다.
        
        while(r -> left != NULL){
        	r_r = right;
			r = r -> left;
        }
        
        if(r_r != NULL)
        	r_r->left = r->right;
        
        p->key = r->key;
        
        free(r);            
    }
            
        

 

이진 탐색 트리의 삽입 순서에 따라서 좌측 혹은 우측으로 치우치는 이진 탐색 트리가 될 수 있습니다.

이런 형태면 탐색 시간이 O(n)이 되기 때문에 균형적인 트리로 만들어 줄 필요가 있습니다.

이후에 AVL 트리 와 같은 균형을 맞추는 기법에 대해서도 소개하겠습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

그래프(graph)  (0) 2019.04.23
트리(tree)  (0) 2019.04.22
큐(queue)  (0) 2019.04.21
스택(Stack)  (0) 2019.04.19
배열과 연결 리스트  (0) 2019.04.18

관련 용어

  • 정점(vertex) : node를 의미한다.
  • 간선(edge) : 노드 간에 연결되어 있는 선을 의미한다.
  • 인접 정점(adjacent vertex) : 간선으로 연결된 정점 혹은 노드를 의미한다.
  • 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.
  • 진입 차수(in-degree) :  방향이 자신 쪽으로 향하는 간선의 수를 의미한다.
  • 진출 차수(out-degree) : 방향이 다른 정점을 향하는 간선의 수를 의미한다. 
  • 경로 길이(path length) : 경로에서 '간선의 개수 = 지나는 정점 - 1' 을 의미한다.
  • 단순 경로(simple path) : 중복되는 정점이 없는 경로를 의미한다.
  • 사이클(cycle) : 출발점과 도착점이 같은 단순 경로를 의미한다.

※오일러 경로

  • 모든 간선을 한번 지나가면서 출발 정점으로 되돌아오는 경로를 뜻한다.
  • 모든 정점의 간선이 짝수개 있어야 한다.

 

정의 및 특징

일반적으로 정점(노드)와 간선으로 구성된 자료구조를 그래프라고 합니다.

  • 일반적으로 정점(노드)는 상태 혹은 객체를 표현한 것이고 간선은 관계를 표현한 것입니다.

그래프의 특징에 대해서 알아보겠습니다.

  • 트리와는 다르게 루트 노드, 부모 노드, 자식 노드의 개념이 없고 인접 노드(정점)의 개념으로 받아 들여집니다.
  • 사이클이 존재하고 self-loop 또한 존재합니다.
  • 간선이 존재할 수도 있고 존재하지 않을 수도 있습니다.
  • 간선의 방향이 존재하면 방향 그래프, 존재하지 않으면 무방향 그래프라고 합니다.
  • '모든 정점의 차수 합 = 간선의 수 x 2' 입니다.

 

그래프의 종류

  • 방향 그래프
    • 간선의 방향이 정해진 그래프를 의미합니다.
    • 진입 차수, 진출 차수가 존재하며 다른 방향의 정점을 바로 갈 수 없습니다.
  • 무방향 그래프
    • 방향이 정해져있지 않기 떄문에 간선으로 연결 된 모든 정점을 바로 갈 수 있습니다.
  • 가중치 그래프
    • 간선에 가중치가 있는 그래프입니다.
    • 가중치가 경로를 결정하는 지의 유무에 따라 경로가 바뀔 수 있습니다.
    • 네트워크라고도 하고 주로 도시와 도시를 연결하는 도로, 통신망의 사용료 등을 추가로 표현 할 때 사용합니다.
  • 완전 그래프
    • 모든 정점이 간선으로 연결되어 있는 무방향 그래프입니다.
    • 정점의 개수가 n이라면 간선의 개수는 n x (n - 1) / 2 입니다.

     

완전 그래프

 

구현 방법

  • 인접 리스트
    • 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방식입니다.
    • 인접한 노드들을 찾기 편합니다.
    • 정점의 개수가 n 개이고 간선의 개수가 e 개이면 n 개의 헤드 노드가 필요하고 2 x e 개의 노드가 필요합니다.
    • 모든 간선을 탐색하는 데 걸리는 시간 O(n(정점의 개수) + e(간선의 개수)) 입니다.
    • 간선의 개수가 많아지면 순회하는 시간이 증가합니다.

인접 리스트로 표현

 

  • 인접 행렬
    • 이차원 배열을 활용합니다.
    • (i, j)의 값이 1이면 i 정점과 j 정점이 간선으로 연결되어 있다는 것입니다.
    • 무방향 그래프일 경우 대칭 행렬의 형태를 띕니다.
    • 정점의 개수가 n개이면 n^2의 공간이 필요합니다.
    • 간선이 적으면 공간적으로 비효율적이다.
    • 모든 간선을 탐색하는 데 걸리는 시간은 O(n^2) 입니다.
  • 선택 기준
    • 간선이 많은 그래프(밀집 그래프)의 경우 인접 리스트로 구현했을 때, 정점의 차수 만큼 순회 시간이 길어지기 때문에 인접 행렬로 구현하는 것이 적합합니다.
    • 간선이 적은 그래프(희소 그래프)의 경우 인접 행렬로 구현했을 때 공간적으로 비효율적이기 때문에 인접 리스트로 구현하는 것이 적합합니다.

 

탐색

그래프를 탐색하는 데에 대표적으로 BFS(너비우선탐색)과 DFS(깊이우선탐색)이 있습니다.

간략하게 소개하자면 BFS의 경우 모든 인접 노드들을 다음 탐색 대상으로 설정하여 넓게 탐색하는 방식입니다.

DFS의 경우, 인접 노드들을 차례로 하나씩 갈 수 있을 때 까지, 깊게 탐색하는 방식입니다.

이 두 가지 탐색법에 대해서는 이후에 자세하게 다룰 예정입니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

이진 탐색 트리(binary search tree)  (0) 2019.04.24
트리(tree)  (0) 2019.04.22
큐(queue)  (0) 2019.04.21
스택(Stack)  (0) 2019.04.19
배열과 연결 리스트  (0) 2019.04.18

관련용어

 

  • 루트 노드(Root Node) : 트리의 가장 위의 노드, 부모 노드가 없다. 
  • 단말 노드(Leaf Node) : 자식이 없는 노드를 말한다.
  • 간선(Edge) : 노드를 연결하는 선을 말한다.
  • 부모 노드(Parent Node) : 임의의 노드 위에 연결된 하나의 노드를 말한다.
  • 자식 노드(Child Node) : 임의의 노드의 하위에 연결된 모든 노드를 말한다.
  • 형제(Sibling) : 같은 부모를 가지는 노드들을 말한다.

  • 노드의 깊이(depth) : 루트 노드 부터 자기 자신 까지의 간선의 개수를 의미한다.
  • 노드의 레벨(level) : 특정 깊이를 가지는 노드의 집합을 의미한다.
  • 노드의 차수(degree) : 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 또는 자식 노드의 수를 의미한다.
  • 트리의 차수(degree of tree) : 가장 큰 노드의 차수를 의미한다.
  • 리의 높이(height) : 가장 밑에 있는 단말 노드의 깊이, 보통 가장 높은 레벨을 의미한다.

 

 

개념 및 특징

트리는 비선형 구조, 그 중에서도 계층적 구조의 대표적인 예인데요, 마치 나무가 가지를 뻗는 모양새라고 해서 트리라는 이름을 가졌습니다.

트리는 방향성이 있는 비순환 그래프의 한 종류인데 몇 가지 특징을 알아보겠습니다.

  • 트리는 노드와 간선으로 구성 된 자료구조 입니다. 노드들 간에 간선으로 이어져 있습니다.
  • 노드 간에 간선에는 방향이 자식 노드가 부모 노드를 가리킬 수 없기 때문에 사이클이 존재하지 않습니다.
    • self loop 또한 존재하지 않습니다.
    • 트리는 방향성이 있는 비순환 그래프입니다.
  • 하나의 트리에는 오직 하나의 루트 노드만이 존재합니다.
  • 노드마다 0개 이상의 자식 노드를 가집니다.
    • 0개면 단말 노드 입니다.
  • 루트 노드를 제외하고 노드마다 부모 노드는 오직 하나입니다.
    • 어떤 노드에서 다른 모든 노드 까지의 경로는 오직 하나입니다.
  • '간선의 개수' = '노드의 개수 - 1' 입니다.
  • 트리의 종류에는 이진 트리, 이진 탐색 트리, AVL 트리, red - black 트리, 힙 등이 있습니다. 

 

이진트리

가장 기본적인 트리인 이진 트리에 대해서 알아보겠습니다.

이진트리는 자식 노드의 최대 개수가 2인 트리를 의미합니다. 따라서 노드 data와 두 개의 자식 노드에 대한 정보로 구성되어있습니다.

node{
	data elemnet;
   	node* child1;
   	node* child2;
}

 

※ 이진 트리의 분류

  • 포화 이진트리
    • 트리의 각 레벨에 노드가 꽉 차있는 이진 트리를 의미합니다. => 트리의 높이가 N이면 노드의 개수는 2^N - 1
    • 말단 노드를 제외한 모든 노드는 2개의 자식 노드를 갖습니다.
    • 말단 노드들은 모두 형제(Sibling)입니다.

포화 이진트리

 

 

  • 완전 이진트리
    • 마지막 레벨을 제외한 모든 레벨에서 노드가 꽉 차있는 이진 트리를 의미합니다.
    • 포화 이진트리와의 차이점은 마지막 레벨에서 노드가 꽉 차있지 않습니다. 
    • 왼쪽 부터 자식을 채워 나갑니다. 만약 왼쪽 자식은 없는 데 오른쪽이 있으면 완전 이진트리가 아닙니다.
    • 포화 이진트리는 완전 이진트리이지만 완전 이진트리는 포화 이진트리가 아닙니다.

완전 이진트리
완전 이진트리 아님

※순회

  • 전위순회(preorder) 
    1. 루트를 방문한다.
    2. 왼쪽 서브트리를 방문한다. 
    3. 오른쪽 서브트리를 방문한다.

preorder(node){
	if(node != NULL){
    	visit(node);
        preorder(node->left);
        preorder(node->right);
    }
}
	

 

  • 중위순회(inorder)

    1. 왼쪽 서브트리를 방문한다.
    2. 루트를 방문한다.
    3. 오른쪽 서브트리를 방문한다.

inorder(node){
	if(node != NULL){
        inorder(node->left);
        visit(node);
        inorder(node->right);
    }
}
	

 

  • 후위순회(postorder
    1. 왼쪽 서브트리를 방문한다.
    2. 오른쪽 서브트리를 방문한다.
    3. 루트를 방문한다.

postorder(node){
	if(node != NULL){
        postorder(node->left);
        postorder(node->right);
        visit(node);
    }
}
	

 

기타 트리(나중에 자세하게 다룰 예정)

  • 이진 탐색트리
    • 모든 서브트리에서 '오른쪽 자식 노드 > 루트 > 왼쪽 자식 노드'의 속성을 가지는 트리를 의미합니다.
    • 한쪽으로 편중 될 수 있다는 단점을 가지고 있습니다. (불균형트리)
  • AVL, red - black 트리
    • 균형트리, 이진 탐색트리의 단점을 보완할 수 있습니다.
    • 최소 힙(Min heap), 최대 힙(Max heap)

 

트리 구현방법

  • 배열
    1. 자식의 최대 개수를 알 때
      • 이차원 배열을 활용해 자식  노드의 index를 저장합니다. ex) 이진트리 array[n][0] => n 노드의 왼쪽 자식, array[n][1] => n 노드의 오른쪽 자식
    2. 자식의 최대 개수를 모를 때
      • 1차원 배열에 부모 노드의 index를 저장합니다.
  • 인접 리스트
    • 각 정점마다 자식 노드를 연결하는 새로운 연결 리스트를 만들어 줍니다.

 

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

이진 탐색 트리(binary search tree)  (0) 2019.04.24
그래프(graph)  (0) 2019.04.23
큐(queue)  (0) 2019.04.21
스택(Stack)  (0) 2019.04.19
배열과 연결 리스트  (0) 2019.04.18

'길게 늘어선 줄' 큐(queue)의 사전적 의미입니다.

밑에서 부터 자료(data)들을 쌓는 스택(stack)과는 달리 일렬로 저장하는 것이죠. 

이제부터 큐(queue)의 동작 원리 및 특징에 대해서 알아보겠습니다.

동작 원리

'가장 먼저 저장된 자료가 가장 먼저 뽑힌다.' 이것이 큐의 동작 원리입니다.

우리는 이것은 '선입선출'이라고 합니다. 영어로는 'FIFO(First In First Out)'라고 하죠. 

저장했던 순서 반대로 자료를 뽑을 수 있었던 스택과는 달리 큐에서는 저장했던 순서대로 자료를 뽑아서 활용할 수 있습니다.

        5
      4 4
    3 3 3
  2 2 2 2
1 1 1 1 1

1에서 부터 5까지 순서대로 큐에 저장하는 모습입니다. 빨간색으로 표현된 자료는 각 단계에서 가장 먼저 뽑을 수 있는 자료입니다. 스택과는 다르게 가장 밑에 있는 자료가 표시되었네요.

 

특징

큐에서도 스택에서와 마찬가지로 크게 두 가지 동작이 있습니다. pop과 push 입니다.

스택에서는 top 하나가 pop과 push를 담당했었는데 큐에서는 pop과 push가 발생하는 위치가 서로 다르기 때문에 두 개의 top이 필요합니다. 

하나는 pop을 위한 top으로 front, 다른 하나는 push를 위한 top으로 rear라고 합니다.

push원리는 stack과 동일합니다. 가장 끝에서 이루어지기 때문에 que에서는 rear(꼬리)라고 흔히 표시합니다.

pop은 가장 앞에서 이루어지기 때문에 흔히 front(앞)이라고 표시합니다.

큐 또한 배열과 연결 리스트를 활용해 구현할 수 있는 데요.

배열에서는 front, rear는 두 개의 index일 것이고, 연결 리스트에서는 두 개의 포인터가 되겠습니다.

 

배열

배열로 구현하는 큐 또한 정말 간편합니다.

front와 rear를 -1 또는 0으로 초기화 하느냐에 따라 살짝 차이가 있지만 저번 스택을 소개하는 글에서 다루었기 때문에 이번에는 0으로 초기했을 때만 다루겠습니다.

pop을 했을 때, 가장 먼저 저장되었던 '1'이 뽑힌 것을 확인할 수 있습니다. push는 스택과 큰 차이점이 없죠?

간단하게 코드만 확인하고 넘어가겠습니다.

push(data element){
	if(큐 범위 넘어가면)
    	return;
    
    queue[rear++] = element;
}
pop(){
	if(front >= rear) // rear가 front와 같거나 작으면 큐가 비어있는 것
    	return;
    
    return queue[front++];
}

 

연결 리스트

처음 rear와 front 포인터는 head 더미 노드를 가리키면서 시작합니다. 여기 까지는 스택과 같습니다.

스택에서는 head 노드 쪽으로 향했던 방향이었던 것과는 달리 큐에서는 반대 방향으로 진행합니다. push와 pop이 일어나는 노드가 rear와 front로 나뉘어졌기 때문이죠.

push할 때는 새로운 노드를 생성해서 rear가 가리키는 노드의 next를 새로운 노드를 가리키게 한 후, rear를 새로운 노드를 가리키게 합니다.

 

pop에서는 사실 front의 역할을 하기 때문에 head의 next가 가리키는 node의 next가 가리키는 node로 head를 연결하면 됩니다.

하지만 필요없는 메모리를 삭제하기 위해 front를 옮겨가면서 pop을 진행합니다.

 

push(data element){
	node* new_node;
    new_node = new node;
    
    new_node->elemnet = elemnet;
    
    rear->next = new_node;
    rear = new_node;
}

pop(){
	front = front->next;
    
    head->next = front->next;
    
    delete front;
	
    front = head;
}

 

지금까지 큐에 대해서 알아봤습니다.

사실 큐는 스택보다 자주 사용되는데요. 특히 bfs 알고리즘을 활용할 때, 자주 사용됩니다.

나중에 bfs 알고리즘을 다룰 때, 더 자세하게 설명하겠습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

그래프(graph)  (0) 2019.04.23
트리(tree)  (0) 2019.04.22
스택(Stack)  (0) 2019.04.19
배열과 연결 리스트  (0) 2019.04.18
자료구조란?  (0) 2019.04.17

'쌓아놓은 더미' 스택(stack)의 사전적 의미입니다. 말 그대로 '무언가'를 밑에서 부터 차곡차곡 쌓는 형태입니다.

자료구조에 스택은 그 '무언가'가 곧 자료(data)가 되겠죠.  이제부터 스택의 동작 원리 및 특징에 대해서 다루기로 하겠습니다.

동작 원리

스택을 소개할 때, 밑에서 부터 자료를 차곡차곡 쌓는 형태라고 말씀드렸습니다. 

쌓는 것은 자료구조에 저장한다는 의미이고 차곡차곡 쌓기 때문에 순서대로 밑에서부터 저장됩니다.

쌓여있는 구조에서 밑에 있는 것을 빼내려고 하면 어떻게 될까요? 당연히 무너지게 됩니다.

그러므로 저장된 자료들을 뽑을 때는 맨 위에서 부터 뽑아야겠죠. 맨 위에 있는 자료는 순서대로 밑에서 부터 저장되기 때문에 가장 늦게 저장된 자료일 것입니다.

'가장 늦게 저장된 자료가 가장 먼저 뽑힌다.' 이것이 스택의 동작 원리입니다.

우리는 이것은 '후입선출'이라고 합니다. 영어로는 'LIFO(Last In First Out)'라고 하죠. 

        5
      4 4
    3 3 3
  2 2 2 2
1 1 1 1 1

1에서 부터 5까지 순서대로 스택에 저장하는 모습입니다. 빨간색으로 표현된 자료는 각 단계에서 가장 먼저 뽑을 수 있는 자료입니다.

 

특징

스택에서는 크게 두 가지 동작이 있습니다. 뽑는 것(Out)과 넣는 것(In) 입니다.

뽑는 것을 우리는 흔히 pop이라고 표현하고, 넣는 것을 push라고 표현합니다. 

pop과 push는 위에서 말한 것 처럼, 스택의 가장 위에서 이루어지는기 때문에 이를 가리키는 녀석이 하나 필요한데 우리는 이것을 top이라고 말합니다.

배열과 연결 리스트를 이용해 스택을 구현할 수 있는 데, 배열에서 top는 단순히 index이고 연결리스트에서는 node를 가리키는 포인터가 되겠습니다.

이제 배열과 연결리스트를 이용해 스택을 구현하는 방법에 대해서 알아보겠습니다.

 

배열

사실 배열로 구현하는 스택은 정말 간편합니다.

top을 처음 설정할 때, -1 또는 0으로 설정할 수 있는데 이것은 취향차이라고 생각합니다.

top이 -1로 초기 설정해주었을 때는, top + 1해주고 push, pop해주고 top - 1을 해주면 되고

top이 0으로 초기 설정해주었을 때는 top에 push하고  top + 1, top - 1 해주고 pop해주면 됩니다.

다음은 1,2,3,4,5를 push 할 때, 각 상황에 맞게 top을 표시한 것입니다.

한마디로 표현하자면 top이 -1로 초기화 되었을 때는, 맨 위의 자료를 가리키고 0으로 초기화 되었을 때는 다음 자료가 push될 자리를 가리킨다고 생각하시면 쉬울 겁니다.

 

push(data element){ // top = -1로 초기화 되었을 때
	if(스택 범위 넘어가면)
    	return;
        
   	 stack[++top] = element;
}
pop(){
	if(스택 비어있으면)
    	return;
        
   	return stack[top--];
}

push(data element){ // top = 0으로 초기화 되었을 때
	if(스택 범위 넘어가면)
    	return;
        
    stack[top++] = element;
}
pop(){
	if(스택 비어있으면)
    	return;
        
    return stack[--top];
}


 

연결 리스트

처음 top 포인터는 head 더미 노드를 가리키면서 시작합니다.

이후, push할 때마다, 새로운 노드를 생성해서 새로운 노드의 next가 top을 가리키는 노드를 가리키게 한 후, top이 새로운 노드를 가리키게 하면 됩니다.

사실, next의 방향을 반대로 해도 되지만 pop연산을 할 때 따로 top 이전의 노드에 대한 탐색이 필요하기 때문에 이런 방향을 선택했습니다.

pop을 할 때는 top을 가리키는 노드를 가리키는 tmp 포인터를 생성한 후, top을 이전 노드로 옮기고 tmp 노드는 삭제하면 됩니다.

push(data element){
	node* new_node;
   	new_node = new node;
    
    new_node->element = element;
    new_node->next = top;
    
    top = new_node;
}

pop(){
	if(top->next = null)
    	return;
        
	node* tmp = top;
    
    top = tmp->next;
    
    data ret = tmp->element;
    
    delete tmp;
    
    return ret;
}

 

지금까지, 스택의 동작 원리와 특징에 대해서 알아봤는데요. 가장 중요한 것은 '후입선출' 인 것 같아요.

어떤 문제 상황에 후입선출이라는 원리가 숨어져 있다면 무조건 스택을 활용하면 됩니다. 

대표적으로 연산식에 괄호가 올바르게 형성되어 있는지 스택을 이용해서 알 수 있습니다. 

닫는 괄호('},],),>')가 나올 때 마다, 순서대로 스택에 push한 여는 괄호(' {, [, (, <')를 pop해서 쌍이 맞는 지, 확인하고 식 전체를 탐색했을 때, stack안에 아무 자료도 없다면 알맞는 괄호 식이 되겠습니다.

추가적으로, 제가 풀었던 알고리즘 문제에서도 스택을 활용한 문제가 있는데요. 바로 드래곤 커브입니다.

어느 정도 스택을 사용할 줄 아시면 이 문제에 도전해보시면 좋을 것 같습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

그래프(graph)  (0) 2019.04.23
트리(tree)  (0) 2019.04.22
큐(queue)  (0) 2019.04.21
배열과 연결 리스트  (0) 2019.04.18
자료구조란?  (0) 2019.04.17

배열과 연결 리스트는 아주 기초적인 선형 자료구조입니다. 보통 다른 자료구조를 구현하기 위한 수단으로 이용됩니다.

 

배열

배열은 가장 기초적이면서 다루기 쉬운 자료구조입니다. 적절하게 인덱스를 핸들링할 수 있다면 다루기 쉬운 자료구조입니다. 

하지만, 처음에 배열을 선언할 때, 크기를 지정해줘야 한다는 문제점이 있죠. 문제상황을 해결할 때, 필요한 배열의 크기를 가늠할 수 없다면 활용하기 쉽지 않습니다.

이런 문제는 크게 두 가지 방법으로 해결이 가능한데, 하나는 동적인 방법으로 배열의 크기를 재설정하는 것이고 다른 하나는 연결 리스트를 활용하는 것 입니다.

동적 배열은 지정된 배열의 크기가 부족할 때, 사이즈가 더 큰 새로운 배열을 할당해 기존 배열의 자료를 복사한 다음, 포인터를 옮기는 방식으로 구현이 가능합니다.

if(용량 == size){

	int new_size = size * 2;
    int *new_array = new int[new_size];
     
    for(int i = 0; i < size; i++){
    	new_array[i] = old_array[i];
    }
     
    delete[] old;
     
    size = new_size;
    old_array = new_array;

 

연결 리스트

연결 리스트를 이용해 배열의 용량 문제 뿐 아니라 삭제, 삽입 등과 같은 연산을 행할 때의 번거로움 또한 해결할 수 있습니다.

연결 리스트는 자료와 포인터로 이루어진 노드라는 구조체를 활용합니다.

struct node{
	dataType *next;
    dataType element;
}

 

head라고 불리는 더미노드를 시작점으로 두고 새로운 자료를 저장할 때마다, 노드를 생성해 이전 노드와 연결만 해주면 됩니다.

그리고 추가 또는 마지막 노드 삭제를 편하게 하기 위해 마지막 노드를 포인터로 지정하는 것이 좋습니다. 마지막 노드의 next는 null로 설정해주면 되겠습니다.

배열에서 삭제와 삽입이 번거로운 반면에 연결 리스트에서는 간편합니다.

삭제는 원하는 자료를 가진 노드를 탐색후 이전 노드의 포인터를 다다음 노드로 이어주기만 하면 됩니다.

삽입은 새로운 노드를 생성한 후 원하는 위치 이전의 노드가 새로운 노드와 이어주고 새로운 노드와 그 다음 노드를 이어주기만 하면 됩니다.

배열과 연결 리스트 비교

가장 큰 차이점은 한번에 접근이 가능하냐 아니냐 인것 같습니다.

배열의 경우, 원하는 위치의 자료에 접근하기 위해서는 인덱스를 이용해 직접적으로 접근이 가능하지만 연결 리스트의 경우, 탐색을 기반으로 원하는 위치의 자료에 접근해야하기 때문에 그만큼 수행시간이 늘어나게 되죠.

삽입, 삭제 할 때, 배열과 연결 리스트 모두 탐색이 필요합니다.

하지만, 배열 같은 경우 삽입, 삭제한 위치 이후의 자료들을 따로 처리해줘야 한다는 점에서 연결 리스트의 강점을 확인할 수 있습니다.

따라서, 만약 1. 필요한 배열의 크기를 알고 2. 삽입, 삭제와 같은 연산이 필요 없을 경우에는 배열을 이용하는 것이 편하고 이외의 경우에는 연결리스트가 더 좋은 선택이 될 수 있겠네요.

 

앞서 말한 것과 같이, 배열과 연결 리스트 모두 다른 자료구조를 구현하기 위한 수단적인 자료구조입니다. 

이제부터 그 자료구조들에 대해서 다뤄보면서 배열, 연결 리스트 두 가지 방법으로 구현하는 방법에 대해서도 다룰 것이기 때문에 각각의 특징을 잘 알아 두는 것이 좋겠습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

그래프(graph)  (0) 2019.04.23
트리(tree)  (0) 2019.04.22
큐(queue)  (0) 2019.04.21
스택(Stack)  (0) 2019.04.19
자료구조란?  (0) 2019.04.17

자료구조의 정의 및 필요성

 

자료구조란?

데이터의 인터페이스를 추상적으로 정의한 것, 어렵죠잉~

쉽게 말해서 데이터를 효율적으로 활용하기 위해 저장하는 방법이라고 생각하면 편할꺼에요.

 

자료구조가 왜 필요할까?

프로그래밍을 하다 보면 데이터를 처리할 때마다 새로운 변수를 선언해서 처리하기에는 양이 너무 방대하죠.

또한, 데이터 마다 변수 이름을 기억하고 활용하기가 불가능합니다.

이런 문제점을 보완하기 위한 것이 자료구조 입니다.

자료구조를 통해 데이터를 검색, 추가, 삭제 등 활용하기 쉽게 정리하여 프로그램의 성능(시간적, 공간적)을 높이는 것입니다.

 

자료구조의 특징

  • 추상화

추상화란 단어 정말 많이 쓰이는데 정확한 뜻을 알기 쉽지않죠.

현실 세계의 개념이나 구조를 프로그램에서 새로 자료구조로 표현하는 것 대략 이런 느낌으로만 알고 있으면 충분합니다.

이러한 자료구조는 그 내용과 작동원리에 대해 다른 사람들도 쉽게 알아보고 활용할 수 있게 표현합니다.

예를 들어, name_stack은 사람들의 이름을 스택(stack)이라는 자료구조를 통해 표현하는 것이죠. name_stack의 내용은 사람 이름이고 작동원리는 스택(stack)push, pop 또는 LIFO 가 되겠네요.

 

  • 최적화

말 그대로 성능을 최대한 높일 수 있는 최적의 자료구조를 선택하는 것입니다.

프로그램 동작의 효율성을 높이기 위해 상황에 맞는 적합한 자료구조를 선택해야 합니다. 

예를 들어, 선착순에 적합한 자료구조는 큐(queue)인데 스택(stack)을 활용하면 안된다는 것입니다.

 

분류

  • 선형구조

선형구조는 쉽게 말해서 일렬로 저장되어 순서가 있는 것입니다. 자료마다 자기 뒤에 0개 또는 1개의 자료가 있는 구조라고 생각하시면 쉽습니다.

  1. 배열
  2. 연결 리스트
  3. 스택
  4.                             
  • 비선형구조

비선형 구조는 선형구조처럼 일렬이 아니라 특이한 형태를 갖는 자료구조입니다. 정해진 순서 없이는 따로 순서가 없고 뒤에 0개 또는 1개의 자료만 있는 것이 아니라 랜덤으로 자료가 붙을 수 있습니다.

  1. 트리 
  2. 그래프

 

이제 선형구조(배열, 리스트, 스택, 큐)와 비선형 구조(트리, 그래프)에 대해서 자세히 알아보겠습니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!

'전체 > 자료구조' 카테고리의 다른 글

그래프(graph)  (0) 2019.04.23
트리(tree)  (0) 2019.04.22
큐(queue)  (0) 2019.04.21
스택(Stack)  (0) 2019.04.19
배열과 연결 리스트  (0) 2019.04.18

+ Recent posts