✔ 트리 트리(Tree)란? 노드와 엣지로 연결된 그래프의 특수한 형태 비선형 자료구조이며 계층적 관계를 표현 트리의 특징 순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재함 (방향성이 있는 비순환 그래프) 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐 노드가 N개인 트리는 항상 N - 1개의 간선을 가짐 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일함 트리를 순회하는 방식으로는 전위 순회, 중위 순회, 후위 순회, 레벨 순회가 존재 트리의 부분 트리 역시 트리의 모든 특징을 따름 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 엣지 (간선) : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 ..
✔ 힙 힙(Heap)이란? 배열을 기반으로 한 완전 이진 트리의 일종이므로 이진 힙(Binary Heap)이라고도 불림 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐 구현을 위해 만들어진 자료구조 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져나가게 됨 힙의 특징 힙의 종류로는 최대 힙과 최소 힙이 존재 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 반정렬 상태를 유지 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 삽입한 후, 새로운 노드를 부모 노드들과 교환하여 힙을 재구성 최대 힙(최소 힙)에서 최대..
✔ 큐 큐(Queue)란? 배열에서 발전된 형태의 선형 자료구조 삽입과 삭제 연산이 선입선출로 이루어지는 자료구조 큐의 특징 먼저 들어간 원소(First In First Out, FIFO)가 먼저 나옴 또는 나중에 들어간 원소(Last In Last Out, LILO)가 나중에 나옴 새 값 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어짐 O(N)의 시간 복잡도와 공간 복잡도를 가짐 삽입과 삭제가 양방향에서 이루어짐 큐는 빈 메모리가 남아 있어도, rear가 끝에 도달할 경우 꽉 차있는 것으로 판단할 수 있으므로 이를 개선하기 위해 처음과 끝이 연결되어 있도록 간주하는 원형 큐, 연결리스트 큐가 존재 큐 용어 rear : 큐의 가장 끝 데이터를 가리키는 영역 front : 큐에서 ..
✔ 스택 스택(Stack)이란? 배열에서 발전된 형태의 선형 자료구조 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조 스택의 특징 나중에 들어간 원소(Last In First Out, LIFO)가 먼저 나옴. 또는 먼저 들어간 원소(First In Last Out, FILO)가 나중에 나옴 새 값이 스택에 들어가면 top이 새 값을 가리킴 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 됨 O(N)의 시간 복잡도와 공간 복잡도를 가짐 해당 위치를 기억하고 있는 스택 포인터가 필요함 스택 포인터는 값이 들어갈 위치를 가리킴 스택 포인터가 최대 크기와 같으면 스택이 꽉 찬 것이며 스택이 꽉 찬 것이 아니라면 스택의 최상위 위치에 값을 저장 스택 포인터가 0이 되면 스택이 빈 것이며 스..
✔ 리스트 리스트(List)란? 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 트리 구조의 근간이 되는 자료구조 리스트의 특징 인덱스가 없어 값에 접근하려면 Head 포인터부터 순서대로 접근해야 하므로 속도가 느림 논리적 저장 순서와 물리적 저장 순서가 일치하지 않음 원하는 위치를 Search 하기 위해 첫 번째 원소부터 다 확인하며 순회 O(N)의 시간 복잡도로 해당 원소에 접근 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하므로 이 부분만 다른 값으로 바꿔 삭제와 삽입이 가능 O(1)의 시간 복잡도로 삽입, 삭제 가능 선언할 때 크기를 별도로 지정하지 않아도 됨 추가할 때마다 동적으로 메모리 할당을 받게 ..
✔ 배열 배열(Array)이란? 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 선언한 자료형의 값만 저장하여 연속적으로 이루어져 있음 불변하므로 기존 배열이나 값을 변경시키지 않고 주어진 배열이나 요소들을 기존 배열에 합쳐 새 배열을 반환 배열의 특징 인덱스를 사용하여 값에 바로 접근할 수 있음 논리적 저장 순서와 물리적 저장 순서가 일치 O(1)의 시간 복잡도로 해당 원소에 접근 가능 랜덤 접근이 가능 새로운 값을 삽입하거나 삭제할 때는 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하므로 어려움 배열은 연속적인 특징을 가져야 하므로 이를 위한 shift 비용인 O(N)의 시간 복잡도가 발생 배열의 크기는 선언할 때 지정하며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 메모리에는 배열..
