728x90 반응형 전체 글58 자료구조 - 맵 (Map) 1. 맵이란? 맵(Map)이란 탐색 가능한 Key와 Value로 이루어진 객체를 저장하는 자료구조로 Set과 같이 Key값의 중복을 허용하지 않으며 value값은 제약이 없다. 삽입, 삭제, 탐색의 세 가지 연산을 지원한다. 구현 방식에 따라 해쉬 맵, 트리 맵 등이 존재한다. 각각의 특징은 해쉬 세트, 트리 세트와 동일하다. 2021. 1. 27. 자료구조 - 세트 (Set) 1. 세트란? 세트(Set)이란 집합을 정의하는 자료구조로 동일한 자료형을 모아놓은 것이다. 집합의 모든 원소(Key)는 유일해 중복이 허용되지 않는다. 삽입, 삭제, 탐색의 세 가지 연산을 지원한다. 구현 방식에 따라 해시 셋, 트리 셋 등이 존재한다. 2. 해시 세트 - 해시 세트(Hash Set)이란 해싱을 이용해 데이터를 저장하는 방법 - 모든 연산이 O(1)에 수행되기 때문에 가장 빠르다. - Key값을 나열했을 때 순서를 예측할 수 없다. 3. 트리 세트 - 트리 세트(Tree Set)이란 일반적으로 균형 이진 검색 트리(Balanced Binary Search Tree) 중 레드 블랙 트리(Red-black Tree)로 구현되어 있다. - 모든 연산이 O(logN)에 수행된다. - key 값.. 2021. 1. 27. 자료구조 - 트라이 (Trie) 1. 트라이란? 트라이(Trie)란 Prefix Tree, Digital Tree, Retrieval Tree라고도 부르며 문자열을 빠르게 검색할 수 있는 자료 구조이다. K진 트리 구조 이고 단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다. 트라이의 Root 노드는 항상 공백문자열(빈 문자열) 상태를 의미한다. 2. 트라이 구축하기 ① 트라이 노드 설계 class Node Ojbect data Node child[] ② 단어 사전의 입력할 단어를 트라이에 삽입 ③ 루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색 ④ 만약 현재 노드의 자식 노드 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동 ⑤ 만약 현재 노드의 자식 노드 중 현재.. 2021. 1. 27. 자료구조 - 인덱스 트리 (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. 이전 1 ··· 4 5 6 7 8 9 10 다음 728x90 반응형
