왕초보개발자

세그먼트 트리(Segment Tree) 여러개의 데이터가 연속적으로 존재할 때 특정한 범위에 속하는 데이터들의 합을 구하는 방법 방법 1️⃣ 단순 배열을 이용해 선형적으로 구하기 e.g.) [5 8 7 3 2 5 1 8 9 7 3] 데이터를 순차적으로 하나씩 더하므로 O(n)의 시간복잡도 index 0 1 2 3 4 5 6 7 8 9 10 11 array 5 8 7 3 2 5 1 8 9 8 7 3 ➡ array[1]부터 array[10]까지의 부분합 : 58 (차례대로 하나씩 더함) 방법 2️⃣ 트리 구조를 이용하여 구하기 각 노드마다 구간합을 저장하여, 트리의 특성상 O(logN)의 시간복잡도 구간합 트리 생성 트리 배열의 크기 기존 배열의 크기 => N = Segment Tree에서 leaf node..

Red-Black 트리(Red-Black Tree) Abstract 불균등상태를 방지하기 위해 균형을 맞추는 이진탐색트리 의 일종 레드블랙트리의 Search는 O(logN) 조건 Root Property: 루트 노드의 색깔은 검정(Black) 이다. External Property : 모든 External Node(자식이 없는 노드)의 색깔은 검정(Black) 이다. Internal Property : 빨강(Red) 노드의 자식은 검정(Black) 이다. (= No Double Red, 빨강 노드는 연속해서 나올 수 없다.) Depth Property : 모든 leaf 노드에서 Black Depth는 같다 모든 leaf 노드에서 root 노드까지 가는 경로에서 만나는 검정(Black)색 노드의 개수는 같..

AVL 트리 Abstract 스스로 균형을 잡는 이진탐색트리 트리의 높이가 h이고 불균등상태(편향이진트리)라면 이진탐색트리의 시간복잡도는 O(h) 이를 방지하고자 높이 균형을 유지하는 트리가 AVL 트리 특징 이진탐색트리의 속성을 가짐 왼쪽, 오른쪽 서브트리의 높이 차는 최대 h 어떤 시점에서든지, 두 서브트리의 높이차이가 2이상이되면 회전을 통해 균형을 맞춤 AVL트리는 높이를 logN으로 유지하기 때문에 삽입, 삭제, 검색의 시간복잡도는 O(logN) Balance Factor(BF) 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺸 값 Balance Factor(k) = height(left(k)) = height(right(l)) BF = 1 : 왼쪽 서브트리의 높이가 오른쪽 서브트리의 높이보..

B+ Tree 데이터의 빠른 접근을 위해 비단말(Non Leaf) 노드는 인덱스 역할만 수행 B 트리 + Leaf 노드들의 데이터는 연결리스트로 표현된 색인 구조 실제 DB에서 사용하는 인덱싱 Index 부분 과 Leaf Node로 구성된 순차 데이터 부분 으로 이루어짐 인덱스 부분의 key값은 leaf에 있는 key값을 직접 찾아가는데 사용함 leaf 노드는 연결리스트 형태, 선형 검색이 가능 특징 루트노드는 적어도 2개 이상의 자식을 가져야함 루트노드를 제외한 모든 노드는 M/2개 부터 M개의 자식을 가짐 노드에는 최소 [M/2]-1개 부터 최대 M-1개의 키를 포함 노드의 자료수(key)가 x개라면, 자식수는 x+1개 여야함 최소 차수(t)는 자식수의 하한값을 의미, 최소차수가 t가 2라면 M = ..

B-Tree 이진트리는 하나의 부모가 두개의 자식밖에 갖지 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(N)) 으로 떨어진다. 하지만 이진트리가 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN) 으로 보이는 장점이 있다. Abstract DB, 파일시스템에서 널리 쓰이는 트리 자료구조의 일종 이진트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree 자식수에 대해 일반화를 진행하면서, 하나의 레벨에 자식을 더 많이 저장하는 것이 아니라 트리의 균형을 자동으로 맞추는 로직까지 구현 단순하고 효율적, 레벨로만 따지만 완전히 균형을 맞춘 트리 멀티레벨 인덱싱을 통해 빠른 검색이 가능 규칙 M차 B 트리 ➡️ 최대 M개의 자식 을 가질 수 있는 B 트리 루트노드는 적어도 2..

