Computer Science and Engineering/Data Structure

순회 (Traversal) 트리에서 순회란 트리의 노드들을 체계적으로 방문하는 것을 말한다. 기본적으로 세 가지 순회방법이 있는데, 전위순회, 중위순회, 후위순회이다. 왼쪽 서브트리를 L, 오른쪽 서브트리를 R, 루트 노드를 V라 하면 전위순회의 순회 순서는 VLR, 중위순회의 순서는 LVR, 후위순회의 순서는 LRV이다. 즉 V의 위치에 따라 전중후로 나눈다.전중후 순회 외에 순회도 존재한다. 스택을 이용해 반복문으로 구현하는 반복적인 순회와 큐를 이용하여 구현하는 레벨 순회가 대표적이다.각 순회들은 방문 방법만을 제시할 뿐 방문하여 어떤 연산을 할 것인지는 따로 구현하면 된다. 각 노드의 값을 출력할 수도 있고, 리스트를 만들어 리스트에 순회 순서대로 넣을 수도 있겠다.이진트리 노드의 구조체는 아래와..

트리  트리는 일대다로 연결된 비선형자료구조로 계층적 자료구조이다. 노드로 구성되어 있으며 다음과 같은 용어를 사용한다.루트 노드(root node): 최상위 노드, 즉 부모가 없는 노드로 트리의 시작점부모 노드(parent node): 해당 노드의 위(루트 노드 방향)로 연결된 노드자식 노드(child node): 해당 노도의 아래(루트 노드 반대 방향)로 연결된 노드형제 노드(siblings node): 같은 부모 노드를 갖는 노드들조상 노드(ancestor node): 해당 노드 위로 연결된 모든 노드후손 노드(descendent node): 해당 노드 아래로 연결된 모든 노드단말 노드(terminal node): 자식이 없는 노드, 리프 노드(leaf node)라 부르기도 함간선(edge): 노드..

스택 기존 정적으로 구현한 스택은 스택의 크기가 유한하고, 한번 설정한 메모리 공간을 계속 사용한다는 단점이 있었다. 이를 연결 리스트로 구현하면 스택의 각 칸을 동적으로 할당하기 때문에 이러한 단점을 극복할 수 있다. 단 각 칸을 노드로 구현하기 때문에 칸 당 소비하는 메모리는 노드로 구현할 때 배열로 구현할 때보다 더 많다.기존에 스택은 top 변수를 배열 인덱스로 이용하였는데, 연결 리스트로 구현하게 된다면 헤드 포인터를 top 변수로 사용하게 된다.#include #include typedef int element;typedef struct Node { element data; struct Node* link;} Node;typedef struct { Node* top;} Stac..

이중 연결 리스트  연결 리스트를 원형으로 구현해도 자신을 가리키는 노드에는 접근할 수 없었기 때문에 근본적인 단점이 있었다. 이를 해결하기 위해 노드 링크를 좌측 노드 링크와 우측 노드 링크로 나누어 저장하는 이중 연결 리스트를 활용할 수 있다.이중 연결 리스트는 사용하는 노드가 링크를 좌측과 우측 두 개를 가지기 때문에 양방향 탐색이 가능하다. 단 그만큼 각 노드가 차지하는 메모리 공간이 크기 때문에 단점 역시 존재한다. 또한 장점을 살리려면 구현이 까다롭다는 단점이 있다.이중 연결 리스트는 단일 연결 리스트나 원형 연결 리스트처럼 헤드 포인터를 사용하는 것이 아니라 헤드 노드를 이용한다. 헤드 노드는 데이터가 없는 노드이다. 헤드 노드를 사용하여 시작 노드와 마지막 노드를 각각 우측 링크와 좌측 링..

원형 연결 리스트  노드 링크로 다음 노드를 가리키게만 하여 끝에 가면 NULL을 가리키게 되는 단일 연결 리스트는 자신을 가리키는 노드에는 접근할 수 없다는 단점이 있다. 예를 들어 세 번째 노드에서는 두 번째 노드로 접근할 수 없다.이를 해결하기 위해 가장 끝 노드가 처음 노드를 가리키게 하여 원형으로 리스트를 구현하는 방법이 있다. 이를 원형 연결 리스트라 하며, 원형 연결 리스트에서는 어떤 노드에서든 다음 노드를 향해 가기만 하면 연결된 모든 노드에 도달 가능하다.기본적인 연산은 연결 리스트와 같지만, 헤드 포인터가 가리키는 곳이 마지막 노드이고, 헤드 포인터의 링크가 가리키는 곳이 시작 노드라는 점이 단일 연결 리스트와 차이이다. 구현 | C 연결 리스트 구현과 같이 구현하였다. 단 앞서 말한 ..

