자료구조 (6) 썸네일형 리스트형 Tree Tree 트리 자료구조 트리는 노드 들이 나무가지처럼 연결된 비선형적 자료구조이다. 선형적 자료구조는 하나의 자료 뒤에 하나의 자료가 존재한다. 자료들간의 앞과 뒤 관계가 1대 1인 경우를 선형적이라고 얘기한다. 비선형은 그렇지 않은 경우라고 생각하면 편할 것 같다. 트리의 이미지를 보면, 한 눈에 보기에도 비선형적 자료구조라는 것을 알 수 있다. 마찬가지로 하나의 트리가 또 다른 트리를 포함할 수 있으며, 이는 재귀적 자료구조라고 볼 수 있다. 트리의 용어 트리 구조에서 주로 사용하는 몇 가지 용어가 존재한다. 자주 쓰는 용어들만 정리하자면 다음과 같다. Node: 트리를 구성하는 기본 요소 Edge: Node와 Node간의 연결 선 Root Node: 트리 구조에서 부모가 없는 최상위 Node Par.. Heap HEAP 구조 Heap 구조는 우선순위 큐를 위하여 만들어진 자료구조이다. 내부적으로 완전 이진트리의 구조를 가지고 있으며, 우선순위 큐를 구현하기 위하여 사용한다. 힙 내부의 데이터들은 모두 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다. 스택은 LIFO, 큐는 FIFO였다면, 우선순위큐는 우선순위에 따라 먼저 나가는 데이터가 결정된다. 힙은 최댓값이나 최솟값을 빠르게 찾는 것에 목적이 있다. (기준에 따라 다를 수 있다.) 힙 트리에서는 중복된 값을 허용하는데, 이 부분이 이진 탐색 트리와의 차이점이다. HEAP의 구현 힙을 저장하는 표준적인 자료 구조는 배열이다. DivisionByZero를 방지하기 위하여 첫 번째 인덱스인 0은 사용하지 않는다. 또한 특정 위치의 노드 번호는 새로.. Recursive 재귀함수 재귀함수는 정의 단계에서 자기 자신을 재참조하는 함수를 뜻한다. 간단한 예시는 다음과 같다. int factorial(int n) { if (n == 1) return (1); return (n * factorial(n - 1)); } 팩토리얼을 간략하게 구현해놓은 함수이다. 함수 내부의 정의에서 자기 자신을 다시 참조하는데, 이러한 구조를 지니는 함수를 재귀함수라고 한다. 모든 반복문으로 이루어진 함수는 재귀로 표현이 가능하며, 그 역도 성립한다. 재귀함수가 자기 자신을 호출할 때마다 콜스택에 쌓이게 된다. 특정 분기(종료 조건)을 만나게 될 때까지 스택처럼 쌓이게 될 것이다. 이러한 재귀함수를 구현할 때 개발자의 실수로 종료 조건을 설정하지 않거나, 결과값이 제대로 수렴하지 않는 경우에는 스.. Queue Queue Queue는 선입선출의 구조를 따른다고 한다. Enqueue 명령에서는 새로 들어온 원소가 꼬리쪽에 붙는다. Dequeue 명령에서는 가장 먼저 들어온 원소가(오래된 원소) 먼저 나간다. Stack이 후입선출의 구조였던 것에 반해, queue는 처음 원소와 끝의 원소를 잘 다뤄줘야한다. ArrayQueue와 LinkedQueue의 형태로 만들면 되는데, ArrayQueue에서는 고민해봐야 하는 지점이 있다. ArrayQueue에서는 [0, 1, 2, 3] 의 큐에서 0이 빠져나간 경우. [-, 1, 2, 3] 의 형태가 되어서 빈 자리가 있음에도 그 다음 원소가 들어오지 못할 수 있다. 이러한 경우 circularArrayQueue의 형태로 만들면 해결이 가능하다. 현재 끝 번호 (ex: 4).. Stack Stack 출처: 나무위키 특징 Stack 자료구조는 LIFO(후입 선출)이라는 특징을 가지고 있다. FIFO(선입선출)의 특징을 가지는 큐 형태와 반대이다. 구현은 큐에 비해서 쉬운 편이나, 응용할 예시가 매우 많다. Stack ArrayStack 사용 예시. ArrayStack은 스택의 용량을 미리 정해둔다. 솔직히 LinkedStack에 비해서 구현이 매우 쉬웠다. topNode의 정보만 수정/추가/제거 해주면 되기 때문에 maxElementCount를 넘어서는 push는 받지 않고, empty인 경우만 잘 처리해주면 쉽게 구현이 가능했다. createArrayStack ArrayStack *createArrayStack(int maxElementCount) { ArrayStack *array; a.. Array List, Linked List Linked List와 ArrayList의 장단점 LinkedList ArrayList 장점 동적으로 자료를 다룰 수 있다. 리스트 내에서 자료의 이동이 필요하지 않다. 사용 후 기억 장소의 재사용이 가능하다. Index를 이용해서 빠르게 접근할 수 있다. (시간복잡도 O(1)) LinkedList에 비해서 고려할 사항이 적다. 데이터 개수가 확실하게 정해져 있고, 접근이 빈번한 경우 배열이 효율적이다. 단점 탐색이 느리다. 구현이 어렵다. 포인터의 사용으로 인해 저장 공간의 낭비 우려가 있다. 동적으로 자료를 다룰 수 없다. LinkedList에 비해서 자료의 추가 삭제가 느리다. 연속적인 형태 유지를 위해 shift 연산을 해야하므로 (O(N))이 된다. 10개 생성 삭제 test linked [ti.. 이전 1 다음