Live Today

📋 목차 Trie 자료구조란? Trie 장/단점 Trie 코드 구현 Trie 관련 알고리즘 문제 1️⃣ Trie 자료구조란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이다. 우리가 원하는 원소를 찾는 작업을 O(n)에 해결 할 수 있는 자료구조이다. 여기서 n은 문자열의 길이입니다. 루트 노드가 되는 가장 최상위 노드에는 어떠한 단어도 들어가지 않고, 루트 아래 노드부터 문자열들의 접두사가 하나씩 나타나게 된다. 💡우리가 사전에서 단어를 찾을 때와 비슷한 메커니즘입니다. 한 글자씩 찾아가며 문자열에 도달합니다. 2️⃣ Trie 장단점 트라이(Trie)는 문자열 검색을 빠르게 한다. 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 ..

📋 목차 B-Tree란? B-Tree 특징 B+ Tree란? B+ Tree 특징 B-Tree와 B+ Tree 비교 B-Tree 이용 사례 1️⃣ B-Tree란? 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 자료구조의 일종 → 탐색 성능을 높이기 위해 균형있게 높이를 유지하는 균형 트리입니다. → (단, B-Tree는 ‘이진 트리’가 아님 !) 2️⃣ B-Tree 특징 노드의 데이터 수가 N이면, 자식 수는 N+1 각 노드의 데이터는 정렬된 상태이어야 함 루트 노드는 적어도 2개 이상의 자식을 가져야 함 루트 노드를 제외한 모든 노드는 적어도 M/2개의 데이터를 가지고 있어..

📋 목차 Binary Search Tree(이진 탐색 트리)란? Binary Search Tree(이진 탐색 트리)의 4가지 조건 Binary Search Tree(이진 탐색 트리) 연산 탐색 연산 삽입 연산 삭제 연산 Binary Search Tree(이진 탐색 트리) 성능 1️⃣ Binary Search Tree(이진 탐색 트리)란? 이진탐색트리(BST: Binary Search Tree)는 이진트리 기반의 탐색을 위한 자료구조이다. 이진탐색의 효율적인 탐색 능력을 가지며, 삽입과 삭제가 가능한 것이 특징이다. 위의 이진 탐색 트리에서, 15의 값을 가진 노드의 왼쪽 서브트리에 있는 값들(5,7,10)은 루트 노드인 15보다 모두 작고, 오른쪽 서브트리에 있는 값들(16, 18, 19, 20)은 모두..

📍Array(배열) 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 자료구조. index와 값의 쌍으로 구성 index는 값에 대한 유일무이한 식별자(마치 주민번호)( 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가짐) 논리적 저장 순서와 물리적 저장 순서가 일치 => index로 해당 원소에 접근할 수 있다. (O(1)) 연속된 메모리의 공간으로 이루어져 있다. 배열은 선언과 동시에 크기를 지정하며 배열의 크기를 바꿀 수 없다. 장점 인덱스를 통한 검색이 용이함. 연속적이므로 메모리 관리가 편하다. 단점 크기가 고정되어 있기 때문에 어떤 엘리먼트가 삭제되면, 삭제된 상태를 빈 공간으로 남으므로 삽입/삭제 연산에 불리함. 정적이므로 배열의 크기를 컴파일 이전에 정해주어야 한다. 컴파일 이..

자료구조란? 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다. 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조(집합) 자료구조를 배우는 이유 ✔️ 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 자료구조를 사용한다. ✔️ 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다. 많은 자료구조를 알아두면, 특정 문제를 해결하는 데에 상황에 가장 적합한 자료구조를 빠르게 찾아 데이터를 정리하고 활용하여문제를 빠르고 정확하게 해결할 수 있다. 이것은 문제 해결 능력을 필요로하는 알고리즘과 굉장히 밀접한 연관성이 있다. 결국 문제해결을 하기 위해서 배운다. 💡 자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주..