알고리즘

그래프  연결되어 있는 객체 간의 관계를 표현하는 자료구조이다. 트리 역시 그래프의 특수한 형태이다.다음은 그래프의 기본적인 용어이다.정점(vertex) 혹은 노드(node): 각 객체간선(edge) 혹은 링크(link): 각 정점을 연결하는 선 혹은 관계부분 그래프(sub graph): 어떤 그래프의 정점과 간선의 부분집합으로 이루어진 그래프인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점차수(degree): 무방향 그래프에서 하나의 정점에 연결된 다른 정점의 수진입 차수(in-degree): 방향 그래프에서 하나의 정점으로 오는 간선의 수진출 차수(out-degree): 방향 그래프에서 하나의 정점에서 외부로 향하는 간선의 수경로(path): 한 정점에서 다른 ..

우선순위 큐 우선순위 큐는 일반적인 큐와 달리 우선순위가 높은 데이터가 먼저 나가는 큐이다. 따라서 일반적인 큐처럼 리스트로 구현하면 우선순위가 높은 데이터를 이동시킬 때, 즉 삽입, 삭제를 할 때 시간복잡도가 커지므로 트리를 이용한 힙으로 구현하는 것이 일반적이다. ADT 객체 (Object)0 개 이상의 우선순위를 가진 요소들의 모임연산 (Operation)create() ::= 우선순위 큐를 생성한다.init() ::= 우선순위 큐를 초기화한다.is_full() ::= 우선순위 큐가 가득 차 있다면 true 를, 아니라면 false 를 반환한다.is_empty() ::= 우선순위 큐가 비어있다면 true 를, 아니라면 false 를 반환한다.insert(item) ::= 우선순위 큐에 item을 추..

이진 탐색 트리 탐색작업을 효율적으로 하기 위해 정렬한 이진 트리이다.루트 노드의 값보다 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 있는 것이 특징이다. 이러한 특징 때문에 이진 탐색 트리를 최상위 노드부터 중위순회한다면 오름차순으로 정렬된 값을 얻을 수 있다. 탐색 탐색 연산은 이진 탐색 트리의 정렬을 이용한다. 최상위 노드의 값부터 비교를 시작하는데, 탐색하고자 하는 값과 같다면 탐색 종료, 탐색하고자 하는 값보다 크다면 그보다 더 작은 값을 찾아야 하기 때문에 외쪽 서브트리로 이동, 반대로 탐색하고자 하는 값보다 작다면 그보다 더 큰 값을 찾아야 하기 때문에 오른쪽 서브트리로 이동하여 탐색을 진행한다.예를 들어 트리에서 5를 탐색한다고 하면 아래와 같이 탐색한다. 탐색 값을 찾으면 해당..

스레드 이진 트리 이진 트리의 빈 포인터를 활용하여 트리 순회 속도를 향상시키기 위해 고안된 자료구조이다. 순회시 이진 트리에서 자식이 없는 노드를 만나면 일반적으로 부모노드로 돌아가지만, 스레드 이진 트리에서는 이 빈 포인터를 활용하여 그 다음 순회에 필요한 노드로 바로 찾아갈 수 있다.때문에 재귀 호출이나 스택 없이 순회가 가능하여 함수 호출에 필요한 시간을 효율적으로 절약할 수 있다.빈 포인터를 다음 순회 노드인 후속 노드(successor)를 가리키는 스레드로 활용하게 되면 해당 포인터가 더이상 빈 포인터가 아니기 때문에 일반적인 포인터인지 스레드인지가 구분 불가능해진다. 따라서 스레드 이진 트리의 노드는 해당 포인터가 스레드인지 아닌지를 나타내는 변수가 들어간다.이진 트리에서는 왼쪽과 오른쪽 자..

순회 (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)..