CS study (17) 썸네일형 리스트형 10. Heapsort Heapsort 전략 i. Heapify: N개의 정렬되지 않은 array를 max Heap 구조로 만들기 ii. maximum 키를 순차적으로 pop 내림차순 정렬을 위해서는 최대힙, 오름차순 정렬을 위해서는 최소 힙을 만들면 된다. 동작 i) Heapify Bottom-up method로 최대 힙을 만들자. 이 경우 마지막 Internal node 3-node heap에서 시작한다. 이미 T가 루트인 3-node heap은 heap 구조를 만족하므로 패스 ii. 순차적으로 maximum key를 지운다. 한 번에 하나씩 최대값을 제거합니다. null을 제거하는 대신 배열에 그대로 두십시오. 이런식으로 쭉쭉 하다보면 이렇게 정렬이 된다. // 실행 과정 Enter a word to sort: SORTE.. 9. Heap, Priority Queue Heap 힙은 완전 이진 트리의 일종으로 priority queue를 구현하기 위해 만들어진 자료구조 특징 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 반정렬 상태(느슨한 정렬 상태) 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) Priority Queue 우선 순위가 있는 큐, 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. Ex) 은행에서 줄을 설 때 먼저 온 순서대로(FIFO) 서비스를 받을 수 있습니다. 하지만 노인이나 장애인이 줄을서는 경우 그들에게 우선권을 부.. 8. Binary Search Tree Binary Search Tree 정의: binary tree in symmetric order Binary Tree: 노드로 구성되며, 각 노드는 최대 두 개의 자식(왼쪽과 오른쪽 자식)을 가진다. Symmetric Order 모든 노드는 키를 갖는다. 모든 노드의 키는 왼쪽 하위 트리의 모든 키보다 큼 오른쪽 하위 트리의 모든 키보다 작음 중복된 노드가 없어야 한다. 이 트리에서 키 값이 가장 작은 노드 키 값이 가장 큰 노드 왼쪽 서브트리에서 가장 큰 키 값의 노드 오른쪽 서브트리에서 가장 작은 키 값의 노드 를 구하는 방법을 알아보자. 구조 Node structure Key: Value: Left: Right: BST node structure typedef int Key; typedef char.. 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 2 3 다음