차가운오미자님의 유리병

Heap Tree Structure을 이용하는 정렬 - Complete Binary Tree; 루트 부터 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차근 들어가는, 빽빽한 구조의 트리 - Heap: 최솟값, 최댓값을 최대한 빨리 찾아나기 위해 Binary Tree를 이용함 - 최대힙: 부모 > 자식 - 최소힙: 자식 > 부모 힙 생성 알고리즘(Heapify Algorithm) 예를 들어 부모 노드의 값보다 자식 노드의 값 중에 큰 값이 있다면, 부모 노드와 자식 중 가장 큰 자식 노드를 바꾸는 것 > 이렇게 하위로 갈 수록 규칙이 깨지지 않는지 쭉 탐색하면서 정렬해줘야 함 * 시간 복잡도: O(lg N) = height of Tree * 전체 힙 생성 시간 복잡도: O(1/2N lg N) = ..

Quick Sort 특정한 값을 기준으로 큰 숫자와 작은 숫자를 나눈다. - 기준값(pivot) - 분할 정복 - 왼쪽은 앞에서부터 탐색하며 기준값보다 큰 값을 찾고, 오른쪽은 뒤에서 탐색하여 기준값보다 작은 값을 찾는다. 찾은 후에 그 두 값의 위치를 바꿔준다. - 언제까지? 두 값이 엇갈릴때까지 - 좌측 인덱스(기준값보다 큰 값)값보다 우측 인덱스(기준값보다 작은 값)이 커지면 위치 변경 #include int number = 10; int arr[10] = {3,7,8,1,5,9,6,10,2,4}; void quickSort(int* arr, int start, int end){ if(start >= end){// 원소가 1개인 경우 return; } int key = start; int i = s..

1. 선택 정렬 가장 적은 것을 선택해 제일 앞으로 보낸다 - 가장 쉽고, 가장 단순 #include int main(void){ int i, j, min, index, temp; // i, j 반복 탐색, min 작은 것 int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9} ; for(i=0; i 속도가 빠르다 가정: 선택된 값보다 앞은 모두 정렬이 되어 있다. index보다 앞에 있는 정렬된 배열 중 어느 사이에 들어가야할지를 정하고 거기에 들어가는 것 #include void swap(int* a, int* b){ int temp = *a; *a = *b; *b = temp; } int main(void){ int i, j; int arr[10] = {1, 10, 5, ..

개념 당장 눈 앞에 보이는 최적의 상황을 쫓기. 그래서 '그리디'라고 불리는 것 예시1) 거스름돈 주기 - 가장 큰 화폐 단위부터 거슬러 주기가 최고의 알고리즘 - 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들의 종합으로 다른 해가 나올 수 없다는 게 보장되어야 탐욕법을 사용했을 때 최적의 해가 나오게 됨 - 만약 500, 400, 100원이 있는데 800원을 거슬러줘야 할때 400*2 가 최적의 해이지만 그리디에 따라 큰 단위인 500부터 주면 500*1 + 100*3 이 됨 무조건 큰 경우부터, 작은 경우부터, 긴 경우부터 등 극단적 접근 => sort 기법 자주 사용 예시2) 크루스칼 - 모든 간선 정렬 후 짧은 간선부터 연결하는 최소비용 신장트리 알고리즘 최적의 해를 못찾을 경우, 동적 프로..

Binary Tree Properties (H: height, N = number of nodes) 1. max Height = N 2. min Height 3. max N 4. balance 5. nearly complete: has the min height for its nodes && all nodes in the last level are found on the left 6. complete tree: has max num of entries for its height Binary Tree Traversals 1. depth first traversal: root to most distant descendent 을 먼저 탐색하고 second child 부터 아래로 탐색 1) preorder tr..

Doubly Linked List Doubly Linked LIst 가 일반 Linked List와 다른 것은 각 노드가 next 뿐만 아니라, front 노드 값도 저장하고 있다는 점이다. 따라서 리스트에서 앞 뒤 데이터를 추출하기에 용이하다. 또 하나 다른 점은 LIST 안에 rear 포인터를 두어서 리스트의 마지막 노드도 참조할 수 있도록 했다. 비록 이건 반드시 Doubly Linked List의 특징이라고 할 수 없겠지만, 연습을 위해 추가해보았다. data.h & data.c 매우 간단하다. 심지어 따로 compare 함수를 사용하지도 않았고, key가 int형이라고 고정한 상태로 compare 하는 과정도 dll.c 안에 코드를 짜버렸다. typedef struct myData { int k..

- operations can be done anywhere in the list - Basic operations insertion deletion retrieval traversal 어디에서나 삽입, 삭제, 추출 등이 가능하기 위해서 - insertion: pPre - deletion: pPre. pLoc - retrieval: key 등 포인터를 추가한다. 1. int 데이터 저장하는 리스트 gll.h #include #include #define TRUE 1 #define FALSE 0 typedef int LData; typedef struct node { struct NODE* next; LData data; }NODE; typedef struct gllist { NODE* head; int ..

1. Queue란? - linear list in which data can only be inserted at one end (한 쪽 끝에서만 데이터가 들어가지는 연결 리스트) - has rear and front (rear와 front를 가짐) - ensures that data are processed in the order in which they are received (FIFO) (들어온 순서대로 데이터가 , first in first out) Operations 1) Create Queue 2) Enqueue 3) Dequeue 4) Destroy Queue 2. 구현 이번에는 큐 안에 저장될 데이터를 기본 데이터형으로 하지 않고 바로 구조체로 만들어보았다. student.c & studen..

Stack 기본 구조 스택은 위에 쌓이고 위에서부터 추출된다. 내가 구현한 스택은 2. ArrayList 같이 배열에 저장하는 게 아니라, 한 노드에 다음 노드를 가리키는 포인터가 존재해서 쭉 이어나가는 Linked List를 사용한 스택이다. 1. int 데이터를 저장하는 stack stack.h #include #ifndef __STACK_H__ #define __STACK_H__ #define TRUE 1 #define FALSE 0 typedef int LData; typedef struct _node { LData data; struct NODE* next; //struct 필수 }NODE; typedef struct s_stack { NODE* top; int count; int size; }..

Big-O Notation 알고리즘의 효율성을 표기할 때 Big-O notation을 사용한다. n²의 증가율을 n이 절대 따라잡을 수 없으므로 그냥 가장 큰 차수를 기준으로 따지는 것 ex) T(n) = 5n²+n+1 => O(n²) Big-O의 정의 두 개의 함수 f(n), g(n)이 주어졌을 때, 모든 n>=k에 대해 f(n) C로 옮긴다 2) 단, 작은 원반 위에 큰 원반을 놓을 수 없다. 해결 방법: 하노이 타워는 재귀 함수로 해결 가능하다! 코드 작성: #include void hanoiTower(int num, char from, char by, char to) { if (num == 1) { //하나일 때는 그냥 옮김 printf("move 1 from %c to %c \n", from, ..