CS/Data Structure

1. 트리(Tree)란? - 이전에 다뤄왔던 것들과는 다르게 "비선형" 구조인 계층 구졸르 가진 자료구조입니다. - 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타날 때 사용됩니다. 2. 용어정리(트리) - 루트(Root) : 가장 상위에 있는 노드를 뜻합니다. - 노드(Node) ; 트리 안에 들어있는 각 항목을 말합니다. - 리프(Leaf) : 자식이 없는 가장 끝에 있는 노드를 의미합니다. 3. 트리의 특징 left = index * 2 right = index * 2 + 1 parent = floor(index / 2) 4. 트리의 종류 - 이진트리 정점이 최대 2개의 자식을 가지는 트리를 의미한다. - 완전 이진트리 리프 노드를 제외하고 모든 정점이 채워져있다. - 포화 이진트리 완전 ..

2021. 8. 10.

CS/Data Structure

1. Heap 우선순위가 높은 요소가 먼저 나가는 특징을 가진다. 루트가 가장 큰 값이 되는 최대 힙과 루트가 가장 작은 값이 되는 최소 힙이 있다. 2. 힙 추가 요소가 추가 될 때는 트리의 가장 마지막 정점에 위치한다. 추가 후 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다. 완전 이진 트리의 높이는 log n 이기에 힙의 요소 추가 알고리즘은 O(log n) 시간복잡도를 가진다. class maxHeap { constructor() { this.heap = [null]; } push(value) { // 힙에 가장 끝에 추가 this.heap.push(value); let currentIdx = this.heap.length - 1; let parentIdx = Math.floor(cu..

2021. 8. 10.

CS/Data Structure

배열 ( Array ) 배열은 연속된 메모리에 저장이 되고, 사이즈 변경이 불가능합니다. 단, 자바스크립트에서는 사이즈가 동적으로 변합니다. 자바스크립트의 배열은 해시 테이블로 구현된 객체이므로 인덱스로 접근하는 경우에는 일반 배열보다 속도가 느리지만, 삽입 & 삭제의 경우에는 보다 빠른 성능을 기대 할 수 있다. ( ArrayBuffer를 쓰면 실제 배열과 비슷하게 동작이 가능 ) 연속된 메모리 구조 덕분에, 삽입과 삭제 작업은 선형 시간인 O(n) 만큼 소요 됩니다. 삽입의 경우, 새로운 값 이후의 인덱스들을 모두 뒤로 밀어야 하고, 삭제의 경우, 빈 인덱스로 이후의 값들을 당겨 와야 합니다. 삽입, 삭제는 느리지만 탐색의 경우 인덱스를 통해 O(1) 만에 접근 할 수 있습니다. 하지만, 정렬 되지 ..

2021. 8. 5.

CS/Data Structure

1. 연결 리스트의 특징 메모리가 허용하는한 요소를 제한없이 추가 할 수 있습니다. 배열과 다르게, 메모리가 연속적으로 저장 되어 있지 않기 때문이다. 탐색은 O(n)이 소요됩니다. 인덱스가 존재 하지 않기 때문에, 찾는 대상을 만날 때까지 순회를 해야합니다. 요소를 추가하거나 제거 할 때는 O(1)이 소요됩니다. 단, 요소의 추가와 삭제를 위해서는 장소의 탐색이 발생하기에 이 작업을 최소화 하는 것이 중요합니다. 링크드 리스트의 유형으로는 [Single, Double, Circular] 총 3가지가 존재합니다. 2. 배열과의 차이점 1. 배열과 연결 리스트의 가장 큰 차이점은 메모리에서 발생합니다. 2. 연결 리스트는 산발적, 배열은 연속적으로 이루어져있습니다. ( => 배열은 연속적인 메모리 구조를 ..

2021. 8. 5.

CS/Data Structure

연결 리스트란 ? 연결리스트는 선형 자료구조로써, 연속적으로 메모리에 존재 하지 않고, 포인터를 통해서 다음 인덱스를 나타냅니다. 연결 리스트의 특징 탐색 및 수정 Linked List는 인덱스가 없어, 처음부터 탐색을 시작 하기 때문에 O(k) 이다. ( = k는 탐색 하는 대상의 위치 ) 예시로 [ 철수, 영희, 민수, 동현 ] 으로 구성된 Linked List에서 동현을 찾는다고 가정해보자. 배열의 경우는 인덱스의 값을 통해 빠르게 접근이 가능하지만, Linked List는 철수 -> 영희 -> 민수 -> 동현을 거쳐야 알 수 있다. 삽입 및 삭제 Linked List의 삽입 삭제는 이전의 next를 제거하고, 이어주는 기능만을 수행하면 되기에 O(1) 이다. 연결 리스트 구현 Node 구현 연결리..

2021. 7. 13.