연결 리스트  연결 리스트는 노드(node)로 구현된 리스트이다. 기존 배열을 통해 리스트를 사용하는 방식은 데이터 값을 연속적인 형태로 저장하기에 접근이 용이하다는 장점이 있었지만, 삽입과 삭제는 어렵다는 단점이 있었다. 즉 배열에서 접근은 임의접근이 가능하기 때문에 $ \mathcal{O}(1) $ 의 시간복잡도를 가졌지만, 삽입과 삭제는 최대 $ \mathcal{O}(n) $ 의 시간복잡도를 가졌다. 그러나 노드로 연결 리스트를 구현한다면 접근은 어렵다는 단점이 있지만, 삽입과 삭제가 상대적으로 쉽고, 고정된 크기를 가지지 않기에 유연하게 크기를 설정할 수 있다는 장점이 있다. 즉 접근에는 최대 $ \mathcal{O}(n) $ 의 시간복잡도를 가지지만, 삽입과 삭제는 $ \mathcal{O}(1)..

덱  덱(deque)은 double-ended queue의 줄임말, 즉 양쪽 방향에서 삽입과 삭제가 가능한 큐이다.데이터 추가와 삭제가 전열(front)와 후열(rear) 모두에서 가능하기 때문에 스택이나 단순 큐보다 유연하게 사용 가능하다는 장점이 있다. ADT 객체 (Object)0 개 이상의 요소들로 구성된 선형 리스트연산 (Operation)create(size) ::= 최대 크기가 size 인 공백 덱을 생성한다.init() ::= 덱를 초기화한다.is_full() ::= 덱의 원소 개수가 size 와 같다면 true 를, 아니라면 false 를 반환한다.is_empty() ::= 덱이 비어있다면 true 를, 아니라면 false 를 반환한다.add_front(item) := 덱이 가득 차 있지..

원형 큐  선형 큐는 구현하였을 때 전열과 후열이 큐를 사용하면서 지속적으로 증가하기 때문에 전열과 후열이 배열의 끝에 도달한다면 배열의 앞 부분이 비어있더라도 사용하지 못하는 단점이 있다. 이를 보완하기 위해 모든 요소를 왼쪽으로 이동시킬 필요가 있는데, 실제 데이터를 이동시키기 위해서는 추가 연산도 필요하고, 구현도 복잡해지기 때문에 다른 방법이 필요하다.이러한 단점을 극복한 것이 원형 큐이다. 원형 큐는 배열을 선형이 아니라 원형으로, 즉 전열과 후열을 연결하여 배열의 끝에 도달하더라도 지속적으로 큐를 사용할 수 있게 하는 것이다. 실제로 배열을 원형으로 만드는 것은 아니고 후열이 배열의 끝에 도달하면 다시 전열을 사용하도록 하여 개념적으로 원형을 만들어 사용한다.큐를 어떻게 구현할 것인가가 다를 ..

큐  큐는 선입선출(FIFO, first in first out) 방식으로 동작하는 자료구조이다. 즉 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다는 뜻이다. 일상에서 흔히 볼 수 있는 줄 서기 상황이 이와 유사하다. 줄을 먼저 선 사람이 먼저 빠져나가는 방식에서 큐의 작동원리를 생각해 볼 수 있다.즉 데이터 추가는 후열(rear)에서만 일어나고 데이터 삭제는 전열(front)에서만 일어난다. 데이터를 처리할 때 순서를 보장하는 성질이 있는 것이다. 때문에 공정하게 데이터를 처리하는 대기열, 프로세스 스케줄링 등에 사용된다. ADT 객체 (Object)0 개 이상의 요소들로 구성된 선형 리스트연산 (Operation)create(size) ::= 최대 크기가 size 인 공백 큐를 생성한다.init() ..

스택  스택이란 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조이다. 즉 마지막에 삽입된 데이터가 가장 먼저 삭제된다는 뜻이다. 무엇인가를 쌓고 나서 치우려고 하면 가장 나중에 쌓은 것인 가장 위부터 치워야 하는 것과 같다. 웹 브라우저의 뒤로 가기 기능이나 프로그램에서 괄호가 제대로 열고 닫혔는지 검사할 때 사용되기도 한다.이러한 성질 때문에 스택은 가장 상위 데이터에만 접근할 수 있다. 상위 데이터를 삭제하거나, 확인하는 것은 가능하지만, 그 아래 데이터에 접근하려면 상위 데이터를 제거해 나가면서 접근해야 한다. 최상위 데이터에만 접근할 수 있다는 것은 최상위 데이터만 관리하면 된다는 뜻이기에 데이터를 관리하는 데에 드는 자원을 적게 소모한다는 뜻이기도 하다. ..