Chapter 04. 자료구조.

Presentation on theme: "Chapter 04. 자료구조."— Presentation transcript:

1 Chapter 04. 자료구조

2 배열, 리스트, 스택, 큐, 트리, 그래프 등의 다양한 자료구조를 배우고 이들 자료구조에서 실행되는 연산을 학습한다
학습목표 자료와 자료구조의 개념을 명확히 이해한다 배열, 리스트, 스택, 큐, 트리, 그래프 등의 다양한 자료구조를 배우고 이들 자료구조에서 실행되는 연산을 학습한다 정렬의 개념과 용도를 알아본다 삽입 정렬, 선택 정렬, 합병 정렬, 퀵 정렬, 기수 정렬 등 기본적인 정렬 방법을 학습한다 해싱의 개념을 이해하고 해시 함수로 많이 쓰이는 나눗셈법, 중간 제곱법, 폴딩법, 기수 변환법, 자릿수 분석법을 학습한다

3 자료(data) 정보(information) 자료구조 일의 바탕이 될 재료 프로그램을 수행하는데 필요한 재료
Section 1. 자료와 자료구조 자료(data) 일의 바탕이 될 재료 프로그램을 수행하는데 필요한 재료 정보(information) 컴퓨터를 이용하여 정제한 자료 사용자의 요구에 따라 꼭 필요한 항목만 추출한 데이터 자료구조 자료 사이의 논리적인 관계가 프로그램에 의해 쉽게 이용되도록 구성한 개별적인 자료 원소들의 집합 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업(조직화 구조화) 수치적 문제 :기본자료 구조(정수,실수,배열)로 해결 비수치적 문제 : 기본자료 구조로 다양한 자료의 복합적 관계 표현이 어려움 컴퓨터 분야에서의 자료구조:자료를 컴퓨터에 어떻게 표현, 표현한 자료를 효율적으로 저장할 것을 처리하는 논리적인 구조와 프로그램적인 처리 방법 컴퓨터(자료처리 장치), 자료구조는 컴퓨터를 전공에 기본적이고 필수적.

4 원소(element) / 멤버(member) 다차원 배열(multi-dimensional array)
Section 2. 배열 배열(array) 같은 자료형(data type)을 갖는 두 개 이상의 데이터 항목을 하나의 변수 이름으로 묶고 선언해서 사용하는 구조 자료를 컴퓨터 기억장치 내의 연속적인 기억장소에 저장하여 순차적으로 또는 임의적으로 접근할 수 있는 가장 간단한 선형 자료구조 원소(element) / 멤버(member) 배열을 구성하는 같은 자료형의 각 항목 다차원 배열(multi-dimensional array) 두 개 이상 여러 개의 배열로 구성된 배열

5 배열로 사용할 기억공간을 할당하는 방법 포트란, 코볼 파스칼, C 배열(계속) 정적 할당(static allocation)
원시 프로그램이 컴파일될 때 기억공간이 할당됨 파스칼, C 동적 할당(dynamic allocation) 기억장소 할당이 프로그램 실행 시 이루어지는 방법

6 1차원 배열(one-dimensional array 또는 vector)
가장 단순한 형태의 배열 기억장치 내에서 같은 자료형을 갖는 원소가 연속적인 기억장소에 할당되어 순서적으로 데이터를 저장하게 되어 있는 자료구조 하한 L(lower bound), 상한 U(upper bound) 배열 원소 수는 U-L+1

7 1차원 배열(one-dimensional array 또는 vector)(계속)
C언어에서의 배열 a[100] 하한은 0이고, 상한은 99로 모두 100개의 기억장소가 할당되는 것 컴퓨터 기억장치에서 고유의 주소를 부여받는 최소단위가 바이트이므로 배열의 각 원소가 4바이트를 차지한다면 배열의 크기는 (U-L+1)*4가 된다

8 다차원 배열(multi-dimensional array)
2차원 배열(two-dimensional array 또는 matrix) 같은 크기의 1차원 배열이 여러 개 모여서 이루어진 배열 행렬(matrix) 가로줄의 벡터: 행(row) 세로줄의 벡터: 열(column) 2차원 배열의 상한과 하한 일반화 b(L1..U1, L2..U2)로 표시 행의 하한 L1, 열의 하한 L2 행의 상한 U1, 열의 상한 U2

9 다차원 배열(multi-dimensional array)

10 다차원 배열(multi-dimensional array)(계속)
컴퓨터 기억장치 1차원으로 구성되어 있는 선형구조 2차원 배열을 선형적 기억장소에 저장시키는 방법 행 우선 순서(row-major order) 코볼, PL/I, 파스칼, C

11 다차원 배열(multi-dimensional array)(계속)
2차원 배열을 행 우선 순서로 저장할 때 원소 b(i, j) 주소는 다음과 같이 계산 address(b(i, j))=address(b(L1, L2))+(i-L1)*(U2-L2+1)*k+(j-L2)*k 예) b(0..9, 0..19) b(4,5)의 주소? 기본주소b(L!,L2)=1000, 각원소 크기8Byte b(4,5)=1000+(4-0)*(19-0+1)*8+(5-0)*8= 1680 열 우선 순서(column-major order) 포트란 2차원 배열을 열 우선 순서로 저장했을 때 a(i, j)의 주소는 다음 식으로 계산 address(a(i, j)) = address(a(L1, L2)) +(j - L2)*(U1-L1+1)*k +(i-L1)*k 예) b(0..9, 0..9) b(5,6)의 주소? 기본주소b(L!,L2)=1000, 각원소 크기4Byte b(5,6)=1000+(6-0)*(9-0+1)*4+(5-0)*4= 1260

12 행렬의 원소값이 0인 원소가 많은 행렬 (ex) 기억장소의 낭비를 줄이기 위해 0이 아닌 원소만 따로 저장하는 방법이 있음
희소 행렬(sparse matrix) 행렬의 원소값이 0인 원소가 많은 행렬 (ex) 기억장소의 낭비를 줄이기 위해 0이 아닌 원소만 따로 저장하는 방법이 있음

13 희소 행렬(sparse matrix)(계속)
많이 쓰이는 저장 방법 0이 아닌 원소를 <행, 열, 원소값>의 벡터로 열이 3인 2차원 배열 이용 0이 아닌 원소는 행의 오름차순,행이 같은 경우 열의 오름차순 8행6열10원소

14 Section 3. 리스트 - 선형 리스트(linear list, ordered list)
어떤 순서에 의해 나열된 항목이 여러 개인 데이터 모임 순서 리스트(ordered list) 순차적 리스트(sequential list) (ex) 요일 리스트 : 일요일, 월요일, 화요일, 수요일, 목요일, 금요일, 토요일 무지개 리스트 : 빨강, 주황, 노랑, 초록, 파랑, 남색, 보라 (a0, a1, a2, ....., an-1)으로 표시 원소 또는 노드 선형 리스트를 구성하는 각 항목 리스트 크기 리스트를 이루는 원소 수 n

15 선형 리스트(linear list, ordered list)(계속)
리스트 연산 호출(access) 리스트를 구성하는 임의의 원소 위치를 파악하여 데이터에 접근하는 연산 삽입(insertion) 리스트에 새로운 원소를 집어 넣는 연산 삭제(deletion) 리스트에 어떤 원소를 제거하는 연산 갱신(update) 리스트에 들어 있는 어떤 원소의 내용을 변경시키는 연산 검색(search) 리스트에서 어떤 특정 원소를 찾는 연산

