1. 트리(Tree)

아직까지도 많이 사용되고, 앞에서 다룬 자료형들보다 더욱 다양한 형태로 개발된 자료형입니다.

트리는 그래프와 유사한 형태이지만, A에서 B라는 노드로 갈 수 있는 한개의 길만 존재하는 자료구조입니다.

이진트리(출처 : 위키)

트리(Tree)는 아래와 같은 요소를 갖고있습니다.

 - Root(루트노드) : 최상의 노드 (위 그림에서 2)

 - parent(부모노드) : 특정 노드의 바로 상위에 연결된 노드 (2는 루트노드이며, 7과 5의 부모노드입니다.)

 - child(자식노드) : 특정노드의 바로 아래에 연결된 노드 (7과 5는 2의 자식노드입니다.)

 - sibling(형제노드) : 같은 부모노드를 갖고있는 노드입니다. (7과 5는 형제노드입니다)

 - leaf(단말노드) : 자식이 없는 최하단의 노드입니다. (2"중복", 5, 11, 4는 단말노드입니다.)

 - Level(레벨) : Root를 Level 1로 두고, 아래로 자식노드로 내려갈 수록 1씩 증가합니다. (6의 경우 Level3)

 - depth(깊이) : 트리의 최대 Level을 의미합니다. 위 트리의 depth는 4입니다.

 - degree(차수) : 특정 노드의 하위 트리의 개수를 의미합니다.

 

 

 

1.1. 이진트리 (Binary Tree)

가장 대표적인 트리의 형태로, 위 그림에서 다루었던 형태입니다.

하나의 노드는 최대 두 개의 자식노드만을 갖을 수 있는 형태입니다. 이진트리를 사용하는 이유는, 자식노드이 수가 최대 2개로 정해져있기 때문에 구현하기 쉽고, 이를 이용하여 다양한 알고리즘을 구현하는것이 가능하다는 장점이 있습니다.

 

 1) BST(Binary Search Tree)

가장 대표적인 탐색알고리즘입니다. BST를 이용하기 위해서는 아래와같은 전재가 필요합니다.

 - 이진트리로 구현되어있을 것

 - 특정 노드를 기준으로 좌측에는 항상 작은 값이, 우측에는 항상 큰 값이 존재해야합니다.

 - 모든 노드는 서로다른 값(키)을 갖고있어야 합니다.

 

class Node():
    def __init__(self, data, left=None, right=None, parent=None):
    	self.value = data
        self.left = left
        self.right = right
        self.parent = parent
    def __str__(self):
    	return str(self.value)
        
class BST:
    def __init__(self):
        self.root = None
    def search(self, target, tree):
        if tree == None: return None
        if tree.value == target: 
            return tree
        if tree.value < target:
            return self.search(target, tree.right)
        else:
            return self.search(target, tree.left)

 

위는 BST의 가장 기본적인 탐색 코드입니다. 각 노드는 부모와, 두 자식 노드를 객체로 갖고있으며, 탐색하기를 원하는 값을 현재의 값과 비교하며 탐색하게 됩니다.

 

BST의 경우, 찾고싶은 값이 최악의 경우에도 Leaf 이하에는 존재할 수 없기 때문에 평균 O(logn)으로 탐색이 가능하다는 장점이 있습니다.

 

BST에서 값을 추가하고, 제거하는 것 역시도 추가 역시도 O(depth)로 가능하다는 장점이 있습니다.

 

 

 

물론 BST도 정말 큰 단점이 있습니다.

 

바로 "Skewed" 라는 현생이 발생할 수 있다는 것입니다.

 

즉, 아래 그림과 같이 한쪽으로만 일방적으로 자식노드가 생길 경우 n개의 노드에 대해서 탐색에 n만큼의 탐색이 필요할 수 있습니다.

 

이러한 문제를 방지하기위해 Bad-Black Tree라는 개념이 등장했습니다.

 

 

 

만........ 정말 많은 이미지를 통한 설명이 필요한 부분이기에... 차후에 뒤에서 다루도록하겠습니다.(꾸벅)

0. 시작하기

 - 대표적인 알고리즘 몇개를 10개정도의 게시물로 나눠 살펴볼 예정입니다.

 - 초점이 알고리즘인 만큼, 다양한 포인터의 활용이나, 복잡한 문법의 사용이 적은 파이썬을 통해 풀어낼 예정입니다.

 - 복습 차원에서 진행하다보니 특정 자료형에서 많이 사용되는 알고리즘임에도 깜빡하고 넘어갈 수 있으며, 내용에 오류가 있을 수 있습니다. 이러한 부분이 있으실 경우 댓글 부탁드리곘습니다.

 - 시작은 간단한 자료형에 대한부분으로 시작하겠습니다.

 

