728x90 반응형 BASE34 자료구조 - 인덱스 트리 (Indexed Tree) 1. 인덱스 트리란? 인덱스 트리(Indexed Tree)란 포화 이진트리 형태의 자료구조로 리프 노드는 배열에 적혀있는 수를 의미하고 내부 노드는 왼쪽 자식과 오른쪽 자식의 합을 이야기 한다. 리프 노드의 개수가 N개 이상인 포화 이진트리는 높이가 최소 logN이다 리프 노드의 개수가 N개 보다 많아 비어있는 공간이 발생할 경우 구조에 지장이 가지 않도록 초기값을 설정한다. 2. 트리 구성 방법 ① 리프 노드의 개수가 N개 이상이 되도록 높이가 T인 트리 배열을 만든다. 배열 크기 : 2^T ② 리프 노드에 데이터를 입력한다. ③ 내부 노드를 양쪽 자식 값을 참조하여 데이터를 입력한다. ◈ 트리의 노드 개수는 꽉 찬 트리에서 약 2N개 이다. 따라서 수행 시간은 O(N)이다. 3. 구간합 구하는 쿼리 .. 2021. 1. 27. 자료구조 - 힙 (Heap) 1. 힙이란? 힙(Heap)이란 완전 이진트리 형태의 자료구조로 힙 조건을 만족한다. 일차원 배열로 구현할 수 있고 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다. 2. 최소 힙과 최대 힙 최소 힙과 최대 힙은 각각 다음 Heap Condition을 가지는 대표적인 유형의 힙이다. 부모노드의 키 값이 자식노드의 키 값보다 작은(큰) 관계가 유지되므로 트리 내에서 가장 작은(큰) 키 값을 가진 노드는 항상루트 노드가 된다. 1) 최소 힙 (Min Heap) : 부모노드의 키 값이 자식노드의 키 값보다 항상 작다. 2) 최대 힙 (Max Heap) : 부모노드의 키 값이 자식노드의 키 값보다 항상 크다... 2021. 1. 27. 자료구조 - 이진 트리 (Binary Tree) 1. 이진 트리란? 이진 트리(Binary Tree)란 트리의 분지 수(자식 노드의 개수)가 2 이하인 트리로 대부분의 트리 자료구조는 이진 트리 형태에서 나온다. 2. 이진 트리의 종류 1) 정 이진 트리 (Full Binary Tree) - 모든 노드의 차수가 0 또는 2인 이진 트리 2) 포화 이진 트리 (Perfect Binary Tree) - 정 이진 트리에서 모든 단말 노드의 깊이가 같은 이진 트리 - 높이가 H인 포화 이진 트리의 노드 개수는 2^H-1개이다. - 반대로 노드가 N개인 포화 이진 트리의 높이는 log(N+1)이다. - 깊이가 D인 포화 이진 트리의 단말 노드 개수는 2^D개이다. 3) 완전 이진 트리 (Complete Binary Tree) - 마지막 레벨은 노드가 왼쪽에 몰.. 2021. 1. 27. 자료구조 - 트리 (Tree) 1. 트리란? 트리(Tree)란 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현된다. 트리는 1개 이상의 노드를 갖는 집합으로 루트 노드가 존재하고 트리의 부분트리(SUb Tree) 또한 트리 구조를 따른다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다. 2. 트리와 관련된 용어 루트 노드(root node) : 트리의 최상위 노드로 유일하다. 깊이 (Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수로 루트 노드는 자기 자신까지 도달하는 간선의 개수가 0.. 2021. 1. 27. 자료구조 - 연결 리스트 (Linked List) 1. 연결 리스트란? 연결 리스트(Linked List)란 불연속적 메모리 공간에 데이터를 빈틈없이 저장하며 노드를 연결하여 만든 리스트로 첫 번째 노드를 헤드, 마지막 노드를 테일이라고 한다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다. 크기가 고정되어 있지 않아 크기 제한에서 자유롭다. 인덱스 접근이 불가능하다. 2. 시간 복잡도 1) 삽입 - 리스트의 맨 앞/뒤에 삽입하는 경우 : O(1) - 리스트의 중간에서 삽입하는 경우 : O(n) (탐색) 2) 삭제 - 리스트의 맨 앞/뒤에 삭제하는 경우 : O(1) - 리스트의 중간에서 삭제하는 경우 : O(n) (탐색) 3) 탐색 - O(n) 3. 장단점 1) 장점 - 포인터로 연결되어 있어 포인터가 가리키는 노드만 변경하면 되기 때문.. 2021. 1. 26. 자료구조 - 배열(Array) 1. 배열이란? 배열(Array)은 가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조로 연속된 메모리 공간에 순차적으로 저장한다. 배열의 크기는 고정되어 있고, 선언할 때 크기를 정하고 후에 변경할 수는 없다. 2. 시간 복잡도 1) 삽입 / 삭제 - 배열의 맨 앞에 삽입 / 삭제하는 경우 : O(n) - 배열의 맨 뒤에 삽입 / 삭제하는 경우 : O(1) - 배열의 중간에 삽입 / 삭제하는 경우 : O(n) 2) 탐색 - O(n) 3. 장단점 1) 장점 - 인덱스를 가지고 있어 바로 접근 가능하다. (자료의 크기가 클수록 매우 유리) - 연속된 메모리 공간에 존재하기 때문에 관리가 편리하다. - 구조가 간단하여 프로그램 작성이 쉽다. 2) 단점 - 데이터 삽입 / 삭제가 어렵다... 2021. 1. 26. 이전 1 2 3 4 5 6 다음 728x90 반응형
