본문 바로가기

컴퓨터공학19

데이터의 검색(query) - 1 기초편 SQL Query의 결과는 relation형태로 나온다. 기본적인 형식은 다음과 같다 select A1,A2,....,An//이 속성들을 추출 from r1,r2,...,rn//이 table에서 추출 where ~~//이 조건에 맞는 튜플을 추출 from부에 명시된 table들에서 where조건에 맞는 tuple들의 select의 속성들을 결과로 도출한다. select부 select부를 통해 추출하고자 하는 속성을 결정할 수 있다. all, distinct SQL은 기본적으로 중복을 제거하지 않는다. 중복을 명시하고자 하는 경우 all을 제거하고자 하는 경우 distinct를 추가한다. select all A1,...,An select distinct A1,...,An * 모든 속성을 보고싶을 경우 '*.. 2022. 8. 1.
테이블 생성 및 업데이트 테이블 생성 create table r (//r: 테이블명 A1 D1,//A: 속성명 A2 D2,//D: 도메인 A3 D3, Ak Dk, Integrity-constraint1,//제약조건들 Integrity-constraint2, Integrity-constraintk ) 제약조건으로는 다음과 같은 사항들을 넣을 수 있다. primary key (A1, A2, ..., An) foreign key (A1, A2, ..., An) reference r A1 not null 테이블 업데이트 1. 튜플 삽입 insert into r values ('value1','value2',...,'value3'); 테이블 r 에 ('value1','value2',...,'value3')을 갖는 튜플을 추가 2. 튜플 .. 2022. 8. 1.
Binary Search Tree binary search tree는 해당 노드보다 큰 값을 갖는 노드는 자신의 오른쪽 노드에, 보다 작은 값을 갖는 노드는 자신의 왼쪽 노드에 배치되는 binary tree이다. 왼쪽 자식 key) inorder_traversal(root->right) 다음은 보다 복잡하지만 재귀를 사용하지 않는 Morris Traversal이라는 inorder traversal 기법이다. 다음 기법은 threaded tree의 기법을 응용한다. morris_traversal(root) if root==NULL return current_node=root while current_node != NULL if current_node->left==NULL print(current_node->key) current_node=.. 2022. 7. 8.
Selection Problem, 중앙값과 순서통계량 i 번째 순서통계량이란 n개의 원소집합 중 i번째로 작은 원소를 말한다. 논의를 간단하게 하기 위해 배열의 원소 개수가 짝수일 경우 (n+1)/2의 floor를 중앙값으로 간주하겠다. 또한, 모든 배열의 원소들이 서로 다른 집합을 가정한다. 그러나 같은 값을 포함하는 집합으로의 확장 역시 가능할 것이다. 선택문제는 정렬을 사용하면 O(n log n)의 시간에 풀 수 있다. 그러나 정렬하지 않고 선택만을 할 경우 O(n)시간에 풀 수도 있다. 1. 최소값과 최대값 모두가 짐작할 수 있는 가장 간단한 방법은 처음부터 끝까지 탐색을 하며 최대/최소값을 찾는 것이다. 이는 n-1번의 비교가 필요하며, 이 이하로 적게 비교는 불가능하다. minimum(A) min=A[1] for i=2 to A.length if.. 2022. 7. 5.
Counting sort 지금까지 살펴본 알고리즘들은 원소들 간의 비교를 통해 정렬작업을 수행한다. 어떤 비교 정렬 알고리즘이라도 원소 n개를 정렬할 때, 최악의 경우 O(n log n)이상의 수행속도를 갖을 수 없다. 그러나, counting sort는 비교 알고리즘이 아니기 때문에 O(n)에 수행이 가능하다. counting sort는 두 가지를 전제한다. 1) n개의 입력원소 모두가 0~k 사이의 정수이다. 2) k=O(n)이다. 즉 k가 n에 비해 압도적으로 크지 않다. counting sort는 각 입력원소 x에 대해 x보다 작은 원소의 갯수를 셈으로써, 출력배열에서 원소 x의 위치를 정해가며 정렬한다. counting_sort(ary,sorted_ary,k) //count를 위한 ary 초기화 count_ary[0~k.. 2022. 7. 5.
Quick sort 퀵정렬은 최악의 경우 O(n^2)의 수행시간으로, 평균 O(n log n)의 수행시간으로 배열을 정렬하는 알고리즘이다. O(n log n) 내에 숨겨진 상수인자가 매우 작아 속도 면에서 매우 효율적이며, 내부 정렬로 작동하기 때문에 실제 문제에서 가장 유용한 정렬 방법 중 하나이다. (내부정렬이란, 정렬하고자 하는 배열 이외의 추가적인 배열공간을 필요로 하지 않는 것을 의미한다.) 퀵정렬은 사전에 배열이 보다 많이 정렬되어 있을수록, 배열 내의 겹치는 원소 수가 많아질 수록 수행시간이 O(n^2)에 가까워진다. 이에 대한 자세한 내용은 후술한다. 퀵정렬은 divide&conquer방식으로 작동한다. A[first~last]의 본래 배열을 A[first~mid-1] A[mid+1~ last]로 분할한다. .. 2022. 7. 4.

티스토리툴바