Computer Science/자료 구조
-
[ 선형 자료구조 ] VectorComputer Science/자료 구조 2023. 1. 9. 11:50
1. Vector 1) 개념 컴퓨터 과학에서 벡터는 배열과 유사하되 동적으로 크기를 조정할 수 있는 자료구조이며, 배열처럼 연속된 메모리 를 바탕으로 구성된다. 백터는 데이터를 연속되게 쌓으며 삭제/삽입 등의 연산시 대상 인덱스 이후의 요소들의 위치를 조정한다. 2) 장점 쉽게 크기 조정이 가능하다. idx를 통해 빠르게 각 요소에 접근가능하며 O(n)의 시간 복잡도를 갖는다. 끝 요소의 경우 삽입/삭제 연산이 빠르다. O(n)의 시간복잡도를 갖는다. 요소 저장을 위한 메모리만 사용하기 때문에 배열보다 메모리 측면에서 효율적이다. 3) 단점 요소들의 위치 조정이 필요하기 때문에 끝 이외의 부분에서의 삽입/삽제 연산은 배열보다 느리다. 각 요소의 크기, 저장된 요소의 개수 등의 정보를 포함하기 때문에 배열..
-
[ 선형 자료구조 ] 배열 & 리스트Computer Science/자료 구조 2023. 1. 6. 16:01
1. 배열 1) 개념 배열은 연관된 데이터를 그룹핑해 관리하는 방식의 자료구조이다. 연속적인 메모리 블록에 데이터를 저장하며, 각 항목을 요소(element)라 한다. 배열은 생성될 때 크기가 고정되며, 해당 위치를 결정하는 인덱스를 가진다. 2) 배열의 특징 (1) 장점 각 항목이 고정적인 인덱스를 가지며, 이를 통해서 각 항목의 요소로의 접근이 O(1)의 빠른 시간복잡도를 가진다. 따라서 잦은 접근이 필요한 데이터를 저장하기에 알맞다. 배열의 경우 데이터의 크기가 고정적이고 잦은 접근이 필요한 경우, 혹은 인덱스가 중요한 경우 이점을 가진다. (1) 단점 생성과 함께 사이즈가 고정되기 때문에 요소의 추가/삭제가 자유롭지 못하다. 항목의 데이터를 삭제해도 인덱스 값은 고정되며 메모리상에서 지속적으로 자..
-
[ 선형 자료구조 ] 연결 리스트 - 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 등 노드가 보유할 실제 데이터..
-
[ 선형 자료구조 ] 연결 리스트 - Singly linked list(단순 연결 리스트)Computer Science/자료 구조 2022. 12. 28. 19:17
연결 리스트는 각각의 요소들이 "노드"에 저장되는 선형 자료 구조이다. 각 노드들은 다음 노드에 대한 참조값을 가지며 이를 "링크"라 한다. 이러한 노드들로 이루어진 연결 리스트는 노드의 link filed를 사용함으로써 데이터의 추가 및 삭제를 모든 리스트 인덱스에 대한 방문 및 재구성 없이 실행 가능하다. 연결 리스트는 스택, 큐, 그래프 등을 구현하는데 자주 사용되며, 그 종류로는 Singly linked list, Doubly linked list 등이 있다. 1. 기본 배경 지식 1) Node 연결 리스트를 구성하는 노드는 Data filed, Linke filed 두 가지 필드로 이루어진 묶음이다. Data filed는 node는 integer, character 등 노드가 보유할 실제 데이터..
-
[ 복잡도 ] 정렬 알고리즘의 복잡도Computer Science/자료 구조 2022. 12. 26. 21:43
정렬 알고리즘에 따른 복잡도 Algorithms space complexity time complexity 최악 최선 평균 최악 bubble O(1) O(n) O(n^2) O(n^2) heap O(1) O(n log n) O(n log n) O(log n) insertion O(1) O(n n) O(n^2) O(n^2) merge O(n) O(n log n) O(n log n) O(log n) quick O(log n) O(n log n) O(n log n) O(n^2) selection O(1) O(n^2) O(n^2) O(n^2) shell O(1) O(n) O(n^1.25) O(n^1.25) smooth O(1) O(n) O(n log n) O(n log n) 자료 구조 별 시간 복잡도 Big-O ..
-
[ 복잡도 ] 시간 복잡도와 공간 복잡도Computer Science/자료 구조 2022. 12. 26. 19:36
컴퓨터 과학에서 "복잡도"란, 문제를 풀거나 알고리즘을 푸는데 필요한 리소스를 나타낸다. 이러한 복잡도는 문제를 푸는데 걸리는 시간을 나타내는 "시간 복잡도"와 문제를 해결하는데 필요한 메모리/스토리지 양을 나타내는 "공간 복잡도" 이 두가지를 포함하여 다양한 측면에서 평가될 수 있다. 1. 시간 복잡도 시간 복잡도는 문제를 풀거나 알고리즘을 실행할 때 필요한 시간의 양을 나타내며, 일반적으로 입력 크기에 따라 측정된다. 이러한 시간 복잡도를 표기하기 위해 Big-O(상한 점근), Big-Ω(하한 점근), Big-θ(평균) 등의 표기법이 있는데, 주로 사용되는 것은 최악의 경우까지 고려할 수 있는 Big-O 표기법이다. big O notation : 빅-오 표기법에서는 복잡도는 입력 (n)에 따라 평가되..