자료구조

가상머신, 언어, 코드, 알고리즘/자료구조 복잡도, Big-O 기호Stack, Queue, Dequeue한 방향, 양 방향해시 함수, 해시 충돌 해결 방법Priority Queue : Heap + HeapSort이진 트리 : 순회이진 탐색 트리 : 삽입, 삭제 등균형

자료 : data -> 저장공간(memory) + 각종 연산들(읽기,쓰기,삽입,삭제,탐색) : 구조data를 입력하여 유한한 횟수의 연산들 -> 알고리즘을 통한 정답 출력자료구조의 예) 변수 a=5, 배열(array), 리스트 등A = 1,2,3,4 A.append('

똑같은 알고리즘이라도 HW/SW 환경이 상이하여 속도가 다르다. 또한 다양한 크기를 입력하기에 내가 만든 알고리즘이 얼마나 빠르게 작동하는지 알 필요가 있다.우선 독립적인 가상 컴퓨터를 설정 : virtual machine이 가상의 컴퓨터에서 가상언어(Pseudo la

알고리즘의 수행시간 = 최악의 경우의 입력에 대한 기본 연산의 횟수n이 증가함에 따라 증가률을 표시하기 위해 최고차항만을 가지고 간단하게 표기하자!ex) T1(n) = 2n-1 = O(n), T2(n) = 4n-1 = O(n), T3(n) = n^2+1 = O(n^2)

가장 기본적인 순차적인 sequential 자료구조이다.특정 인덱스를 보며 쓰고 읽고 대입하고 산술하는 작업을 할 수 있다.ex) a = 2, 4, 0, 5, a2 = a2 + 1 -> a = 2, 4, 1, 5, a.append(6) -> a = 2, 4, 1, 5,

index로 임의의 원소를 접근\-연산자 \[] a2:-1\-삽입 append, insert\-삭제 pop, remove여기서 단순히 연산, append, pop의 경우는 O(1) 이지만, insert나 remove의 경우 자리를 줄이고 옮기고 해야 하기에 O(n)이

일단 기본적으로 삽입, 삭제, 탐색이 되어야 한다.Stack에서의 삽입은 push, 삭제는 pop이라고 한다.물론 list의 append와 pop과 똑같지만, 다양한 작업을 할 수 있는 list 대신 딱 두 가지만 함으로 다른 실수를 하지 않게 하기 위해 Stack을

"2+3 5" \-> 피연산자 연산자 구별 2 + 3 5\-> 연산자 우선순위 (2+(3\* 5))\-> 계산 17

FIFO : First in First out 들어온 순서대로 나간다.stack에서의 push를 여기서는 enqueue라고 한다.stack에서의 pop은 dequeue라고 한다.front에서 dequeue()가 된다.저장공간은 items라고 부르며, list이다.Jos

Linked list는 순차적 자료구조의 마지막이다.한 방향과 양 방향이 있다.배열 vs 연결 리스트배열은 연속된 공간에 메모리를 차지하고, 인덱스를 통해 값을 수정 및 첨가할 수 있다.이에 반해 연결 리스트는 그것이 아니다. 배열과 대조적으로 연속되어 있지 않고 흩어

이렇게 만들고 head와 size를 잘 적어주면 한 방향 연결리스트 객체를 만든 것이다!push front, push back을 알아볼 것인데, push front는 말 그대로 head node 앞에 새로운 노드를 삽입하는 것이고, push back은 tail node

기존의 한 방향 리스트의 단점은 tail node까지 가기 위해서는 한 번에 찾을 수는 없고, head node부터 차례로 링크를 따라가며 찾아야 했다.이렇게 되면 만약 연결 리스트의 길이가 너무나 길 때, prev node를 계속 따라가며 오랜 시간이 걸리게 되고 비

BST가 무엇인가?모든 노드의 left sub tree들은 해당 노드의 값보다 작은 값들만 가지고,모든 노드의 right sub tree들은 해당 노드의 값보다 큰 값들만 가진다. 그렇다면 예시를 한 번 살펴보자.1)은 12와 10이 맞지 않기에 BST라고 할 수 없다

AVL Tree는 앞 포스터의 Binary Search Tree의 depth가 너무 깊어지는 단점을 보완하고 balance를 맞추기 위해 등장했다.무엇이 balance가 있는 것일까?Balance factor (B) = HL−HRBalanced binary tr

A Heap is a binary tree structure with the following properties:The tree is complete or nearly completeThe key value of each node is greater than or e

Multiway Tree는 BST의 변형이라고 생각하면 된다.Binary Search Tree? 모든 노드의 left sub tree들은 해당 노드의 값보다 작은 값들만 가지고,모든 노드의 right sub tree들은 해당 노드의 값보다 큰 값들만 가진다. Multi

가장 복잡한(일반적인) 자료구조G = (V,E) : (vertex set, edge set)자주 등장하는 용어들Vertex 정점 = nodeedge = linkdegree 분지수 : 이웃한 노드의 개수ex) 4의 분지수 = 3, 1의 분지수 = 2, G의 분지수 = 3