자료구조
-
[ 비선형 자료구조 ] 맵(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..
-
[ 비선형 자료구조 ] 트리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..
-
[ 선형 자료구조 ] 스택(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) 단점 최대 할당 크기가 제한된다...
-
[ 선형 자료구조 ] VectorComputer Science/자료 구조 2023. 1. 9. 11:50
1. Vector 1) 개념 컴퓨터 과학에서 벡터는 배열과 유사하되 동적으로 크기를 조정할 수 있는 자료구조이며, 배열처럼 연속된 메모리 를 바탕으로 구성된다. 백터는 데이터를 연속되게 쌓으며 삭제/삽입 등의 연산시 대상 인덱스 이후의 요소들의 위치를 조정한다. 2) 장점 쉽게 크기 조정이 가능하다. idx를 통해 빠르게 각 요소에 접근가능하며 O(n)의 시간 복잡도를 갖는다. 끝 요소의 경우 삽입/삭제 연산이 빠르다. O(n)의 시간복잡도를 갖는다. 요소 저장을 위한 메모리만 사용하기 때문에 배열보다 메모리 측면에서 효율적이다. 3) 단점 요소들의 위치 조정이 필요하기 때문에 끝 이외의 부분에서의 삽입/삽제 연산은 배열보다 느리다. 각 요소의 크기, 저장된 요소의 개수 등의 정보를 포함하기 때문에 배열..
-
[ 자료구조 ] linked list의 삽입/삭제는 정말 array list보다 빠른가?문득 든 의문점 2023. 1. 5. 22:19
의문점 연결 리스트의 경우 삽입/삭제 자체는 O(1)의 시간 복잡도를 가지지만, 대상이 되는 인덱스 까지 찾아가는 과정을 고려한다면 O(n)의 시간 복잡도가 추가된다고 볼 수 있는데 이를 단순히 O(n + 1)이라 가정한다면 O(n)의 시간 복잡도를 가지는 배열 리스트보다 빠르다고 할 수 없지 않는가? 결론 배열 리스트의 경우 특정 인덱스에 요소를 삽입 / 삭제할 경우 해당 인덱스 이후 모든 요소의 위치를 이동시켜야 한다. 따라서 일정하게 O(n)의 시간 복잡도를 갖는다. 하지만 연결 리스트의 경우 head 부분에 가까워질수록 시간복잡도는 O(1)에 가까워진다. 즉, 삽입/삭제의 대상이 될 인덱스의 위치에 따라 O(1) ~ O(n)의 시간 복잡도를 갖는다. 결론적으로 연결리스트는 배열 리스트보다 빠르거나..
-
[ 선형 자료구조 ] 연결 리스트 - Circular Linked List(원형 연결 리스트)Computer Science/자료 구조 2023. 1. 4. 17:27
연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 link filed를 사용함으로써 데이터의 추가 및 삭제를 모든 리스트 인덱스에 대한 방문 및 재구성 없이 실행 가능하다. 연결 리스트는 스택, 큐, 그래프 등을 구현하는데 자주 사용되며, 그 종류로는 Singly linked list, Doubly linked list 등이 있다. 1. 기본 배경 지식 1) Node 연결 리스트를 구성하는 노드는 Data filed, Linke filed 두 가지 필드로 이루어진 묶음이다. Data filed는 node는 integer, character 등 노드가 보유할 실제 데이터..
-
[ 선형 자료구조 ] 연결 리스트 - Doubly Linked List(이중 연결 리스트)Computer Science/자료 구조 2023. 1. 3. 16:47
연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 link filed를 사용함으로써 데이터의 추가 및 삭제를 모든 리스트 인덱스에 대한 방문 및 재구성 없이 실행 가능하다. 연결 리스트는 스택, 큐, 그래프 등을 구현하는데 자주 사용되며, 그 종류로는 Singly linked list, Doubly linked list 등이 있다. 1. 기본 배경 지식 1) Node 연결 리스트를 구성하는 노드는 Data filed, Linke filed 두 가지 필드로 이루어진 묶음이다. Data filed는 node는 integer, character 등 노드가 보유할 실제 데이터..