16 선형 리스트(linear list, ordered list) – 리스트 연산(계속)
정렬(sort) 리스트를 구성하는 모든 원소들을 어떤 순서로 재배치하는 연산 복사(copy) 리스트를 전부 또는 일부 복사하여 새로운 리스트로 만드는 연산 분리(split) 리스트 하나를 리스트 두 개 이상으로 나누는 연산 합병(merge) 리스트 둘 이상을 리스트 하나로 합치는 연산

17 연결 리스트(linked list)를 구성하는 각 노드
선형 리스트를 컴퓨터 내부에 저장하는 방법 순차적 사상(sequential mapping) 1차원 배열 이용 비순차적 사상(non-sequential mapping) 포인터 변수(링크)를 사용하는 연결 리스트로 저장 연결 리스트(linked list)를 구성하는 각 노드 데이터 필드(data field)와 링크 필드(linked field) 가지고 있음 각 노드는 하나 또는 그 이상의 데이터 필드 포함, 링크 필드는 포인터 변수로서 다른 노드의 주소를 저장 즉, 리스트를 구성하는 각 원소가 연속적인 기억장소에 저장되지 않아도 링크에 의해 다른 노드에 연결되어 있음으로 접근이 용이

18 연결 리스트(linked list)(계속)
단일 연결 리스트(singly linked list) 리스트를 구성하는 각 노드가 링크 필드를 하나만 갖고 있는 연결 리스트 각 노드는 하나 또는 그 이상의 데이터 필드와 다음 노드의 주소를 나타내는 단 하나의 링크필드로 구성 원형 연결 리스트(circular linked list) 마지막 모드를 헤드 노드와 연결시켜 원형으로 만든 리스트 단일연결 리스트에서는 선행 노드를 접근하려면 헤드 노드 부터 시작해야하는 제한성

19 연결 리스트(linked list)(계속)
이중 연결 리스트(doubly linked list) 링크 필드 두 개를 사용하는 리스트 선행 노드 접근에 용이 다중 연결 리스트(multi-linked list) 연결 리스트를 구성하는 각 노드가 링크 필드 두 개 이상을 사용하는 연결 리스트 이중 원형 연결 리스트 이중 연결 리스트에서 첫 번째 노드 링크와 마지막 노드 링크를 서로 연결시켜 원형으로 구성한 것

20 Section 4. 스택과 큐 – 스택(stack)
원소의 삽입과 삭제가 한쪽 끝인 톱(top)에서만 이루어지도록 제한하는 특별한 형태의 자료구조 푸쉬(push) 원소를 삽입하는 연산 팝(pop) 원소를 삭제하는 연산 스택의 구조

21 후입선출(LIFO, Last-In First-Out) 리스트 푸쉬다운(push-down) 리스트
스택(stack)(계속) 후입선출(LIFO, Last-In First-Out) 리스트 가장 나중에 삽입한 원소를 가장 먼저 삭제함 푸쉬다운(push-down) 리스트 스택으로 구성되는 리스트는 연속적인 푸쉬 연산에 의해 만들어짐 스택에서의 삽입과 삭제

22 오버플로우(overflow) 발생 언더플로우(underflow) 발생 스택의 오버플로우를 처리하기 위한 방안
스택(stack)(계속) 오버플로우(overflow) 발생 스택이 가득 차서 더 이상 삽입할 수 없을 경우 언더플로우(underflow) 발생 스택이 비어서 더 이상 삭제할 수 없을 경우 스택의 오버플로우를 처리하기 위한 방안 이중 스택 구조 저장 공간 하나를 스택 2개로 구성해서 운영 다중 스택 구조 저장 공간 하나를 스택 여러 개로 구성해서 운영

23 새로운 원소 삽입이 한 쪽에서만 이루어지고, 삭제는 다른 한 쪽에서만 이루어지는 특별한 형태의 자료구조
큐(queue) 새로운 원소 삽입이 한 쪽에서만 이루어지고, 삭제는 다른 한 쪽에서만 이루어지는 특별한 형태의 자료구조 일상 생활의 줄서기-> 큐의 대표적인 예 리어(rear) 큐에서 원소 삽입(enqueue)이 일어나는 한 쪽 끝 프론트(front) 큐에서 원소 삭제(dequeue)가 일어나는 다른 쪽 끝

24 선입선출(FIFO, First-In First-Out) 리스트
큐(queue)(계속) 선입선출(FIFO, First-In First-Out) 리스트 제일 먼저 삽입된 원소가 제일 먼저 삭제됨 서비스를 받기 위한 대기행렬로 사용 FCFS(First-Come First-Served) 큐에서의 삽입과 삭제

25 배열로 구현한 큐 이동 문제를 해결하기 위한 방법 원형 큐의 개념도
큐(queue)(계속) 구현 배열이나 연결리스트 사용하여 구현(프로그래밍 언어의 기본 자료구조가 아님) 배열로 구현한 큐 이동 문제를 해결하기 위한 방법 원형 큐(circular queue) 사용 원형 큐의 개념도 160쪽

26 뿌리(root)를 최상위에 두고 거꾸로 서 있는 형태
Section 5. 트리 – 트리의 기본 개념 뿌리(root)를 최상위에 두고 거꾸로 서 있는 형태 노드(node)라고 하는 정보 항목이 에지(edge)로 연결되어 계층적 구조를 이루는 비선형 자료구조(non-linear data structure) 계층적 자료구조(hierarchical data structure)

27 트리의 기본 개념(계속) (ex) K 대학의 조직구조

28 리프 노드(leaf node) 또는 단말 노드(terminal node) 비단말 노드(nonterminal node)
트리의 기본 개념(계속) 노드 차수(degree) 한 노드가 가지고 있는 서브트리(subtree) 수 트리의 차수(degree of tree) 트리에 있는 노드 차수 중에서 가장 큰 차수 리프 노드(leaf node) 또는 단말 노드(terminal node) 차수가 0인 노드 비단말 노드(nonterminal node) 차수가 1 이상인 노드 트리의 깊이(depth) 또는 높이(height) 트리에서 가장 큰 레벨

29 트리의 기본 개념(계속) (ex) 트리

30 부모 노드(parent node) 자식 노드(child node) 형제 노드(siblings node)
트리의 기본 개념(계속) 부모 노드(parent node) 어떤 노드에서 그 노드 바로 위의 상위 레벨에 있으면서 그 노드와 에지로 연결된 노드 자식 노드(child node) 어떤 노드 바로 아래 하위 레벨에 있으면서 에지로 연결된 노드 형제 노드(siblings node) 부모 노드가 같은 노드 단말 노드(terminal node) 자식이 없는 노드

31 어떤 노드의 후손(descendents)
트리의 기본 개념(계속) 어떤 노드의 선조(ancestor) 그 노드에서 루트에 이르는 경로 위에 있는 모든 노드 어떤 노드의 후손(descendents) 그 노드와 에지로 연결되어 있으면서 하위레벨에 있는 모든 노드 숲(forest) 독립적인 여러 트리의 집단 N개의 서브트리를 가진 트리에서 루트노드를 제거하면 분리된 N개의 트리가 숲이 됨

32 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리
이진 트리(binary tree) 자료구조에서 가장 많이 쓰이는 트리구조. 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리 0 ≤ 노드의 차수 ≤ 2 서브트리가 공백이 될 수 있음 양쪽 서브트리가 모두 공백이면 리프노드 왼쪽 자식 노드(left child node) 오른쪽 자식 노드(right child node) EGHI 양쪽서브트리가 공백인 단말노드 D는 왼쪽, F는 오른쪽 서브트리가 공백

