School/DataStructure

Data Structure - Sorting ( Merge Sort )

How Fast Can We Sort key에 의존한 comparisons와 interchanges가 있는 한 우리는 O(nlogn)보다 빠른 sorting algorithm을 만들 수 없습니다. 다음과 같이 decision tree를 그려서 input sequence R1, R2, R3에서 나올 수 있는 경우 의 수를 찾아보니 3!개가 나옵니다. Theorm : Any decision tree that sorts n distinct elements has a height of at least log2(n!) + 1 우리가 n개의 원소를 정렬한다고 했을 때, 여기에서는 위에서 본 것처럼 n!개의 가능한 결과들이 있습니다. -> n1개의 leaft nodes가 존재하기 떄문 그리고 binary tree는 ..

Data Structure - Sorting ( Quick Sort )

Quick Sort quick sort는 불안전 정렬 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 비교 정렬에 속합니다. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 속도를 자랑하는 정렬 방법입니다. 합병 정렬(merge sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할합니다. 분할 정복(divide and conquer)방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 분할 정복 방법은 대개 순환 호출을 이용해서 구현합니다. 과정 설명 리스트 안에 있는 한 요소를 선택합니다. 이렇게 고른 원소를 피벗(pivot)이라고 합니다. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소..

Data Structure - Sorting ( Insertion Sort )

sequential Search sequential search는 리스트 레코드를 left-to-right order로 비교하면서 하나의 값을 찾는 것입니다. /sequentialSort.c #include #include int seqSearch(int a[], int k, int n) { int i; for (i = 1; i = n) return -1; return i; } int main(void) { int sortArr[100] = {0}; int count = 0; FILE *fp_read = fopen("sort.txt", "r"); while ((fscanf(fp_read, "%d", sortArr + count) != EOF)) {..

Data Structure - Graph ( AOV, AOE Network )

AOV Network AOV는 Activity On Vertex의 약자입니다. 즉 정점이 Activity 작업을 나타내고, 간선이 작업간의 우선순위 관계를 나타내는 방향 그래프입니다. 위의 그래프의 각 정점이 작업을 나타내다고 해 봅시다. 1번 작업이 끝나면 3, 4번 작업을 할 수 있고, 3, 4번 작업이 끝나야 5번 작업을 할 수 있고, 2번 작업이 끝나야 6번 작업을 할 수 있고, 마지막으로 5, 6번 작업이 끝나면 7번을 할 수 있는 식입니다. predecessor는 어떤 작업을 하기 전에 해야하는 작업을 의미하고, successor는 어떤 작업을 하고 나서 해야 할 작업을 의미합니다. 앞에 immediate가 붙으면 바로 전, 바로 후의 작업을 의미합니다. AOV네트워크에서 중요한 것은 어떤 순..