기록을 합쉬다

5.1 복잡도: 시간복잡도, 공간복잡도 시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계. 보통 빅오표기법으로 나타냄. ※ 빅오표기법: 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것. -> 효율적인 코드로 개선하는 데 쓰이는 척도 공간복잡도: 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 자료구조에서의 시간 복잡도 - 평균 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 O(1) O(n) O(n) O(n) 스택 O(n) O(n) O(1) O(1) 큐 O(n) O(n) O(1) O(1) 이중 연결 리스트 O(n) O(n) O(1) O(1) 해시 테이블 O(1) O(1) O(1) O(1) 이진 탐색 트리 O(log n) O(log n) O(log n) O(log n) A..

Stack & Queue (Using an Array) Stack definition LIFO(Last-In-First-Out) 구조 나중에 들어간 데이터가 먼저 나오는 구조의 리스트 자료구조 Implementation 배열을 이용하는 방법(global or local) non-circular buffer circular buffer 연결 리스트를 이용하는 방법 Using an Array: non-cicular buffer 1차원 배열 (datatype) stack[stack_size] ex) char stack[100] variable: top - 0으로 초기화(empty stack) 삽입할 때마다 top++ int main(void) { int stack[5]; int top = 0; // inser..

Graph Definition Node(Vertex) Edge undirected edge(무방향 간선) 무방향 그래프 directed edge(방향 간선) 방향 그래프 weighted edge 가중치 그래프(방향/무방향 그래프) Subgraph 그래프의 부분이면서 그 자체로 그래프인 것 Connected Graph 한 노드에서 출발했을 때 모든 노드를 방문할 수 있는 그래프 Disconnected Graph 한 노드에서 출발했을 때 모든 노드를 방문할 수 없는 그래프 Adjacent Nodes edge로 서로 연결되어있는 인접한 두 개의 노드 Complete(Connected) Graph 모든 노드가 다른 노드의 인접한 노드인 그래프 Graph Algorithms Graph representation ..

Tree 그래프의 일종 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프 루트(root) 노드: 최상위 노드가 리프(leaf) 노드: 자식 노드가 없는 노드 내부(interior) 노드: 루트 노드도, 리프 노드도 아닌 노드 상위 노드와 하위 노드를 각각 부모(parent) 노드와 자식(child) 노드라고 함 같은 부모 노드를 둔 자식 노드들끼리를 형제(sibling) 노드라고 함 Types of Tree Data Structures Binary Tree Binary Search Tree, Heap, Trie Red-Black Tree Height-Balanced Binary Tree AVL Tree, T-Tree n-Way Tree m-Way Trie 2-3 Tree Height-Balanced m-W..

Red-Black Tree 탐색, 삽입, 삭제 성능: O(log2n) 탐색, 삽입, 삭제에 binary search tree 알고리즘 사용 각 노드는 색상이 할당됨 Properties(Rules) 각 노드는 red 노드거나 black 노드다 루트 노드는 black 노드다 모든 leaf 노드는 black 노드다(NIL 포함) 모든 red 노드는 반드시 2개의 black 노드를 자식으로 갖는다 주어진 어떤 노드에서든 자식 노드까지 모든 경로에서 같은 수의 black 노드를 갖는다 Insertion 새로운 노드는 red 노드 상태로 binary search tree 삽입 uncle 노드를 확인해서 밸런스를 맞춘다 삽입에는 5가지 경우가 있을 수 있다 (N: 삽입하는 노드(red) P: N의 부모 노드, G: ..

Static Hashing Definition 배열 안에 key를 저장하고 탐색하는 기법 - hash table key를 배열의 index로 mapping 이를 bucket이라고 함 평균 성능: O(1) 탐색, 삽입, 삭제 index bucket 0 Korea 1 Japan 2 Qatar 3 Vietnam 4 China 5 Taiwan 6 Singapore 7 France Insert Thailand & Spain index bucket 0 Korea 1 Japan 2 Qatar 3 Vietnam 4 China 5 Taiwan Thailand 6 Singapore Spain 7 France -> index 5, 6에서 collision 발생 Insert SriLanka index bucket 0 Kore..

Definition 리스트의 요소들을 특정 순서로 배열하는 것 Sorting Algorithms - 1 Internal Sorting 리스트가 메인 메모리 안에서 정렬되는 것 정렬 속도는 빠르지만, 데이터의 양이 제한적 External Sorting 부가적인 공간에서 리스트가 정렬되는 것 정렬 속도는 느리지만, 보조 공간을 이용하여 큰 데이터도 정렬할 수 있음 Insertion sort 새로운 key를 삽입하기 위해서 리스트에서 맞는 위치를 찾고 그 위치에 삽입 성능 O(n2) n = 키의 개수 짧은 리스트에서 간단하고 좋음 부분적으로 이미 정렬된 리스트일 때 좋음 Example // GeeksforGeeks void insertionSort(int arr[], int n) { int i, key, j;..