33 이진 트리(binary tree)(계속)
이진트리는 왼쪽 서브트리(left subtree)와 오른쪽 서브트리(right subtree)를 분명하게 구분 두 개의 다른 이진 트리 이진 트리가 일반 트리와 다른점 노드 차수가 2로 제한된다는 점 공백 트리 개념이 있음 서브트리 순서를 구별함(왼쪽과 오른쪽의 서브트리의 순서)

34 이진 트리(binary tree)(계속)
깊이가 k인 이진 트리에서 최대 노드 수 2k+1-1 포화 이진 트리(full binary tree) 노드의 총 개수가 2k+1-1인 트리 (ex) 단말노드는 마지막 레벨, 단말을 제외한 내부 노드는 모두 2개의 자식노드 깊이가 3인 포화이진트리 노드수 2K+1 -1= 15

35 이진 트리(binary tree)(계속)
완전 이진 트리(complete binary tree) 높이가 k면서 총 노드의 수 n이 최대 노드 수인 2k+1-1보다 작고 노드 번호가 포화 이진 트리와 1부터 n까지 모두 일치하는 트리 (ex)

36 이진 트리(binary tree)(계속)
편향 이진 트리 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리 왼쪽 편향 이진 트리 모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리 오른쪽 편향 이진 트리 모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리

37 이진 트리(binary tree)(계속)
이진 트리의 순차 자료구조 구현 1차원 배열의 순차 자료구조 사용 높이가 h인 포화 이진 트리의 노드번호를 배열의 인덱스로 사용 인덱스 0번 - 실제로 사용하지 않고 비워둔다. 인덱스 1번 – 루트 저장 노드의 총 개수가 2k+1-1인 트리

38 이진 트리 순회(binary tree traversal)
트리의 노드가 데이터를 저장하는데 일정한 규칙에 따라 이진 트리의 모든 노드를 꼭 한 번씩만 방문하는 것 계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산 순회를 위해 수행할 수 있는 작업 정의 ⑴ 현재 노드를 방문하여 데이터를 읽는 작업 D ⑵ 현재 노드의 왼쪽 서브트리로 이동하는 작업 L ⑶ 현재 노드의 오른쪽 서브트리로 이동하는 작업 R 전위 순회(preorder traversal) 루트 노드를 방문 → 왼쪽 서브트리를 전위 순회 → 오른쪽 서브트리를 전위 순회 중위 순회(inorder traversal) 왼쪽 서브트리를 전위 순회 → 루트 노드를 방문 → 오른쪽 서브트리를 전위 순회 후위 순회(postorder traversal) 왼쪽 서브트리를 전위 순회 → 오른쪽 서브트리를 전위 순회 → 루트 노드를 방문

39 이진 트리 순회(binary tree traversal)(계속)
전위 순회 경로 전위 순회 과정 >> A-B-D-H-E-I-J-C-F-G-K

40 이진 트리 순회(binary tree traversal)(계속)
전위 순회 과정 >> A-B-D-H-E-I-J-C-F-G-K ① 루트 A에서 시작하여 현재 노드 A의 데이터를 읽고, 왼쪽 서브트리 B로 이동한다. ② 현재 노드 B의 데이터를 읽고, 왼쪽 서브트리 D로 이동한다. ③ 현재 노드 D의 데이터를 읽는다. ④ 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽고, 오른쪽 노드인 공백 노드를 읽는 것으로 노드 D에 대한 순회가 끝난다. 이제 현재 노드 D의 이전 경로인 노드 B의 오른쪽 서브트리 E로 이동한다. ⑤ 현재 노드 E의 데이터를 읽는다. ⑥ 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ⑦ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽는 것으로 노드 E에 대한 순회가 끝나고, 이것으로 노드 E의 이전 경로인 노드 B의 오른쪽 서브트리의 순회가 끝난다. 다시 노드 B의 이전 경로인 노드 A로 돌아가서 노드 A의 오른쪽 서브트리 C로 이동한다. ⑧ 현재 노드 C의 데이터를 읽는다. ⑨ 현재 노드 C의 왼쪽 단말노드 F의 데이터를 읽고, 오른쪽 서브트리 G로 이동한다. ⑩ 현재 노드 G의 데이터를 읽는다. ⑪ 공백노드인 왼쪽 단말노드를 읽고, 현재 노드 G의 오른쪽 단말노드 K의 데이터를 읽는다.

41 이진 트리 순회(binary tree traversal)(계속)
중위 순회경로 수행 방법 ① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L ② 현재 노드 n을 방문하여 처리한다. : D ③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R 중위 순회 과정 >> H-D-B-I-E-J-A-F-C-G-K

42 이진 트리 순회(binary tree traversal)(계속)
중위 순회 과정 >> H-D-B-I-E-J-A-F-C-G-K ① 루트 A에서 시작하여 노드 A의 왼쪽 서브트리 B로 이동한다. 현재 노드 B의 왼쪽 서브트리 D로 이동한다. 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽는다. ② 현재 노드 D의 데이터를 읽고, 오른쪽 단말노드인 공백노드를 읽고 이전 경로인 노드 B로 돌아간다. ③ 현재 노드 B의 왼쪽 서브트리 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 오른쪽 서브트리 E로 이동한다. ④ 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ⑤ 현재 노드 E의 데이터를 읽는다. ⑥ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ⑦ 노드 B는 이미 방문했으므로 다시 이전 경로인 노드 A로 이동한다. 이로써 현재 노드 A의 왼쪽 서브트리에 대한 순회가 끝났으므로 현재 노드 A의 데이터를 읽고, 오른쪽 서브트리 C로 이동한다. ⑧ 현재 노드 C의 왼쪽 단말노드 F의 데이터를 읽는다. ⑨ 현재 노드 C의 데이터를 읽고, 오른쪽 서브트리 G로 이동한다. ⑩ 현재 노드 G의 왼쪽 단말노드인 공백노드를 읽고, 현재 노드 G의 데이터를 읽는다. ⑪ 현재 노드 G의 오른쪽 단말노드 K의 데이터를 읽는다.

43 이진 트리 순회(binary tree traversal)(계속)
후위 순회경로 수행 방법 ① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L ② 현재 노드 n의 오른쪽 서브트리로 이동한다. : R ③ 현재 노드 n을 방문하여 처리한다. : D 후위 순회 과정 >> H-D-I-J-E-B-F-K-G-C-A

44 이진 트리 순회(binary tree traversal)(계속)
후위 순회 과정 >> H-D-I-J-E-B-F-K-G-C-A ①루트 A에서 시작하여 노드 A의 왼쪽 서브트리 B로 이동한다. 현재 노드 B에서 왼쪽 서브트리 D로 이동한다. 현재 노드 D의 왼쪽 단말노드 H의 데이터를 읽는다. ② 현재 노드 D의 오른쪽 단말노드인 공백노드를 읽는다. 현재 노드 D의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ③ 현재 노드 B의 왼쪽 서브트리에 대한 순회가 끝났으므로 현재 노드 B의 오른쪽 서브트리 E로 이동 한다. 현재 노드 E의 왼쪽 단말노드 I의 데이터를 읽는다. ④ 현재 노드 E의 오른쪽 단말노드 J의 데이터를 읽는다. ⑤ 이제 현재 노드 E의 데이터를 읽고, 이전 경로인 노드 B로 이동한다. ⑥ 현재 노드 B의 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 B의 데이터를 읽고, 이전 경 로인 노드 A로 이동한다. ⑦ 현재 노드 A의 왼쪽 서브트리에 대한 순회가 끝났으므로, 오른쪽 서브트리 C로 이동한다. 현재 노 드 C의 왼쪽 단말노드 F의 데이터를 읽는다. ⑧ 현재 노드 C의 오른쪽 서브트리 G로 이동한다. 현재 노드 G의 왼쪽 단말노드인 공백노드를 읽고, 오른쪽 단말노드 K의 데이터를 읽는다.  ⑨ 이제 현재 노드 G의 데이터를 읽고, 이전 경로인 노드 C로 이동한다. ⑩ 현재 노드 C의 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 C의 데이터를 읽고, 이전 경 로인 노드 A로 이동한다. ⑪ 루트노드 A에 대한 오른쪽 서브트리에 대한 순회가 끝났으므로, 현재 노드 A의 데이터를 읽는다.

