1과목 데이터베이스 강사 이 민 욱.

Presentation on theme: "1과목 데이터베이스 강사 이 민 욱."— Presentation transcript:

1 1과목 데이터베이스 강사 이 민 욱

2 1. 이진 트리 운행법 1) inorder 운행법 좌, 근, 우측 순서로 운행하는 방법으로 ⓗ ⓓ ⓘ ⓑ ⓔ ⓐ ⓕ ⓒ ⓙ ⓖ ⓚ로 운행한다. 2) preorder 운행법 근, 좌, 우측 순서로 운행하는 방법으로 ⓐ ⓑ ⓓ ⓗ ⓘ ⓔ ⓒ ⓕ ⓖ ⓙ ⓚ로 운행한다. 3) postorder 운행법 좌, 우, 근 순서로 운행하는 방법으로 ⓗ ⓘ ⓓ ⓔ ⓑ ⓕ ⓙ ⓚ ⓖ ⓒ ⓐ로 운행한다. A B C G D E F K H J I

3 2. 폴리쉬 표기법 ① infix  (대상   연산자   대상)(2 + 3) → 중위 표기방식 운행 ② prefix (연산자   대상   대상) (+ 2 3) → 전위 표기방식 운행 ③ postfix(대상   대상   연산자)(2 3 +) → 후위 표기방식 운행 1)Infix 표기를 postfix로 변경하기 A / B * (C + D) + E  AB / CD + * E + ( ( (A / B) * (C + D) ) E ) 2)Infix 표기를 prefix 로 변경하기 A / B * (C + D) + E  + * / AB + CDE ( ( (A / B) * (C + D) ) + E )

4 3) postfix표기를 Infix로 변경하기
ABC - / DEF + * +  A / (B - C) + D * (E + F) ( ( A ( B C - ) / ) (D (E F + ) * ) + ) 4) prefix 표기를 Infix로 변경하기 + / A-BC * D+EF  A / (B - C) + D * (E + F) ( + ( / A ( - B C ) ) (* D ( + E F) ) )

5 1. 비방향성 그래프의 인접행렬(Adjacency matrix)
그래프(Graph)의 표현 1. 비방향성 그래프의 인접행렬(Adjacency matrix)       ▪ 위와 같이 정점들의 집합 {①, ②, ③, ④}이 있을 때 차례로 {1, 2, 3, 4}라는 위치의 값을 배정한다. ▪ 인접행렬을 A라 하고 위와 같이  A = (4 x 4) 2차원 배열을 구성한다. ▪ ①과 ②는 간선이 있으니 1로, ①과 ④는 간선이 없으니 0으로 표시한다. ▪ 비방향 그래프에서 유의할 점은 자기자신에서 자기 자신으로 가는 간선은 존재하지 않는다는 가정 하에 전개시킨다는 점이다. (①에서 ①로 가는 간선은 없다.) 1 2 3 4 1 2 3 4

6 2. 방향성 그래프의 인접행렬(Adjacency matrix)
     ▪ 위와 같이 정점들의 집합 {①, ②, ③, ④}이 있을 때 차례로 {1, 2, 3, 4}라는 위치의 값을 배정한다. ▪ 인접행렬을 A라 하고 위와 같이  A = (4 x 4) 2차원 배열을 구성한다. ▪ ①과 ②는 간선이 있으니 1로, ①과 ③은 간선이 없으니 0으로 표시한다. 1 2 3 4 1 2 3 4

7 정렬(Sort) 1. 정렬방식 1) 내부정렬 소량의 데이터에 대하여 주기억장치 내에만 기억시켜서 정렬하는 방식
종류 : 히프정렬, 삽입정렬, 버블정렬, 선택정렬, 퀵정렬, 2-Way Merge Sort, 기수정렬(=Radix Sort) 2) 외부정렬 대량의 데이터에 대하여 보조기억장치에 기억시켜서 정렬하는 방식으로, 대부분 합병정렬(Merge Sort) 기법으로 처리 종류 : 밸런스 병합정렬, 캐스캐이드 병합정렬, 폴리파즈 병합정렬, 오실레이팅 병합정렬 2. 정렬 알고리즘 선택시 고려사항 ▪ 데이터의 양 ▪ 초기 데이터의 배열 상태 ▪ 키 값들의 분포 상태 ▪ 소요공간 및 작업시간 ▪ 사용컴퓨터 시스템의 특성 내부정렬 외부정렬 선택법 : 히프정렬 삽입법 : 삽입정렬, 셀정렬 교환법 : 버블, 선택, 퀵정렬 병합법 : 2-Way Merge Sort 분배법 : 기수정렬(=Radix Sort) 밸런스 병합 정렬 캐스케이드 병합 정렬 폴리파즈 병합 정렬 오실레이팅 병합 정렬

8 3. 내부정렬 (Internal sort) 정렬하고자 하는 자료를 주기억장치(주 메모리)에 모두 가져다 놓고 고속으로 정렬하는 방식으로 자료의 양이 적을 때 사용 1) 삽입 정렬(Insertion sorting) 대상자료가 일부 정렬되어 있을 때 유리한 정렬방식으로 선택(기준)된 키 값을 앞쪽자료들의 킷값과 비교하여 자신의 위치를 찾아 삽입하여 정렬시키는 방식 2) 셀 정렬(Shell Sort) shell 정렬은 삽입정렬의 확장된 개념으로 삽입정렬에서는 데이터가 이미 정렬되어 있는 경우에는 비교하지 않으므로 정렬 간격을 축소시켜가면서 데이터를 미리 듬성듬성 정렬하여 놓고 삽입정렬하자는 방식, 3) 버블 정렬(Bubble Sort) 인접키와 비교하면서 교환하여 정렬하되 단계별로 수행하면서 각 단계 수행 중 교환이 일어나지 않으면 정렬이 완료된 것이므로 더 이상의 단계를 수행하지 않고 종료시켜 정렬을 완료시키는 방식 4) 퀵 정렬(Quick Sort) 첫 번째 데이터를 중간 값으로 설정하고 그 중간 값을 대상 자료 중 적당한 위치에 위치시켜 대상자료를 부분적으로 나누어 가면서 되부름 방식으로 반복 분류시켜 정렬하는 방식

9 5) 선택 정렬(Selection sorting)
전체 자료 중에서 작은(혹은 큰 것) 킷값을 찾아 선택(기준)된 위치에 교환하여 정렬하는 방식 6) 힙 정렬(Heap Sort) 완전이진 트리인 오더드 트리 형태로 데이터를 저장하고 트리 엑세스 알고리즘에 의해 부노드가 자노드 보다 크게 되도록 구성하는데 첫 번째 구성된 형태를 초기 heap상태라고 한다. 이 초기 heap 상태에서 근 노드를 맨 마지막으로 이동시켜 대상 개수를 하나씩 줄여나가면서 정렬하는 방식 7) 2-way 합병 정렬 두개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정하고 나서 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브 리스트로 만들어 최종적으로 하나의 정렬된 파일이 될 때까지 반복하여 정렬하는 방식 8) 버킷정렬(bucket sort) 정렬할 데이터의 기수(radix) 값에 따라 스택(stack)이나 큐(Queue)에 분배하여 정렬하는 방식으로 여분의 기억공간이 많이 필요하다. O(k(n+q)) (k : 반복 횟수, q : 스택이나 큐의 수)