데이터를 더 효율적으로 관리하기 위한 자료구조

## ADT(abstract data type, 추상 데이터 타입) - 데이터와 그 데이터에 대한 연산들을 묶어놓은 하나의 논리적 단위로 정의되는 프로그래밍의 추상화 - 데이터와 그 데이터를 다루는 연산들을 분리하여 정의하며, 이로써 어떤 데이터가 어떤 연산을 지원하는지에 대한 논리적 틀을 제공함 #### Stack - **LIFO**: Last-In, First-Out - 한쪽 끝에서만 접근 가능한 자료구조 - 연산 종류 - Push: 스택에 아이템 하나 추가 - Pop: 스택에서 아이템 하나 제거 - IsEmpty: 스택이 비었는지 확인 - 배열 아이템 순서 바꾸는데 용이함 #### Queue - **FIFO**: First-In, First-Out - 연산 종류 - Enqueue: 큐에 아이템 하나 추가 - Dequeue: 큐에서 아이템 하나 제거 - IsEmpty: 큐가 비었는지 확인 - RR scheduling algorithm에 사용됨 #### Linked List ![[linked_list.png|w80|center]] - 다음 데이터가 어디에 저장되어 있는지 주소값(link)을 가지는 자료구조 - 같은 데이터 타입의, 선형적인 자료구조 - 연산 종류 - Insert: 아이템 하나 삽입 - Delete: 아이템 하나 삭제 - IsThere: 아이템이 리스트에 있는지 체크 - GetLength: 리스트의 길이 확인 - Reset, GetNext, MoreItems: 아이템 순회(iteration)에 용이한 메소드 - 연산에서 주의할 점 - Delete - 현재 노드를 가리키고 있는 이전 노드의 포인터를 현재 노드가 가리키고 있는 노드의 주소로 변경 - Insert - 추가하고 싶은 위치를 찾아서 이전 노드의 포인트가 추가하고자 하는 노드를 가리키게 변경하고, 추가하는 노드의 포인터는 이전 노드가 기존에 가리키고 있던 노드를 가리키도록 수정 - 연결리스트와 배열 비교하기 - 가장 크게는 저장하는 방식이 다름 - 배열: 물리적인 저장 공간에 연속적으로 저장됨 (index로 참조하기 위해) - 리스트: 메모리에 연속적으로 저장될 필요가 없음, **하나의 노드에 데이터+링크(포인터)가 함께 저장됨** - 배열은 프로그래밍 언어에 대부분 포함되어 있으나, 리스트는 직접 구현해야 하는 경우가 있음 #### Tree - 복잡한 관계를 표현 가능한 계층이 있는 자료구조 - parent node, child node: 상위 노드와 하위 노드의 관계성 - sibling node: 같은 계층에 있는 노드 - **root** node: 가장 상단에 있는 노드, parent node가 없는 노드 - leaf node: 가장 하단에 있는 노드, child node가 없는 노드 - internal node: root node와 leaf node 사이에 있는 노드 > **Binary Tree** > 각 노드가 2개 이하의 child node를 가지는 트리 ###### ==Binary Search Tree(BST)== - 기존 트리는 unsorted list와 유사해서 검색을 위해서는 모든 트리를 순회해야 하지만, BST처럼 정렬된 상태, 의미 있는 순서로 저장하면 검색이 쉬워짐 ![[binary_search_tree.png|w80|center]] - 어떠한 노드에서든 왼쪽 subtree에 있는 노드들보다는 값이 커야하고, 오른쪽 subtree에 있는 노드들보다는 값이 커야함 - balanced tree인 경우에는 검색에 O(log n)이 걸리지만 최악의 경우(skewed tree) O(n)이 걸림 - n개의 노드가 있을 때, 트리의 높이는 최소 log n #### Graph ✨ ![[data_structure_graph.png]] - G = (V,E) - vertice라 불리는 node의 집합과 edges라 불리는 링크로 구성된 자료구조 - vertice는 객체를 나타내고 edge는 vertice 간의 관계를 나타냄 - edge를 인접 행렬 혹은 연결 리스트로 표현함 - 방향 유무에 따라, 가중치 유무에 따라 그래프 유형을 나눌 수 있음 - 트리는 순회가 없는 그래프라고 볼 수 있음 ###### DFS(Depth-First-Search) - 시작 노드에서 출발하여 최대한 깊게 탐색한 후, 더 이상 진행할 수 없을 때 다시 돌아와 다른 경로로 진행하는 방식 - 스택(Stack) 또는 재귀 함수를 사용하여 구현 가능 - 경로의 존재 여부를 찾거나 모든 해를 찾는 데 유용함 ![[DFS.png|w70|center]] ###### BFS(Breadth-First-Search) - 시작 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한 후, 그 다음 레벨의 노드로 이동하는 방식 - 큐(Queue)를 사용하여 구현 가능 - 최단 경로를 찾거나 어떤 형태의 '최단 거리' 문제에 유용함 ![[BFS.png|w70|center]] ###### SSSP(Single-Source Shortest-Path, Dijkstra Algorithm) - 우선순위 큐(priority queue)를 사용함 - 큐에서 꺼낼 때 우선 순위가 높은 아이템부터 꺼냄 #### Subprograms(function, 함수) ###### Parameter Passing - (formal) parameters : 형식 인자, 함수 선언에 사용되는 인자 - 함수 내에서 사용하는 일시적인 identifier - (actual) arguments : 실제 인자, 함수 호출 시 사용되는 인자