45 힙 트리(heap tree) 힙(heap) 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모노드의 키 값 ≥ 자식노드의 키 값} 루트 노드 : 키 값이 가장 큰 노드 최소 힙(min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모노드의 키 값 ≤ 자식노드의 키 값} 루트 노드 : 키 값이 가장 작은 노드 완전 이진 트리에:높이가 k면서 총 노드의 수 n이 최대 노드 수인 2k+1-1보다 작고 노드 번호가 포화 이진 트리와 1부터 n까지 모두 일치하는 트리

46 힙 트리(heap tree) 최대 힙(max heap) 모든 노드의 키 값이 자식 노드의 키 값보다 작지 않은 완전 이진 트리(complete binary tree)

47 힙 트리(heap tree)(계속) 최소 힙(min heap) 모든 노드의 키 값이 자식 노드의 키 값보다 크지 않은 힙 트리

48 힙에서의 삽입 연산 1단계 : 완전 이진 트리를 유지하면서 노드를 확장하고, 삽입할 원소를 임시 저장
힙 트리(heap tree) 힙에서의 삽입 연산 1단계 : 완전 이진 트리를 유지하면서 노드를 확장하고, 삽입할 원소를 임시 저장 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드가 된다. n+1번 자리에 노드를 확장하고 삽입할 원소를 임시 저장한다. 2단계 : 만들어진 완전 이진 트리 내에서 삽입 원소의 자리를 찾는다. 현재 위치에서 부모노드와 비교하여 크기 관계를 확인한다. {부모노드의 키 값 ≥ 삽입 원소의 키 값}의 관계가 성립하지 않으면, 부모노드의 원소와 삽입 원소의 자리를 서로 바꾼다.

49 힙에서의 삽입 연산 예 1) - 17을 삽입하는 경우 힙 트리(heap tree)
힙에서의 삽입 연산 예 1) - 17을 삽입하는 경우 임시로 저장한 위치에서 부모노드와 크기를 비교하여 히프의 크기관계가 성립하므로, 현재 위치를 삽입 원소의 자리로 확정

50 힙 트리(heap tree) 힙에서의 삽입 연산 예 2) - 23을 삽입하는 경우 (3)비교할 부모 노드가 없으면 자리 확정

51 ① 현재 힙의 크기를 하나 증가시켜서 노드위치를 확장하고, 확장한 노드번호가 현재의 삽입 위치 i가 된다.
힙 트리(heap tree) ① 현재 힙의 크기를 하나 증가시켜서 노드위치를 확장하고, 확장한 노드번호가 현재의 삽입 위치 i가 된다. ② 삽입할 원소 item과 부모노드 heap[i/2]를 비교하여 item이 부모노드 보다 작거나 같으면  현재의 삽입 위치 i를 삽입 원소의 위치로 확정한다. ③ 만약 삽입할 원소item이 부모노드 보다 크면, 부모노드와 자식노드의 자리를 바꾸어 최대 힙의 관계를 만들어야 하므로 부모노드 heap[i/2]를 현재의 삽입 위치 heap[i]에 저장하고, ④ i/2를 삽입 위치 i로 하여 ②~④를 반복하면서 item을 삽입할 위치를 찾는다. ⑤ 찾은 위치에 삽입할 노드 item을 저장하여 최대힙의 재구성 작업을 완성하고 삽입 연산을 종료한다.

52 힙에서의 삭제 연산 힙 트리(heap tree) 힙에서는 루트 노드의 원소만을 삭제 할 수 있다.
1단계 : 루트 노드의 원소를 삭제하여 반환한다. 2단계 : 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정한다. 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 해서서 마지막 노드, 즉 n번 노드를 삭제한다. 삭제된 n번 노드에 있던 원소는 비어있는 루트노드에 임시 저장한다. 3단계 : 완전 이진 트리 내에서 임시 저장된 원소의 자리를 찾는다. 현재 위치에서 자식노드와 비교하여 크기 관계를 확인한다. {임시 저장 원소의 키 값 ≥ 자식노드의 키 값 }의 관계가 성립하지 않으면, 자식노드의 원소와 임시 저장 원소의 자리를 서로 바꾼다.

53 힙 트리(heap tree) 힙에서의 삭제 연산 예)

54 ①루트노드 heap[1]을 item에 저장하고, ②마지막 노드의 원소 heap[n]을 temp에 임시 저장한 후에,
힙 트리(heap tree) ①루트노드 heap[1]을 item에 저장하고, ②마지막 노드의 원소 heap[n]을 temp에 임시 저장한 후에, ③마지막 노드를 삭제한다. ④마지막 노드의 원소였던 temp의 현재 저장위치 i는 루트노드의 자리인 1번이 된다. ⑤현재 저장위치에서 자식노드 heap[j]와 heap[j+1]이 있을 때 키 값이 큰 자식노드 heap[j+1]의 키 값과 temp를 비교하여, temp가 크거나 같으면 현재 위치가 temp의 자리로 확정된다. ⑥만약 temp가 자식노드 heap[j+1]보다 작으면 자식노드와 자리를 바꾸고 다시 ⑤~⑥을 반복하면서 temp의 자리를 찾는다. ⑦찾은 위치에 temp를 저장하여 최대 히프의 재구성 작업을 완성하고 ⑧루트노드를 저장한 item을 반환하는 것으로 삭제 연산을 종료한다.

55 이진 탐색 트리(BST, Binary Search Tree)
파일에서 임의의 원소를 삽입, 삭제, 검색하거나 또는 많은 자료를 순차적으로 정렬하는 데 사용되는 효율적인 자료구조 이진 탐색 트리가 만족해야 할 성질 모든 노드는 트리에서 유일한 키 값을 가짐 왼쪽 서브트리에 있는 모든 노드의 키 값들은 루트의 키 값보다 작음 오른쪽 서브트리에 있는 모든 노드의 키 값들은 루트의 키 값보다 큼 왼쪽 서브트리와 오른쪽 서브 트리의 모두가 이진 탐색 트리

56 이진 탐색 트리(BST, Binary Search Tree)(계속)
(ex)

