CS study/[core] 데이터 구조 (14) 썸네일형 리스트형 7. Tree Tree 정의: Direct Acyclic Graph 노드로 구성된 자료구조 Term level( =degree): leaf nodes( =internal nodes): 자식이 없는 노드 height(=depth): 루트 노드에서 가장 깊숙히 있는 노드의 깊이 root: 첫 번째 노드 sibling: 같은 부모를 가지는 노드 List representation: (A (B (E (K, L), F), C (G), D (H (M), I, J) ) ) Binary Tree 각 노드에 왼쪽 child and/or 오른쪽 child가 있는 트리 (정확히 두 자녀는 중간 아이가 아닌 왼쪽 아이와 오른쪽 아이를 의미하기 때문에) 즉 얘들도 binary tree 이다. Full Binary Tree : depth가 $.. 6. Queue Queue 뒤에서 대기열에 추가하고 앞에서 대기열에서 제거가 발생하는 자료구조입니다. FIFO (First-in-First Out) 목록이라고도합니다. 추가는 대기열의 뒤쪽에만 할 수 있으며 제거는 앞쪽에서만 할 수 있습니다. Array implementation of a queue 큐에 항목을 저장하기 위해 q[] 배열을 사용합니다. enqueue(): q[tail]에 새로운 항목을 추가합니다. dequeue(): q[head]에 있는 항목을 제거합니다. Update head and tail modulo the capacity. Add resizing array. 큐의 문제점 배열의 특성상 큐의 용량(Capacity) 이미 정해져 있으므로, 배열로 구현한 큐의 삽입(Enqueue)과 삭제(Dequeue.. 5. Stack Stack 입출구가 동일하여 가장 나중에 들어온 데이터가 가장 빨리 나가는 자료구조입니다. LIFO(Last-in-First-Out) 목록이라고도 합니다. 구현 (배열) N개의 항목을 스택에 저장하기 위해 배열 s[ ]을 사용합니다. push(): s[N]에 새로운 항목을 추가합니다. pop(): remove item from s[N-1]에 있던 항목을 제거 합니다. Defect. capacity이상으로 항목의 개수가 들어오면 스택 오버플로우가 일어납니다. => resize로 해결 기능 Stack CreateStack (maxStackSize) bool IsFull (Stack stack) bool IsEmpty (Stack stack) void Push (Stack stack, item) void Po.. 4. Linked List Linked List Singled Linked List 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다. Example) 단어 정렬 단어들이 임의의 순서로 주어졌을 때 단일 연결 리스트를 사용하여 알파벳 순으로 단어를 배열하고 싶습니다. 단어 목록은 다음과 같습니다. HAT, CAT, EAT, WAT, BAT, FAT, VAT 알파벳순 정렬을 할 때 Link의 숫자는 다음 data의 숫자입니다. data[4] = bat; link[4] = 1; data[link[4]] = data[1] = cat; link[1] = 2; ... 위와 같이 단일 연결 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입.. 3. Recursion Recusion 재귀: 자기 자신을 호출하는 함수 자신의 복사본을 호출하여 더 작은 문제를 풀게함으로써 문제를 해결합니다. 이를 재귀 단계라고 하는데, 재귀 단계는 더 많은 수의 재귀 단계를 만들 수 있습니다. 매 단계보다 함수는 원본 문제보다 조금 더 단순한 문제를 가지고 자기 자신을 호출합니다. 재귀를 사용하여 문제를 해결할 때 아이디어는 큰 문제를 더 작고 유사한 문제로 만듭니다. 결국이 프로세스가 반복되고 문제의 크기가 각 단계에서 감소하면 매우 작고 해결하기 쉬운 문제에 도달합니다. void recursiveFunction (int num) { printf("%d\n", num); if (num < 4) recursiveFunction(num+1); } n = 0 일때 결과 구성 base cas.. 1. 기초수학 1. logarithms $ X = a^b, \ \ b = log_aX \\$ $ log \ ab = log \ a + log \ b \\$ $ log \ \frac a b = log \ a - log \ b \\$ $ log \ a^b = b \ log \ a \\$ $ log_an = \frac {log_bn} {log_ba} = \frac {log \ n} {log \ a} \\ $ $ log_aa = 1, for \ all \ a > 0 \\ $ $ log_a1 = 0, for \ all \ a > 0 \\$ 2.summation 2-1. Arithmatic sum $ \sum_{i=1}^n i = 1 + 2 + 3 ... + i \\ $ $ \sum_{i=1}^n i = \frac {n(n+1).. 이전 1 2 다음