알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.

Presentation on theme: "알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도."— Presentation transcript:

1 알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도

2 알고리즘의 개념을 익히고 의사코드로 표현한다.
데이터를 정렬시켜주는 정렬 알고리즘들에 대해 이해한다. 원하는 키를 탐색하는 탐색 알고리즘의 다양한 방법을 익힌다. 알고리즘을 검증하고 적합한 알고리즘을 선택할 수 있다. 알고리즘 복잡도를 이해하고 계산할 수 있다.

3 알고리즘(Algorithm) 주어진 문제를 해결하기 위한 일련의 절차 알고리즘 개발 조건 입력(input) 출력(output)
정확성(correctness) 유한성(finiteness) 일반성(generality)

4

5

6

7

8 유클리드 알고리즘(Euclidean algorithm)

9

10

11 정렬(sorting) 데이터의 저장 위치에 따라 내부정렬(internal sort) 방식
주기억장치 내에서 이루어지는 정렬 방식 버블정렬 선택정렬 퀵정렬 외부정렬(external sort) 방식 외부정렬은 보조기억장치를 이용하는 방식

12 버블정렬(bubble sort) 방식 배열 A에서 인접한 두 데이터 A[i]와 A[i+1]을 비교하여 A[i+1]이 A[i] 보다 작다면 두 데이터를 서로 교환하여 주면서 큰 데이터가 배열의 끝에 오도록 정렬 데이터의 양이 늘어날수록 느리고 비효율적인 방식 [그림 10-1] 버블정렬 수행 전의 데이터

13 버블정렬 1단계 [그림 10-2] 버블정렬 1단계 완료

14 버블정렬 2단계 [그림 10-3] 버블정렬 2단계 완료

15 버블정렬 완성 [그림 10-4] 버블정렬 완성

16 버블정렬 알고리즘

17 선택정렬(selection sort) 방식
데이터에서 제일 큰 값이나 제일 작은 값을 찾은 후에 그 값만을 단계적으로 교환하여 정렬을 이뤄나가는 방식 선택정렬 과정 n 개의 데이터 값들 중에서 가장 큰 값을 찾음 그 값이 A[j]에 있다면 A[j]와 A[n-1]번째 값을 서로 교환 가장 큰 값을 배열의 맨 마지막 A[n-1]에 정렬 맨 마지막 원소 A[n-1]를 제외한 나머지 값들로 같은 과정을 반복 실행

18 선택정렬 예제 선택정렬 1단계 완성 [그림 10-5] 선택정렬 전 데이터 [그림 10-6] 선택정렬 1단계 완성

19 선택 정렬 완성 [그림 10-7] 선택정렬 완성

20 선택 정렬 알고리즘

21 삽입정렬(insertion sort) 방식
새로운 데이터를 정렬된 데이터에 삽입해 나가는 과정을 반복하여 전체 데이터를 정렬하는 방식 삽입정렬 과정 n 개의 데이터 정렬시 처음의 A[0]는 정렬된 데이터로 취급 다음 데이터 A[1]을 정렬된 데이터와 비교하여 적절한 위치에 삽입 다음 데이터 A[2]를 정렬된 데이터 A[0], A[1]과 비교하여 적절한 위치에 삽입 같은 방식으로 나머지 데이터들을 삽입하여 정렬을 완성

22 삽입 정렬 예제 A[2] 원소의 삽입 정렬 [그림 10-8] 삽입정렬 전 데이터 [그림 10-9] A[2] 원소의 삽입정렬

23 A[3] 원소의 삽입 정렬 [그림 10-10] A[3] 원소의 삽입정렬

24 삽입 정렬 완성 [그림 10-11] 삽입정렬 완성

25 삽입 정렬 알고리즘

26 삽입 정렬 알고리즘(계속)

27 퀵정렬(quick sort) 방식 퀵정렬 과정 특정한 데이터 피봇(pivot) 기준
전체 원소를 피봇 보다 작은 원소들과 피봇 보다 큰 원소들의 집합으로 분류 분류된 각각의 집합에서 다시 피봇을 설정 같은 과정을 반복하여 집합을 정렬

