Computer Science/자료 구조
-
[ 비선형 자료구조 ] 해시 테이블(Hash Table)Computer Science/자료 구조 2023. 3. 9. 18:07
1. 해시 테이블 해시 테이블은 key-value 쌍으로 데이터를 저장하는 자료구조입니다. 해시 테이블은 내부적 배열을 이용하며, 각 key에 해시 함수를 적용해 얻은 인덱스에 value를 저장합니다. 이때 value가 저장되는 장소를 슬롯이라 하며, 이러한 특성을 바탕으로 데이터 검색에서 빠른 퍼포먼스를 보여줍니다. 즉, 해시 테이블에서 각 key는 대응되는 인덱스를 가지며 O(1)의 시간 복잡도를 보여줍니다.(해시 테이블에 데이터가 찰수록 충돌 발생 가능성이 높아지고 가용 가능한 슬롯의 검색에 대한 비용이 추가되어 O(N) 까지 증가할 수 있습니다.) 해시 함수는 문자열 혹은 다른 데이터 타입의 인풋 인자를 받아 인풋 인자에 대응하는 고유하고, 고정된 사이즈의 아웃풋(일반적으로 수 혹은 문자열)을 출..
-
[ 비선형 자료구조 ] 맵(Map) & 셋(Set)Computer Science/자료 구조 2023. 3. 7. 17:47
1. 맵(Map) 1) 특징 map은 key - value 쌍으로 이루어진 자료구조이며, key의 중복을 허용하지 않는 자료구조입니다.(value의 중복은 허용합니다.) 이러한 map의 특징은 각 key에 대응하는 value에 효율적으로 접근 가능하게 해 주며 O(n)의 복잡도를 가집니다. key-value쌍을 메모리에 저장 순서를 고려하지 않는다. key에는 다양한 데이터타입이 올 수 있다.(언어에 따라 약간의 차이를 가진다 ex. python - strings, numbers, tuples, javascript - any data type including objects and functions) key의 중복을 허용하지 않는다. 데이터에 효율적으로 접근 가능하다. 2) 종류 HashMap : 순서를..
-
[ 비선형 자료구조 ] heapify & heap sortComputer Science/자료 구조 2023. 3. 5. 02:06
heapify와 heap sort 힙은 모든 부모 노드가 자식 노드 이상(max-heap) 혹은 이하(min-heap)의 값을 가지는 완전이진트리이며, 주어진 배열이나 리스트를 힙 구조로 만드는 연산이 heapify입니다. heap sort는 정렬되지 않은 배열이나 리스트를 heapify 프로세스를 이용해 heap 자료구조로 변환한 뒤 root 노드의 값을 추출해 배열 혹은 리스트에 추가하는 과정을 모든 요소가 정렬될때까지 반복하는 알고리즘 입니다. heapify : 배열이나 리스트를 힙 구조로 재구성하는 연산 heap sort : 힙에서 root값을 반복적으로 추출해 정렬된 배열을 만드는 알고리즘 heapify heapify는 배열을 인자로 받아 힙의 특성에 맞게 재구성시키는 연산입니다. 이러한 hea..
-
[ 비선형 자료구조 ] 우선순위 큐(Priority Queue) & 힙(Heap)Computer Science/자료 구조 2023. 1. 20. 15:46
1. 우선순위 큐(priority queue) 1) 개념 FIFO 규칙을 따르는 일반적인 큐와는 다르게, 데이터간 우선순위를 할당하고 우선순위에 따른 보다 효율적인 삽입, 삭제등의 연산을 구현한 추상 자료구조를 우선순위 큐라한다. 따라서, 우선순위 큐에선 높은 우선순위를 지닌 요소가 비교적 낮은 요소보다 앞서 디큐, 접근된다. 2) 특징 우선순위 큐는 배열 운영 체제, 네트워크 라우팅 알고리즘, 데이터 압축 알고리즘 등에서 널리 사용되, 연결리스트 등을 이용해 구현 가능하지만 삽입, 삭제 연산의 시간복잡도 측면에서 힙을 사용하는 것이 효율적이기 때문에 일반적으로 힙을 사용해 구현한다. (배열이나 연결 리스트를 사용할 경우 우선순위가 중간쯤 위치한 데이터의 삽입 시 배열의 경우 대상 인덱스 이후의 모든 데..
-
[ 비선형 자료구조 ] 트리 순회Computer Science/자료 구조 2023. 1. 19. 17:36
1. pre-order traversal (전위 순회) [root - 왼쪽 자식 노드 - 오른쪽 자식 노드] 순으로 순회하는 방식이다. 이 방식에 따르면 A-B-D-E-C-F-G 순으로 트리를 순회하며, 자바스크립트로 구현한 코드는 아래와 같다. fucntion preOrder(root) { if (!root) return; console.log(root.data); preOrder(root.left); preOrder(root.right); } 2. in-order traversal (중위 순회) [왼쪽 자식 노드 - root - 오른쪽 자식 노드] 순으로 순회하는 방식이다. 이 방식에 따르면 D-B-E-A-F-C-G 순으로 트리를 순회하며, 자바스크립트로 구현한 코드는 아래와 같다. fucntion ..
-
[ 비선형 자료구조 ] 트리Computer Science/자료 구조 2023. 1. 18. 07:23
트리 1. 개념 트리는 그래프의 한 종류로서 각 노드가 특정 값을 저장하고 하나 이상의 자식 노드에 대한 참조값을 가지고 있는 자료구조이다. 트리를 구성하는 노드들은 계층구조로 이루어져있으며 최상위 노드를 root라 한다. 트리는 일반적으로 파일 시스템, 데이터 베이스, 의사결정 알고리즘 등에서 사용된다. 2. 용어 root : 부모 노드가 존재하지 않는 노드, 최상위 노드 (A) node : 데이터와 다음 노드에 대한 주소값을 저장한 자료구조 leaf : 자식노드가 존재하지 않는 노드, 최하위 노드 (H, I, E, J, K, L) parent : 하나 이상의 자식 노드를 가진 노드 (A, B, C, D, F, G) child : 다른 노드의 자손인 노드 (B, C, D, E, F, G, H, I, J..
-
[ 비선형 자료구조] 그래프Computer Science/자료 구조 2023. 1. 11. 07:15
그래프 1) 개념 그래프는 정점(vertex)와 간선(edge)으로 이루어진 대상 간의 관계를 표현하는 자료구조이다. 2) 용어 정리 정점(vertex) / 노드 : 데이터가 저장되는 공간 간선(edge) / link / branch : 정점을 연결하는 선 인접 정점(adjacent vertex) : 직접 연결된 정점 단순 경로(simple path) : 방복되는 정점/간선 없이 이루어진 경로 차수(degree) : 무방향 그래프에서 하나의 정점에 연결된 정점의 수 진출 차수(out-degree) : 방향 그래프에서 정점을 기준으로 나가는 간선의 수 진입 차수(in-degree) : 방향 그래프에서 정점을 기준으로 들어오는 간선의 수 경로 길이(path length) : 경로를 구성하는 간선의 수 cyc..
-
[ 선형 자료구조 ] 스택(Stack) & 큐(Queue)Computer Science/자료 구조 2023. 1. 9. 13:55
1. Stack 1) 개념 스택은 LIFO(last-in-first-out), 즉, 후입선출 원칙을 따르는 선형 자료구조이다. 따라서 데이터의 출입은 한 방향에서만 이루어지고, 이름에 걸맞게 쌓아가는 구조를 가진다. 데이터에 대한 접근은 가장 위층에 대해서 가능하며, 삽입(push) / 삭제(pop) 연산 또한 가장 위층의 데이터에 대해서 가능하다. 스택에서 사용되는 주요 연산은 앞서 소개한 push, pop과 더불어 가장 위층의 데이터를 삭제하지 않고 반환하는 peek, 스택이 비었는지 여부를 반환하는 isEmpty 등이 있다. 2) 장점 구조 자체가 간단하고 직관적이며, 구현이 쉽다. 가장 마지막 데이터에대한 접근만 가능하므로 데이터에 대한 접근이 매우 빠르다. 3) 단점 최대 할당 크기가 제한된다...