57 그래프(graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현하기 위한 자료구조
Section 6. 그래프 그래프(graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현하기 위한 자료구조 그래프 G 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 G = (V, E) V는 그래프에 있는 정점들의 집합 E는 정점을 연결하는 간선들의 집합

58 그래프(graph) 1736년에 수학자 오일러(Euler)가 퀘닉스버그 다리 문제를 해결하는 데 처음으로 이용
Section 6. 그래프 그래프(graph) 1736년에 수학자 오일러(Euler)가 퀘닉스버그 다리 문제를 해결하는 데 처음으로 이용 퀘닉스버그 다리 문제 어느 한 쪽 육지를 출발하여 모든 다리를 단 한 번씩 경유하여 다시 출발점으로 되돌아 올 수 있는가 하는 것

59 오일러 각 지역을 정점(vertex)으로 정의하고 모든 다리를 에지(edge)로 정의
그래프(계속) 오일러 각 지역을 정점(vertex)으로 정의하고 모든 다리를 에지(edge)로 정의 오일러 그래프 고안함으로써 문제 해결 오일러 경로 임의의 정점을 출발하여 모든 에지를 한 번씩 거친 후에 출발한 정점으로 돌아오기 위해서는 홀수 개의 에지를 갖는 정점 수가 0 또는 2개여야 함을 증명

60 그래프 G 하나 이상의 정점 혹은 노드들의 집합 V와 두 정점의 쌍으로 구성되는 에지들의 집합 E로 이루어져 있음
그래프(계속) 그래프 G 하나 이상의 정점 혹은 노드들의 집합 V와 두 정점의 쌍으로 구성되는 에지들의 집합 E로 이루어져 있음 두 집합은 유한하다고 가정하며 G=(V, E)와 같이 표기 정점 집합 V 및 에지 집합 E가 그래프 G에 대한 것임을 밝히고자 할 때는 각각 V(G)와 E(G)로 나타냄

61 그래프의 구분 무방향 그래프(undirected graph)
그래프(계속) 그래프의 구분 무방향 그래프(undirected graph) 정점 사이가 방향성이 없는 에지로 연결된 그래프 에지를 나타내는 정점 쌍에 순서가 없음 <v1, v2>와 <v2, v1>은 같은 에지 방향 그래프(directed graph) 또는 다이그래프(digraph) 에지가 화살표로 표현되어 방향성을 가지는 그래프 정점 쌍에 나타난 정점의 순서 중요 <v1, v2>와 <v2, v1>은 같은 에지가 아님 <v1, v2> v1 은 에지의 꼬리(tail) v2 은 에지의 머리(head)

62 무방향 그래프(undirected graph)
그래프(계속) 무방향 그래프(undirected graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타낸다. V(G1)={A, B, C, D}      E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)} V(G2)={A, B, C}          E(G2)={(A,B), (A,C), (B,C)}

63 방향 그래프(directed graph) , 다이그래프(digraph)
그래프(계속) 방향 그래프(directed graph) , 다이그래프(digraph) 간선이 방향을 가지고 있는 그래프 정점 Vi에서 정점 Vj를 연결하는 간선 즉, Vi→Vj를 <Vi, Vj>로 표현 Vi를 꼬리(tail), Vj를 머리(head)라고 한다. <Vi, Vj>와 <Vj, Vi>는 서로 다른 간선 V(G3)={A, B, C, D}      E(G3)={<A,B>, <A,D>, <B,C>, <B,D>, <C,D>} V(G4)={A, B, C}          E(G4)={<A,B>, <A,C>, <B,A>, <B,C>}

64 다중 그래프(multi graph) 단순 그래프(simple graph)
그래프(계속) 다중 그래프(multi graph) 두 정점 사이에 한 개 이상의 에지들이 포함되는 그래프 엄격히 말해서 그래프로 취급하지 않음 단순 그래프(simple graph) 두 정점 사이에 0개 혹은 오직 1개의 에지를 갖는 그래프 그래프로 취급

65 가중치 그래프(weighted graph)
그래프(계속) 가중치 그래프(weighted graph) 네트워크(network) 그래프의 에지에 가중치를 부여한 그래프 가중치(weight) 시간이나 비용 또는 거리와 같이 의미가 있는 값

66 n개의 정점을 갖는 무방향 그래프에서 vi≠vj인 서로 다른 무순서 쌍(vi, vj)들의 최대수
그래프(계속) n개의 정점을 갖는 무방향 그래프에서 vi≠vj인 서로 다른 무순서 쌍(vi, vj)들의 최대수 nC2로서 n(n-1)/2이 됨 n개의 정점을 갖는 방향 그래프에서 vi≠vj 인 서로 다른 순서쌍<vi, vj>들의 최대 수 nP2로서 n(n-1)이 됨 완전 그래프(complete graph) 정점의 수가 n인 무방향 그래프의 에지 수가 n(n-1)/2와 같은 그래프

67 기본 경로(elementary path)
그래프(계속) 그래프의 경로(path) 그래프에서 에지들을 이용하여 어느 정점에서 다른 정점으로 이르는 길 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 즉, 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 경로 길이(path length) 경로 상의 에지들의 수 단순 경로(simple path) 하나의 경로 상에 있는 모든 정점들이 서로 다를 경우 기본 경로(elementary path) 하나의 경로 상에 있는 모든 에지들이 서로 다를 경우

68 사이클이 있는 방향 그래프 정점 2에서 출발하여 정점 4에서 끝나는 경로 그래프(계속) P1=<2, 4>

69 사이클(cycle) 그래프(계속) 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은
그래프 G1에서 단순경로 A-B-C-D-A와 그래프 G4에서 단순경로 A-B-A는 사이클이 된다 하나의 경로 상에 있는 모든 정점들이 서로 다를 경우

70 방향 그래프에서의 진입차수(in-degree) 방향 그래프에서의 진출차수(out-degree)
그래프(계속) 방향 그래프에서의 진입차수(in-degree) 주어진 정점으로 향한 에지의 개수 방향 그래프에서의 진출차수(out-degree) 주어진 정점에서 나가는 에지의 개수 그래프 G’가 있을 때 V(G’)∈V(G)이고, E(G’) ∈E(G)이면 그래프 G’는 그래프의 부분그래프 (ex)

71 연결 그래프(connected graph)
그래프(계속) 연결 그래프(connected graph) 무방향 그래프에서 서로 다른 모든 쌍의 정점들 사이에 경로가 있을 경우 비사이클 그래프(acyclic graph) 트리(tree) 사이클이 없는 그래프 대그(DAG, Directed Acyclic Graph) 방향이 있는 비사이클 그래프

72 순회(traversal) 그래프의 각 정점을 한 번씩만 방문하는 것 그래프의 순회
하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 그래프 순회, 예) 우물 파기 한 지점을 골라서 팔 수 있을 때까지 계속해서 깊게 파다가 아무리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라서 다시 깊게 땅을 파는 방법 ( ☞ 깊이 우선 탐색 ) 여러 지점을 고르게 파보고 물이 나오지 않으면, 파놓은 구덩이들을 다시 좀더 깊게 파는 방법 ( ☞ 너비 우선 탐색 )

73 깊이 우선 탐색(DFS, Depth First Search)
그래프의 순회 깊이 우선 탐색(DFS, Depth First Search) 주어진 정점 v를 출발점으로 하여 이를 방문 다음 v에 인접하고 아직 방문하지 않은 정점 w를 선택하여 w를 출발점으로 해서 다시 깊이 우선 탐색을 시작 이것을 모든 정점이 한 번씩 방문될 때까지 반복 인접한 모든 정점이 이미 방문한 정점 v인 경우는 가장 최근에 방문했던 정점 중에서, 방문하지 않은 정점 w를 가진 정점을 선택하여 정점 w로 부터 다시 깊이 우선 탐색을 시작

74 너비 우선 탐색(BFS, Breadth First Search)
그래프의 순회(계속) 너비 우선 탐색(BFS, Breadth First Search) 주어진 정점 v를 출발점으로 하여 이를 방문 v에 인접한 정점 w들을 먼저 모두 방문하고 그 다음으로 w에 인접하고 아직 방문하지 않은 정점들을 모두 방문 이 과정을 반복하여 더 이상 방문할 노드가 없을 때까지 계속하여 방문

75 탐색을 위한 그래프 그래프의 순회(계속) 깊이우선:1,2,4,8,5,6,3,7 너비우선:1,2,3,4,5,6,7,8
깊이우선:1,2,4,8,5,7,3,6 1,3,6,7,8,2,5,4 너비우선:1,2,4,3,4,5,6,7,8 1,3,2,6,5,4,7,8