28 퀵 정렬 예제 [그림 10-13] 퀵정렬을 수행하기 전 데이터 피봇과 키 설정 [그림 10-14] 퀵정렬에서 피봇과 키 설정

29 처음 키 값의 교환 처음 피봇 7에 대해 L 과 R 이 가리키는 값을 찾음
L = A[1] = 8 R = A[6] = 2 L 이 가리키는 값과 R 이 가리키는 값을 서로 교환 [그림 10-15] 처음 키 값의 교환

30 퀵 정렬 1단계 완성 [그림 10-16] 피봇 7을 기준으로 퀵정렬 1단계 완성

31 [그림 10-17] 피봇 5를 기준으로 하여 퀵정렬 2단계 완성
퀵 정렬 2단계 완성 [그림 10-17] 피봇 5를 기준으로 하여 퀵정렬 2단계 완성

32 퀵 정렬 완성 [그림 10-18] 퀵정렬 완성

33 합병정렬(merge sort) 방식 합병정렬 과정 정렬하고자 하는 데이터의 모임을 비슷한 크기의 두 부분으로 반복해서 나눔
나뉘어진 부분 데이터들을 합병정렬 알고리즘을 이용하여 정렬 정렬된 부분 데이터들을 다시 합병 하나의 정렬된 데이터 모임으로 완성

34 합병 정렬 예제 [그림 10-19] 합병정렬 전 데이터 합병 정렬의 분할 과정 [그림 10-20] 합병정렬의 분할

35 합병 정렬 완성 [그림 10-21] 합병정렬된 데이터

36 합병 정렬 알고리즘

37 탐색(search) 데이터가 가지고 있는 특정한 키(key)를 찾는 작업 데이터는 레코드(record) 형태로 구성
레코드 : 특정한 필드들의 모임 필드(field) : 데이터가 가지고 있는 특정한 값들을 의미 키(key) : 각 데이터를 구분해주는 고유한 필드

38 선형탐색(linear search) 방식
이해하기 쉽고 간단한 탐색 알고리즘 순차탐색(sequential search)이라고도 함 선형탐색은 주어진 데이터의 조작없이 순서대로 데이터를 탐색하는 방법

39 선형 탐색 알고리즘

40 이진탐색(binary search) 방식
정렬되어 있는 데이터에서 원하는 값을 찾을 때 효과적인 탐색 방법 정렬된 데이터의 중간 값을 찾는 값과 비교하여 그 값이 작은 쪽에 속하는지 큰 쪽에 속하는지를 판단하면서 원하는 값을 찾는 탐색 방법

41

42

43 이진탐색트리(binary search tree) 방식
데이터의 탐색뿐만 아니라 삽입과 삭제도 편리하게 진행할 수 있는 방식 이진탐색트리는 정렬된 데이터뿐만 아니라 정렬되지 않은 데이터도 트리 형태로 구현하여 이진탐색으로 원하는 값을 탐색 탐색을 위해 데이터를 트리 형태로 구현

44 이진 탐색 트리 예제 이진 탐색 트리 완성 [그림 10-26] 이진탐색트리로 나타낼 데이터
[그림 10-27] 이진탐색트리 완성

45 이진탐색트리에서의 탐색 [그림 10-28] 이진탐색트리의 탐색

46 알고리즘 복잡도(complexities of algorithm)
알고리즘이 수행되는 데 필요한 시간과 공간을 측정하는 작업 알고리즘이 실행되는 데 필요한 시간과 기억장소의 양을 측정하는 작업 알고리즘을 보고 분석하여 판단하는 계산 값 Big-Oh 표기법 알고리즘 복잡도를 대문자 O를 사용하여 표기

47 Big-Oh 표기법 f 와 g 를 음수 값을 갖지 않는 함수라 하자.
이때 n≥n0인 모든 자연수 n에 대하여 f(n)≤c·g(n)가 되는 양의 상수 c와 n0가 존재하면 f(n) = O(g(n))이라고 한다.

48

49 다양한 복잡도 함수들 [표 10-2] 다양한 복잡도 함수들

50

51

52

53