UpWrite

일러두기 # 선형구조에서는 데이터를 저장하고 꺼내는 것이 중요한 작업이었지만 비선형구조에서는 저장된 데이터가 그 구조로 잘 표현되어 있는지가 더 중요하다. # 즉, 삽입과 삭제는 데이터의 표현을 위해 기본적으로 제공되는 것이고, 목적에 맞는 검색과 순회가 가능한지가 더 중요하다. 트리의 구현 # 저장과 삭제가 빈번하게 이루어져야 한다면 트리를 배열을 기반으로 구현하는 것은 비효율적이다. # 하지만 데이터의 구조가 완전이진트리라면 배열로 구현하는 것이 검색과 순회에 있어서 더 효율적일 수 있다. # 그리고 이러한 구조의 완전이진트리는 다음에 소개할 힙에 활용된다. 배열로 구현한 완전 이진트리의 특징 # 뿌리 노드의 인덱스가 0일 경우 1) 인덱스 [K]에 있는 노드의 왼쪽 자식은 인덱스 [2*K+1]에 오..

트리의 정의 # 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다. # 트리란 정점(vertex)과 정점과 정점 사이를 연결시켜주는 간선(edge)으로 이루어진 순환 구조가 없는 특별한 형태의 연결 그래프(Graph)의 일종이다. # 즉, 트리는 이 다음에 다룰 그래프의 특수한 형태이다. 이 정의는 그래프를 공부하고 나면 더 잘 이해가 될 것이다. # 트리는 다음 조건들을 만족하는 하나 이상의 노드로 구성된 유한 집합이다. 1) 모든 노드가 시작되는 특정한 뿌리 노드(root node)가 존재한다. 2) 노드와 노드 사이의 간선이 하나만 존재한다. 3) 각 노드들 사이에 순환이 존재하지 않는다. 4) 뿌리 노드를 제외한 다른 노드들도 자신을 뿌리 노드로 하는 트리..

덱 # 리스트의 양쪽 끝 모두에서 입출력을 할 수 있는 자료구조이다. # 큐와 스택의 개념을 일반화시킨 자료구조라고 할 수 있다. # 연결 리스트나 배열 기반으로 만들 수 있는데 배열 기반으로 하면 원형큐의 형태로 만들어 중앙부분부터 채워넣는다. # 덱이 비어있는 상태에서 데이터를 빼려고 하면 널포인터를 반환한다. 덱의 변형 # 한 쪽 끝에서의 삽입 작업에 제한을 둔 덱을 입력제한덱(Input restricted deque) 혹은 스크롤(Scroll)이라 한다. # 구현은 앞부분에 삽입하는 것을 제한하는 형태로 만들었다. # 한 쪽 끝에서의 제거 작업에 제한을 둔 덱을 출력제한덱(Output restricted deque) 혹은 셸프(Shelf)라고 한다. # 구현은 뒷부분에서 제거하는 것을 제한하는 형..

원형큐 # 일반적인 큐가 시작과 끝이 있는 선분의 형태라면 원형큐는 시작과 끝을 이어 고리형태를 이루게 한 구조이다. 배열 기반 큐의 문제점 # 배열 기반의 큐를 선형큐로 만들면 문제가 되는 것이 두가지 있다. # 첫째는 front를 항상 0번 인덱스로 유지하기 위해서는 Remove때마다 데이터를 이동시켜야 한다는 것이다. # 이를 해결하기 위해서는 Remove시에 front의 인덱스를 다음 인덱스로 이동시켜야만 한다. # 두번째 문제는 Add와 Remove를 반복할 시 Front와 Rear의 위치가 배열의 뒷부분으로 이동되어 앞부분에 공간이 있음에도 오버플로우가 발생한다는 것이다. 배열 기반 큐의 문제 해결 방법 # 배열 기반의 큐에서 이를 해결하는 방법은 두가지다. # 하나는 오버플로우가 발생했을 때..

큐 # 큐는 영어로 줄이나 대기 행렬을 의미하는 단어로, 먼저 들어온 데이터가 먼저 빠져나가는 구조의 리스트이다. # 영어로는 'FIFO(First In First Out)' 혹은 'LILO(Last In Last Out)' 구조의 자료구조로 불린다. # 입구와 출구가 각각 있는 구조라고 생각하면 이해하기 편하다. (이때 입구로 나가거나, 출구로 들어오는건 불가능하다고 가정한다.) # 일반적으로 줄의 출구 즉 큐의 맨 앞을 Front, 줄의 입구 즉 큐의 맨 끝을 Rear라고 한다. # 일반적으로 큐에 데이터를 넣는 행위를 Enqueue 혹은 Add, 큐에서 데이터를 빼는 행위를 Dequeue 혹은 Remove라고 한다. # 큐도 배열이나 연결 리스트를 이용해서 구현할 수 있다. # 하지만 큐를 배열로 ..

