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

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

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

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

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

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

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

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

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

버블정렬 알고리즘

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

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

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

선택 정렬 알고리즘

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

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

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

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

삽입 정렬 알고리즘

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

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

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

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

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

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

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

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

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

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

합병 정렬 알고리즘

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

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

선형 탐색 알고리즘

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

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

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

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

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

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

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