76 그래프 G의 에지의 일부 또는 전부와 모든 정점을 포함하는 트리
신장 트리(spanning tree) 그래프 G의 에지의 일부 또는 전부와 모든 정점을 포함하는 트리 그래프 G의 최소 부분 그래프 G의 부분 그래프 중 에지의 수가 가장 적은 것 깊이 우선 신장 트리(depth first spanning tree) 깊이 우선 탐색 알고리즘을 이용하여 만들어진 신장 트리 너비 우선 신장 트리(breadth first spanning tree) 너비 우선 탐색 알고리즘을 이용하여 만들어진 신장 트리

77 신장 트리(spanning tree)(계속)
그래프와 신장 트리

78 신장 트리(spanning tree)(계속)
깊이 우선 신장 트리와 너비 우선 신장 트리

79 최소 비용 신장 트리(minimum cost spanning tree)
프림(Prim), 크루스컬(Kruskal) 및 솔린(Sollin) 알고리즘 프림 알고리즘 최소 비용을 갖는 에지(u, v)를 선택하여 이 에지를 최소 비용 신장 트리 T에 포함시킴 정점 u 또는 v에 연결된 에지 중에서 최소 비용을 갖는 에지 (u, w) 또는 (v, w)를 선택하여 T에 포함시킴 정점 u, v, w와 연결된 에지 중에서 같은 방법으로 최소 비용을 갖는 에지를 선택하여 만약 이 에지가 최소 비용 트리 T에 포함시켰을 때 사이클을 형성하지 않는다면 이 에지를 T에 포함시킴 같은 방법으로 T가 n-1개 에지를 갖거나 에지가 모두 소모될 때까지 반복

80 최소 비용 신장 트리(minimum cost spanning tree)(계속)
최소 비용 신장 트리의 생성 과정

81 최소 비용 신장 트리(minimum cost spanning tree)(계속)
최소 비용 신장 트리의 생성 과정(계속)

82 주어진 데이터를 정해진 순서에 따라 재배열하는 연산(operation)
Section 7. 정렬(sorting) 주어진 데이터를 정해진 순서에 따라 재배열하는 연산(operation) 2개 이상의 자료를 작은 것부터 큰 것 순서의 오름차순(ascending)이나 큰 것부터 작은 것 순서의 내림차순(descending)으로 재배열하는 것 키 자료를 정렬하는데 사용하는 기준이 되는 특정 값 데이터를 정렬하는 방법 내부 정렬(internal sort) 파일 크기가 크지 않아서 주기억장치 내에서 정렬이 이루어지는 방법 삽입, 선택, 버블, 셀, 콤, 퀵, 합병, 힙, 리스트, 트리, 테이블, 기수 정렬 등 외부 정렬(external sort) 파일이 커서 디스크와 같은 보조기억장치를 이용하여 정렬하는 방법 우선적으로 내부 정렬 방법으로 정렬된 여러 개의 파일을 합병함으로써 전체적으로 정렬된 파일을 생성

83 삽입 정렬(insertion sort) 맨 처음 하나의 레코드가 정렬되어 있는 것으로 가정하여 정렬되지 않은 리스트의 레코드들을 하나씩 순서에 맞게 제 위치를 찾아주는 방식으로 정렬하는 방법 n=6이고 입력 데이터 ( ) 초기상태: [] i = 1: [5 ] i = 2: [3 5 ] i = 3: [1 3 5 ] 9 7 6 i = 4: [ ] 7 6 i = 5: [ ] 6 i = 6: [ ]

84 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법 정렬할 자료를 두 개의 부분집합 S와 U로 가정
삽입 정렬(insertion sort) 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법 정렬할 자료를 두 개의 부분집합 S와 U로 가정 부분집합 S : 정렬된 앞부분의 원소들 부분집합 U : 아직 정렬되지 않은 나머지 원소들 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입 정렬이 완성된다.

85 삽입 정렬(insertion sort) 삽입 정렬 수행 과정 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 삽입 정렬 방법으로 정렬하는 과정을 살펴보자. 초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나머지 원소들은 정렬되지 않은 원소들의 부분 집합 U로 생각한다. S={69}, U={10, 30, 2, 16, 8, 31, 22}

86 삽입 정렬(insertion sort) ① U의 첫 번째 원소 10을 S의 마지막 원소 69와 비교하여 (10 < 69) 이므로 원소 10은 원소 69의 앞자리가 된다. 더 이상 비교할 S의 원소가 없으므로 찾은 위치에 원소 10을 삽입한다. S={10, 69}, U={30, 2, 16, 8, 31, 22}

87 삽입 정렬(insertion sort) ② U의 첫 번째 원소 30을 S의 마지막 원소 69와 비교하여 (30 < 69) 이므로 원소 69의 앞자리 원소 10과 비교한다. (30 > 10) 이므로 원소 10과 69 사이에 삽입한다.  S={10, 30, 69}, U={2, 16, 8, 31, 22}