1. 리스트(List)

배열과 비교되는 자료 형태로, 일반적으로 크기를 미리 정해두고 순차적으로 자료를 저장하여 관리하는 배열과 다르게, [데이터와 포인터]의 형태로 만들어져, 포인터를 통해 연결되어 크기를 미리 정하지 않고도 얼마든지 객체의 추가와 제거가 가능한 데이터 형태입니다.

 

단일 연결리스트(출처 : 위키)

배열과 다르게 무한히 새로운 데이터를 연결하여 만들어 줄 수 있다는 장점이 있지만, Index를 통해 특정 데이터를 한번에 호출 할 수 없다는 단점도 있습니다. 때문에, 최악의 경우 N개의 객체를 갖은 리스트에서 특정한 값을 찾기위해서는 N번 탐색을 해야할 수 있습니다.

 

또한 위와같은 단일연결리스트에서는 다음 객체에 대한 포인터만을 갖기 때문에 이미 지나간 값을 참조하기 위해서는 다시 처음부터 리스트를 탐색해야하는 문제가 있습니다. 때문에 아래와 같이 여러 목적을 위한 몇가지 형태가 생겼습니다.

 

이중 연결리스트(출처 : 위키)
단순 원형 연결리스트(출처 : 위키)

 

 2. 스택(Stack)

대표적인 LIFO(Last In First Out)의 자료형입니다. 입력되는 데이터가 층층이 쌓이는 형태로 주로 아래 그림과 같이 표현되며, 운영체제, 메모리에 대한 개념을 다룰때 많이 다루는 자료형입니다.

 

스택(출처 : 위키)

 

3. 큐(Queue)

대표적인 FIFO(First In First Out) 형태의 자료형입니다. 네트워크에서 라우터, 스위치와 같이 데이터(패킷)를 수신하여 특정한 방향으로 다시 발송하는 형태(순차적인 처리)에서 많이 채용되어 사용중에 있습니다.

 

 

4. 정리

대표적인 자료형이고, 대부분의 언어에서 기본으로 제공하거나 대표적인 라이브러리로 제공되는 자료형이기 때문에 코드로 구현해보지는 않았습니다.

특히 스택이나 큐의 경우 단순한 배열에 포인터만 추가하면 되는 형태이기 때문에 더욱이 별도로 코드를 첨부하지는 않았습니다.

궁금한 부분은 댓글로 남겨주세요~

0. 정의

  • 그래프(G)는 정점(Vertex)와 간선(Edge)로 이루어집니다.   * G = (V, E)
  • 인접(Adjacent) : 간선(Edge)으로 연결된 두 정접(Vertex)
  • 완전그래프(Complete Graph) : 간선(Edge)의 개수가 최대인 그래프
  • 경로(Path) : 경로의 길이는 경로사이의 간선(Edge)의 수
  • Directed Graph : 방향성이 있는 간선(Edge)을 갖는 그래프
  • Undirected Graph : 방향성이 없는 간선(Edge)을 갖는 그래프

 

그래프는 아래와 같이 표현합니다.

그래프 예제

 

표를 이용한 그래프 표현

 

 

1. Graph Traversal

그래프의 탐색방법은 크게 두가지로 나눠집니다.

 

  • Depth First Search(DFS) : 깊이 우선 탐색
  • Breadth First Search(BFS) : 너비 우선 탐색

두 개념은 그래프와 트리와 같이 Vertex와 Edge로 이루어진 자료구조에서 사용되는 탐색방법입니다.

 

두개의 차이는 아래를 참고하면 쉽게 이해할 수 있습니다.

 

출처 : http://blog.hackerearth.com/wp-content/uploads/2015/05/dfsbfs_animation_final.gif

 

DFS는 순환호출 형태로 많이 구현하며 BFS는 Quere를 이용하여 쉽게 구현할 수 있습니다.

 

void DFS(Vertex* V)
{
	Edge* E = NULL;
    printf("%d ", V->Data);
    
    V->Visited = Visited;
    
    E = V->AdjacencyList;
    
    while(E != NULL){
    	if( E->Target != NULL && E->Target->Visited == NotVisited )
        	DFS( E-> Target );
        
        E = E->Nest;
    }
}
       

전체 알고리즘자료는 깃헙에 올리고있습니다. => https://github.com/yekyu94

 

yekyu94 - Overview

네트워크 프로그래밍 / 텐서플로우 / 보안 / 고양이. yekyu94 has 15 repositories available. Follow their code on GitHub.

github.com

 

 

+ Recent posts