반응형 ＃알고리즘 [Algorithm]/Concept7 [알고리즘] ⏰ 주요 자료구조 시간 복잡도 (Time Complexity) 주요 자료구조에 대한 평균 시간 복잡도는 아래의 도표와 같습니다. 평균 시간 복잡도 (Aveage Time Complexity) 접근 (Access) 탐색 (Search) 삽입 (Insert) 삭제 (Delete) 배열 (Array) O(1) O(n) O(n) O(n) 스택 (Stack) O(n) O(n) O(1) O(1) 큐 (Queue) O(n) O(n) O(1) O(1) 이중 연결 리스트 (Doubly Linked List) O(n) O(n) O(1) O(1) 해시 테이블 (Hash Table) O(1) O(1) O(1) O(1) 이진 탐색 트리 (Binary Search Tree) O (log n) O (log n) O (log n) O (log n) AVL 트리 O (log n) O (log n.. 2024. 3. 5. [알고리즘] 📚 용어 정리 공간 복잡도 (Space Complexity) → 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 뜻합니다. 시간 복잡도 (Time Somplexity) → 입력 크기에 대한 어떠한 알고리즘이 실행되는 데 걸리는 시간을 뜻하며, 주요 로직의 반복 횟수를 중점으로 측정됩니다. 선형 자료 구조 (Linear DataStrucutre) → 요소가 일렬로 나열되어 있는 자료 구조를 뜻합니다. 대표적인 자료구조로는 스택, 큐, 배열, 연결리스트 등이 있습니다. 비선형 자료 구조 (Non-Linear DataStructure) → 요소들을 일렬로 나열하지 않고 자료의 순서나 관계가 복잡한 자료 구조를 뜻합니다. 대표적인 자료구조로는 그래프, 트리 등이 있습니다. 해시 테이블 (Hash Table) 데이터들을.. 2024. 3. 5. [Algorithm - Concept] AVL Tree (named after inventors Adelson-Velsky and Landis) [Algorithm - Concept] AVL Tree (named after inventors Adelson-Velsky and Landis) AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진 탐색 트리이다. 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information" 을 통해 발표했고 그들의 이름을 따서 지어졌다. AVL 트리는 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다. 균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(l.. 2019. 9. 4. [탐색] 깊이 우선 탐색 (DFS, Depth First Search) [탐색] 깊이 우선 탐색 (DFS, Depth First Search) 깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as.. 2019. 8. 29. 이전 1 2 다음 반응형