88 (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데,
삽입 정렬(insertion sort) ③ U의 첫 번째 원소 2를 S의 마지막 원소 69와 비교하여 (2 < 69) 이므로 원소 69의 앞자리 원소 30과 비교하고, (2 < 30) 이므로 다시 그 앞자리 원소 10과 비교하는데,  (2 < 10) 이면서 더 이상 비교할 S의 원소가 없으므로 원소 10의 앞에 삽입한다.  S={2, 10, 30, 69}, U={16, 8, 31, 22}

89 (16 < 30) 이므로 다시 그 앞자리 원소 10과 비교하여,
삽입 정렬(insertion sort) ④ U의 첫 번째 원소 16을 S의 마지막 원소 69와 비교하여 (16 < 69) 이므 로 그 앞자리 원소 30과 비교한다. (16 < 30) 이므로 다시 그 앞자리 원소 10과 비교하여, (16 > 10)이므로 원소 10과 30 사이에 삽입한다.  S={2, 10, 16, 30, 69}, U={8, 31, 22}

90 ⑤ U의 첫 번째 원소 8을 S의 마지막 원소 69와 비교하여 (8 < 69) 이므로 그 앞자리 원소 30과 비교한다.
삽입 정렬(insertion sort) ⑤ U의 첫 번째 원소 8을 S의 마지막 원소 69와 비교하여 (8 < 69) 이므로 그 앞자리 원소 30과 비교한다. (8 < 30) 이므로 그 앞자리 원소 10과 비교하여, (8 < 10) 이므로 다시 그 앞자리 원소 2와 비교하는데, (8 > 2)이므로 원소 2와 10 사이에 삽입한다. S={2, 8, 10, 16, 30, 69}, U={31, 22}

91 삽입 정렬(insertion sort) ⑥ U의 첫 번째 원소 31을 S의 마지막 원소 69와 비교하여 (31 < 69) 이므 로 그 앞자리 원소 30과 비교한다. (31 > 30) 이므로 원소 30과 69 사이에 삽입한다.  S={2, 8, 10, 16, 30, 31, 69}, U={22}

92 (22 < 31) 이므로 그 앞자리 원소 30과 비교하고,
삽입 정렬(insertion sort) ⑦ U의 첫 번째 원소 22를 S의 마지막 원소 69와 비교하여 (22 < 69) 이므 로 그 앞자리 원소 31과 비교한다. (22 < 31) 이므로 그 앞자리 원소 30과 비교하고, (22 < 30) 이므로 다시 그 앞자리 원소 16과 비교하여, (22 > 16) 이므로 원소 16과 30 사이에 삽입한다. S={2, 8, 10, 16, 22, 30, 31, 69}, U={} U가 공집합이 되었으므로 실행을 종료하고 삽입 정렬이 완성된다.

93 삽입 정렬 알고리즘 삽입 정렬(insertion sort) insertionSort(a[],n)
     for (i←1; i<n; i←i+1) {         temp ← a[i];         j ← i;         if (a[j-1]>temp) then move ← true;         else move ← false;         while (move) do {            a[j] ← a[j-1];            j ← j-1;            if (j>0 and a[j-1]>temp) then move ← true;            else move ← false;         }         a[j] ← temp;      } end insertionSort()

94 삽입 정렬 알고리즘 분석 메모리 사용공간 연산 시간 n개의 원소에 대하여 n개의 메모리 사용
삽입 정렬(insertion sort) 삽입 정렬 알고리즘 분석 메모리 사용공간 n개의 원소에 대하여 n개의 메모리 사용 연산 시간 최선의 경우 : 원소들이 이미 정렬되어있어서 비교횟수가 최소인 경우 이미 정렬되어있는 경우에는 바로 앞자리 원소와 한번만 비교한다. 전체 비교횟수 = n-1 시간 복잡도 : O(n) 최악의 경우 : 모든 원소가 역순으로 되어있어서 비교횟수가 최대인 경우 전체 비교횟수 = ⋯ +(n-1) = n(n-1)/2 시간 복잡도 : O(n2) 삽입 정렬의 평균 비교횟수 = n(n-1)/4 평균 시간 복잡도 : O(n2)

95 최선의 경우와 최악의 경우 예 삽입 정렬(insertion sort)
이미 정렬되어있는 원소에서의 삽입정렬 역순으로 정렬되어있는 원소에서의 삽입정렬

96 삽입 정렬 C 프로그램 정렬할 자료 : {69, 10, 30, 2, 16, 8, 31, 22} 실행 결과 >
삽입 정렬(insertion sort) 삽입 정렬 C 프로그램 정렬할 자료 : {69, 10, 30, 2, 16, 8, 31, 22} 실행 결과 >

97 #include <stdio.h>
int size; void insertionSort(int a[],int size) { int i, j, t, temp; printf("\n정렬할 원소 : "); for(t=0; t<size; t++) printf("%d ", a[t]); printf("\n\n<<<<<<<<<< 삽입 정렬 수행 >>>>>>>>>>\n"); for (i=1; i<size; i++) { temp = a[i]; j = i; while ((j>0) && (a[j-1]>temp)) { a[j] = a[j-1]; j = j-1; } a[j] = temp; printf("\n %d 단계 : ", i); for(t=0; t<size; t++) printf("%3d ", a[t]); void main() int list[8]={69, 10, 30, 2, 16, 8, 31, 22}; size = 8; insertionSort(list, size); getchar();

98 선택 정렬(selection sort) 리스트에서 가장 작은 키를 갖는 레코드를 찾아서 첫번째 위치에 있는 레코드와 교환하고, 그 다음 두 번째로 작은 키를 갖는 레코드를 찾아서 두 번째에 있는 레코드와 교환 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 수행 방법 전체 원소 중에서 가장 작은 원소를 찾아서 선택하여 첫 번째 원소와 자리를 교환한다. 그 다음 두 번째로 작은 원소를 찾아 선택하여 두 번째 원소와 자리를 교환한다. 그 다음에는 세 번째로 작은 원소를 찾아서 세 번째 원소와 자리를 교환한다. 이 과정을 반복하면서 정렬을 완성한다. n=6이고 입력 데이터 ( ) 초기상태: i = 1: i = 2: i = 3: i = 4: i = 5: i = 6:

99 선택 정렬(selection sort) 선택 정렬 수행 과정 정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택 정렬 방법으로 정렬하는 과정을 살펴보자. ① 첫 번째 자리를 기준 위치로 정하고, 전체 원소 중에서 가장 작은 원소 2를 선택하여 기준 위치에 있는 원소 69와 자리 교환

100 선택 정렬(selection sort) ② 두 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 8을 선택하여 기준 위치에 있는 원소 10과 자리 교환

101 선택 정렬(selection sort) ③ 세 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 10을 선택하여 기준 위치에 있는 원소 30과 자리 교환

102 선택 정렬(selection sort) ④ 네 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 16을 선택하여 기준 위치에 있는 원소 69와 자리 교환

103 선택 정렬(selection sort) ⑤ 다섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 22를 선택하여 기준 위치에 있는 원소 69와 자리 교환

104 선택 정렬(selection sort) ⑥ 여섯 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 30을 선택하여 기준 위치에 있는 원소 30과 자리 교환 (제자리)

105 선택 정렬(selection sort) ⑦ 일곱 번째 자리를 기준 위치로 정하고, 나머지 원소 중에서 가장 작은 원소 31을 선택하여 기준 위치에 있는 원소 31과 자리 교환. (제자리) 마지막에 남은 원소 69는 전체 원소 중에서 가장 큰 원소로서 이미 마지막 자리에 정렬된 상태이므로 실행을 종료하고 선택 정렬이 완성된다.

106 선택 정렬 알고리즘 selectionSort(a[],n) for (i←1; i<n; i←i+1) {
        a[i], ⋯,a[n-1] 중에서 가장 작은 원소 a[k]를 선택하여,         a[i]와 교환한다.      } end selectionSort()

107 선택 정렬 알고리즘 분석 메모리 사용공간 비교횟수 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n2)이 된다.
선택 정렬(selection sort) 선택 정렬 알고리즘 분석 메모리 사용공간 n개의 원소에 대하여 n개의 메모리 사용 비교횟수 1단계 : 첫 번째 원소를 기준으로 n개의 원소 비교 2단계 : 두 번째 원소를 기준으로 마지막 원소까지 n-1개의 원소 비교 3단계 : 세 번째 원소를 기준으로 마지막 원소까지 n-2개의 원소 비교 i 단계 : i 번째 원소를 기준으로 n-i개의 원소 비교 어떤 경우에서나 비교횟수가 같으므로 시간 복잡도는 O(n2)이 된다.

108 선택 정렬(selection sort) 선택 정렬 C 프로그램 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 선택 정렬 알고리즘을 사용하여 정렬하는 프로그램 실행 결과 >

109 #include <stdio.h>
int size; void SelectionSort(int a[], int size) { int i, j, t, min, temp; printf("\n정렬할 원소 : "); for(t=0; t<size; t++) printf("%d ", a[t]); printf("\n\n<<<<<<<<<< 선택 정렬 수행 >>>>>>>>>>\n"); for (i=0; i<size-1; i++) { min = i; for (j=i+1; j<size; j++) { if (a[j]<a[min]) min = j; } temp = a[i]; a[i] = a[min]; a[min] = temp; printf("\n%d 단계 : ", i+1); for(t=0; t<size; t++) printf("%3d ", a[t]); void main() int list[8]={69, 10, 30, 2, 16, 8, 31, 22}; size = 8; SelectionSort(list, size); getchar();

110 합병 정렬(merge sort) 원래의 리스트를 이등분해서 두 개의 리스트로 분할한 다음, 각 리스트를 정렬한 뒤 이 두 리스트를 합병하여 하나의 정렬된 리스트를 얻는 것 n=8이고 입력 데이터 ( ) 분할된 상태: 별도로 정렬된 상태: i = 1: i = 2: i = 3: i = 4: i = 5: i = 6: i = 6: i = 6:

111 분할 교환 정렬(partition exchanging sort)
퀵 정렬(quick sort) 주어진 입력 리스트를 특정한 키 값보다 작은 값을 갖는 레코드와 큰 값을 갖는 레코드로 분리하여 논리적으로 두 개의 서브리스트로 재배열하고, 각각의 서브리스트에 대해서 순환적으로 다시 퀵 정렬을 적용하여 입력 리스트의 모든 레코드를 정렬하는 방법 호어(C. A. R Hoare)에 의해 개발 평균적인 수행 시간이 가장 짧은 정렬 방법 분할 교환 정렬(partition exchanging sort) 제어키 또는 피벗이라는 키를 정하고 1차로 퀵정렬을 적용하여 제어 키를 중심으로 그 왼쪽에는 작은 값을 오른쪽에는 큰 값을 갖는 레코드를 배열

112 퀵 정렬(quick sort)(계속) 수행되는 순서

113 n=9이고 입력 데이터 (2, 10, 7, 1, 8, 6, 9, 4, 3) Pivot의 위치는 [n/2]로 가정
퀵 정렬(quick sort)(계속) n=9이고 입력 데이터 (2, 10, 7, 1, 8, 6, 9, 4, 3) Pivot의 위치는 [n/2]로 가정

114 퀵 정렬(quick sort)(계속)

115 정렬한 원소의 키 값을 나타내는 숫자의 자릿수(radix)를 기초로 정렬하는 방법
기수 정렬(radix sort) 정렬한 원소의 키 값을 나타내는 숫자의 자릿수(radix)를 기초로 정렬하는 방법 먼저 정렬할 키의 가장 작은 자릿수(least significant digit)를 기준으로 분배하여 정렬 첫번째 패스의 결과를 두 번째로 작은 자릿수를 기준으로 다시 분배하여 정렬 이러한 정렬과정을 키의 제일 큰 자릿수(most significant digit)까지 반복해서 수행하게 되면 최종적인 정렬 결과 얻음 사전식 정렬(lexicographical sort)

116 기수 정렬(radix sort)(계속)

117 기수 정렬(radix sort)(계속)

118 Section 8. 해싱(hashing) 데이터의 신속한 검색을 위해 데이터를 해시 테이블(hash table)이라고 하는 배열에 저장하고 데이터의 키 값을 주면 이를 적절한 해시 함수(hash function)를 이용하여 테이블의 주소로 변환하고, 원하는 데이터를 찾아내는 방법 해시 테이블(hash table) 해시 함수에 의해 참조되는 테이블 데이터가 저장되는 버킷(bucket)들 또는 그 버킷들을 가리키는 포인터들의 배열로 만들어짐 버킷 안에 여러 개의 레코드가 들어갈 때는 각각을 슬롯(slot)이라고 함

119 해싱(hashing)(계속) 키 값, 해시 함수 및 해시 테이블의 관계

120 해시 테이블에서 키 값을 주소로 변환하는 데 사용되는 함수
해시 함수 해시 테이블에서 키 값을 주소로 변환하는 데 사용되는 함수 계산이 빠르고 간단해야 하며 서로 다른 키 값들이 같은 주소를 산출하는 경우가 적어야 함 계산을 해야할 해시 주소를 해시 테이블의 총 개수로 나누어서 그 나머지를 취하는 경우가 많음 충돌을 적게 하려면 해시 테이블의 크기는 소수로 정하는 것이 좋음

121 해시 함수(계속) 나눗셈법 키 값을 정수로 보고 이를 적당한 양의 정수(주로 해시 테이블의 크기)로 나누어서 그 나머지를 취하는 방법으로 가장 간단한 해시 함수 키 값을 k, 나누는 수를 N, 해시 함수를 h라고 하면 h(k)=k mod N N의 값을 선택할 때의 고려 사항 데이터가 할당 될 수 있는 주소 개수가 N이 되므로 자동적으로 결정 N의 값은 충돌 발생의 가능성을 최소화하도록 선정

122 중간 제곱(mid-square)법 키 값을 제곱한 다음 이 값의 중간 부분의 적당한 자릿수를 취하는 방법
해시 함수(계속) 중간 제곱(mid-square)법 키 값을 제곱한 다음 이 값의 중간 부분의 적당한 자릿수를 취하는 방법 해시 테이블의 크기에 따라서 중간 부분의 적당한 자릿수를 선택할 수 있음 비트 단위로 n자릿수를 중간 부분의 자릿수라고 본다면 해시 테이블의 크기는 2n이 됨 (ex) 키 값 k=7632 k2= K2의 값에서 중간부분의 4자릿수를 취한다고 가정 주소는 2474가 됨

123 해시 함수(계속) 폴딩(folding)법 키를 균등한 크기의 부분으로 나누고 이들을 모두 더하거나 배타적 논리합(XOR)을 취함으로써 해당 레코드의 주소를 얻는 방법 4단계 주어진 키 값을 2진수로 변환 이들 2진수를 동일한 크기의 여러 부분으로 나눔 이러한 부분 2진수들 전부에 대해 ADD 또는 XOR 연산 수행 계산된 2진수를 해당 레코드의 주소 값으로 함

124 (ex) 키 값 k=7632 해시 함수 - 폴딩법(계속) 2진수로 표현하면 k=0001110111010000
8비트 단위 2부분으로 나누면 seg1= seg2=

125 기수 변환(radix exchange)법
해시 함수(계속) 기수 변환(radix exchange)법 어떤 진법으로 표현된 키를 다른 진법으로 표현되었다고 간주하고 키를 변환하는 방법 크기가 10000인 해시 테이블에서 키 값이 인 레코드를 저장할 주소 계산 8진법의 키를 11진법으로 표현한 것으로 보고 10진법의 값을 구함 1*115+7*114+2*113+1*112+4*111+5*110=266370 해당 레코드의 주소 값은 6370

126 자릿수 분석(digit analysis)법
해시 함수(계속) 자릿수 분석(digit analysis)법 키가 취할 수 있는 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택하는 방법 각각의 키에 대해 키 값을 구성하는 숫자 중에서 분포가 고르지 못한 숫자를 제거함으로써 주소를 만들어감

127 선형 검색(linear probing)법
충돌 해결 방안 충돌(collision) 해시 테이블에 데이터를 넣을 때 서로 다른 데이터가 같은 주소에 배정되는 것 선형 검색(linear probing)법 해싱에서 나타나는 충돌 현상을 해결하기 위한 방법으로 충돌이 일어난 자리에서 그 다음 버킷들을 차례로 하나씩 검색하여 최초로 나오는 빈 버킷에 그 데이터를 집어넣는 방법 검색 시간이 많이 걸리고 해시 테이블에 레코드 위치가 일정한 키에 의해 집단적으로 모이는 경향 있음 데이터의 삭제에 많은 부담이 따름

128 2차 검색(quadratic probing)법
충돌 해결 방안(계속) 2차 검색(quadratic probing)법 해싱에서 같은 키 값을 가지는 2개의 데이터가 충돌했을 때 이를 해소하는 방법 원래 주소로부터 d제곱(d=1, 2, 3, …)이 되는 거리만큼 떨어진 곳을 차례로 찾아서 최초로 나오는 빈 곳에 해당 레코드를 넣는 방법 계산 매우 간단 레코드들의 위치가 일정한 키를 중심으로 뭉치려는 경향 피할 수 있음 해시 테이블의 모든 버킷이 다 검색되지 않음

129 해시 체이닝(hash chaining)법
충돌 해결 방안(계속) 해시 체이닝(hash chaining)법 해시 테이블에서 서로 다른 키 값을 가지는 데이터가 해시 함수에 의해 같은 버킷에 배정되는 충돌이 발생했을 때 포인터를 이용하여 같은 해시 함수 값을 갖는 레코드들을 연결리스트로 연결하는 방법

130 충돌 해결 방안 – 해시 체이닝법(계속) 26개의 버킷을 갖는 해시 테이블 선형 검색(linear probing)법

131 충돌 해결 방안 – 해시 체이닝법(계속) 해시 체인

132 Thank you