연결 리스트 기반 스택 # 스택을 연결 리스트를 이용해서 구현하면 스택의 크기를 신경쓰지 않아도 된다는 장점이 있다. # 연결 리스트 기반의 스택은 pTop(=pHead) 포인터가 가리키는 노드를 바꿔주는 것으로 구현이 가능하다. # push가 되면 새로운 노드를 리스트의 맨 앞에 연결한 뒤 pTop을 새로운 노드를 가리키게 한다. # Pop이 되면 pTop의 노드를 삭제하고 pTop이 그 다음 노드를 가리키게 한다. STL의 스택 # STL에서는 선형 구조의 컨테이너를 통해 스택 구조를 이용할 수 있다. (배열 기반도 가능하고, 연결 리스트 기반도 가능하다는 뜻) 연결 리스트 기반 스택의 ADT 1. 스택에 데이터를 넣는다. (Push) 2. 스택에서 데이터를 뺀다. (Pop) 3. 스택 맨 위의 데이..

스택 # 스택이란 먼저 들어온 자료가 마지막에 나오고, 마지막에 들어간 자료가 가장 먼저 나오는 구조를 가진 일종의 리스트이다. # 영어로는 'FILO(First In Last Out)', 'LIFO(Last In First Out)' 구조의 자료구조라고 불린다. # 현실의 쌓여있는 책더미나 동전 지갑, 한쪽만 뚤려있는 통등을 생각하면 이해하기 편하다. # 일반적으로 스택에 가장 나중에 들어온 데이터의 위치를 Top, 가장 처음에 들어온 데이터의 위치를 Bottom이라 한다. # 일반적으로 스택에 데이터를 넣는 행위를 Push, 데이터를 빼는 행위를 Pop, Top의 데이터를 확인하는 행위를 Peek이라 한다. # 스택이 비어있을 때 데이터를 빼려고 하면 Underflow가 발생하고, 스택이 가득 차있을..

이중 원형 연결 리스트 # 이중 원형 연결 리스트는 마지막 노드가 첫번째 노드를 가리키고, 첫번째 노드도 마지막 노드를 가리키게 함으로 원형 구조를 이루게 한 이중 연결 리스트다. # 그러므로 순회시 따로 끝을 지정하지 않는한 무한 루프를 돌게 된다. # 앞에 두개는 처음이나 끝에 도달했는데도 계속 prev나 next를 호출하면 각각 첫 노드나 끝 노드를 계속 반환하도록 했었다. # 앞에 두개에서는 Head포인터와 Tail포인터 두개를 사용했으나 Head포인터 하나로 두 위치를 모두 표시할 수 있다. (Head의 prev가 Tail임으로) # 연결 리스트의 특성상 특정 위치의 노드를 찾기 위해서는 각각의 노드를 거쳐가야 하므로 최악의 경우 size만큼의 노드를 확인해야한다. # 하지만 이중 원형 연결 리..

이중 연결 리스트 # 이중 연결 리스트에서는 이전 노드가 다음 노드의 포인터를, 다음 노드는 이전 노드의 포인터를 가지고 있다. # 그러므로 시작에서만이 아니라 앞에서뿐만 아니라 뒤에서부터도 순회가 가능하다. # 삽입, 삭제 위치에 따른 분류는 이후에 다룰 '스택', '큐', '덱'으로 이루어지므로 이에 자세한 고민은 안했다. # STL에서는 list가 이 구조이다. (즉, 실제로 사용하게 되는건 STL의 ) 단일 연결 리스트의 ADT 1. 원하는 위치에 노드를 추가할 수 있다. 2. 원하는 위치의 노드를 삭제할 수 있다. 3. 원하는 위치의 노드의 값을 수정할 수 있다. 4. 리스트 전체를 양방향으로 순회할 수 있다. 5. 리스트의 전체 노드수를 확인할 수 있다. 6. 리스트가 비어있는 경우는 사용자가..

연결 리스트 # 연결 리스트는 노드가 '데이터'부분과 다음 노드를 가리키는 '링크'부분으로 이루어진 리스트이다. # C/C++에서는 연결 리스트의 링크 부분을 포인터로 구현하며 그렇기에 선형 리스트와는 달리 연속된 메모리 공간을 필요로 하지 않는다는 장점이 있다. # 연결 리스트는 어떻게 연결하느냐에 따라서 '단일 연결 리스트', '이중 연결 리스트', '원형 연결 리스트'등으로 나뉜다. # (Chunked List)라는 것도 있다는 것 같은데 잘 모르겠으므로 생략한다. # 단일 연결 리스트는 이전 노드가 다음 노드를 가리키는 포인터만 가지고 있는 구조이다. 단일 연결 리스트의 ADT 1. 원하는 위치에 노드를 추가할 수 있다. 2. 원하는 위치의 노드를 삭제할 수 있다. 3. 원하는 위치의 노드의 값을..