트라이(Trie) 문자열에 대한 검색을 빠르게 도와주는 자료구조 Abstract 문자열에 대해 이진탐색트리를 적용하면 ➡️ 문자열의 길이(M) + 문자열의 총 개수(O(log(N)) ➡️ O(Mlog(N)) 의 시간복잡도 트라이를 적용하면 ➡️ O(M) 으로 문자열 검색이 가능 e.g.) [bear, bell, bid, bull, buy, sell, stack, stop] (N = 8) BST for Strings 문자열의 개수(N)만큼 비교하기 때문에 O(logN) 가장 길이가 긴 문자열의 길이가 M이라면 두 문자열을 비교하는데 O(M) 총 O(MlogN)의 시간복잡도 Trie for Strings 트라이(Trie)를 활용 한 Tree의 leaf node의 갯수는 문자열의 총 개수(N)과 동일하다 O(..

해시(Hash) Abstract 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터(input)을 고정된 길이의 데이터(key)로 매핑하는 것 해시 함수를 구현하여 데이터를 해시 값으로 매핑 사용 이유 적은 자원으로 많은 데이터를 효율적으로 관리 하기 위함 하드 디스트나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 적은 메모미로도 프로세스 관리가 가능해짐 input에 대해 언제나 동일한 Hash 값을 리턴, index를 알면 빠른 데이터 검색 이 가능해짐 검색시 해시 테이블의 시간 복잡도는 O(1) (이진탐색트리는 O(logN) 해시 충돌(Hash Collsion) 데이터가 많아지면, 다른 데이터에 대해 동일한 해시 값으로 충돌이 일어나는 현상(비둘기집 원리) 해시 충돌(H..

이진 탐색 트리(Binary Search Tree, BST) 이진 탐색 과 연결 리스트 의 장점을 결합 Abstract 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN) 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), 탐색의 시간복잡도는 O(n) => 두가지를 합하여 장점을 모두 취하는 것이 이진탐색트리 => 효율적인 탐색을 하며, 자료의 삽입/삭제도 용이하게 하기 위함 특징 모든 노드의 자식은 2개 이하 모든 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 중복된 노드가 없어야함 중복된 노드가 없어야 하는 이유 검색목적 자료구조인데, 굳이 중복이 많은 경우에 BST를 사용하여 검색속도를 느리게 할 필요가 없음 중복이 많다면 트리에 삽입하는 것보다, Count를 두어 처리하는 것이..

트리(Tree) Abstract Node 와 Edge 로 이루어진 자료구조 Cycle이 존재하지 않는다.(Cycle이 존재한다면 트리가 아니라 그래프) 모든 노드는 자료형으로 표현 가능 루트에서 어떤 노드로 가는 경로는 유일(오직 1개) 노드가 N개면 간선은 N-1개를 갖는다. 순회 방식 전위순회(Pre-Order) Parent -> Left child -> Right child 순으로 방문 1 ➡️ 2 ➡️ 4 ➡️ 8 ➡️ 9 ➡️ 5 ➡️ 10 ➡️ 11 ➡️ 3 ➡️ 6 ➡️ 13 ➡️ 7 ➡️ 14 중위순회(In-Order) Left Child -> Parent -> Right child 순으로 방문 8 ➡️ 4 ➡️ 9 ➡️ 2 ➡️ 10 ➡️ 5 ➡️ 11 ➡️ 1 ➡️ 6 ➡️ 13 ➡️ ..

힙(Heap) Abstract 우선순위 큐 를 위해 만들어진 자료구조 완전 이진 트리 의 일종(여러 값 중, 최댓값과 최솟값을 빠르게 찾아내도록 만들어진 자료구조) 반정렬 상태(느슨한 정렬상태) 힙트리는 중복허용, 이진 탐색 트리는 중복허용 X 우선순위 큐 우선순위 개념을 큐에 도입한 자료구조 큐의 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나감 배열, 연결리스트, 힙으로 구현할 수 있는데 힙(heap)이 가장 효율적 완전 이진 트리 마지막 레벨을 제외한 모든 레벨이 완전히 채워져있는 트리 적합할 때 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 힙의 종류 최대힙(Max Heap) 부모노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전이진트리 최소힙(Min Heap) 부모..

Array VS. Linked List Array index로 빠르게 값을 탐색(O(1)) 선언시 크기와 데이터 타입 을 지정해야함 -> 연속적인 메모리 공간을 미리 할당하여 사용하는 자료구조 사이즈가 정적임기 때문에 최대 사이즈를 알 수 없을때 부적합(추가적인 공간을 할당하고 전부 옮겨줘야함) Linked List 한 노드에 연결될 노드를 포인터로 가리키는 자료구조 탐색은 오래 걸리지만(O(n)), 삽입/삭제가 용이(O(1))

연결리스트(Linked List) Abstract 불연속적인 메모리 위에 저장되는 선형 데이터 구조(배열은 메모리 공간이 연속적) 포인터를 사용해서 연결. 각 node는 데이터 필드 와 다음 노드에 대한 참조 를 포함하는 노드 로 구성 Linked List를 사용하는 이유 배열도 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있찌만 제한사항이 존재 크기만큼 정적으로 메모리 공간을 연속적으로 할당 연속적으로 할당하기때문에, 사용하지 않는 공간이 있더라고 그 공간을 다른 용도로 쓰지 못함 =>메모리 낭비가 클 수 있음 배열의 크기는 고정되어 있기 때문에 미리 그 수를 할당받아야함(정적) 크기를 초과할시 새로운 요소를 삽입하는 비용이 많이듦 -> 공간을 만들고, 기존 요소를 전부 이동 장점 동적 크기 삽입..