 12장

(1)

 12장

알고리즘을 통한 문제해결

(2)

• 알고리즘의 특성

• 입력(input) 문제를 풀기 위한 입력이 있어야 함(내부 입력이라도 있어야 함)

• 출력(output) : 문제를 해결한 결과가 생성되어야 함

• 유한성(finiteness) : 유한 번의 명령이 실행되고 난 후에는 실행이 종료되어야 함

• 정확성(correctness) : 주어진 문제를 올바르게 해결해야 함

• 확정성(definiteness) : 일정한 단계가 실행되고 난 후에는 결과가 확정되어야 함

• 일반성(generality) : 같은 유형의 문제에 모두 적용할 수 있어야 함

• 효율성(effectiveness) : 문제 해결을 위한 여러 방법론 중 가장 효 율적인 방법이어야 함

• 알고리즘 표현 방법

• 순서도(flow chart), 유사 코드(pseudo code), 프로그래밍 언어 (programming language) 등

1. 알고리즘이란 무엇인가?

알고리즘

(3)

• 알고리즘의 효율성을 결정하는 두 가지 중요 요인

• 실행 속도

• 메모리 요구량

2. 알고리즘의 효율성

알고리즘의 효율성

(4)

• 알고리즘의 효율성 분석

• 효율성 분석의 핵심

• 알고리즘이 수행되는데 필요한 비용의 최소화

• 비용이란 금전적 비용을 의미하는 것이 아니라 주로 알고리즘 이 수행되는데 소요되는 시간과 메모리 요구량을 의미함

• 시간 복잡성(time complexity) : 알고리즘이 실행되는데 소요되는 시간이 얼마나 짧은가?

• 프로그램이 실행되는 하드웨어의 성능에 따라 다르기 때문에 합리적인 판단 도구가 있어야 함

• 일반적으로 알고리즘이 처리하는 데이터의 수를 n으로 놓고 n 에 대한 함수를 분석함으로써 효율성을 분석함

• 공간 복잡성(space complexity) : 알고리즘이 실행되는데 소요되 는 메모리 용량이 얼마나 적은가?

• 메모리 용량의 크기가 계속해서 커지고 있기 때문에 최근에는 큰 의미를 두지 않는 경향도 있음

3. 알고리즘 분석

효율성 분석

(5)

• 알고리즘의 효율성 분석 예

• 다음과 같이 n개의 양의 정수 중에서 가장 작은 수를 찾는 알고리즘에 서 기억장소의 크기와 수행 회수를 분석해보자.

3. 알고리즘 분석

Find_MIN(int array[], int MIN) {

int i;

MIN=array[0];

for(i=1; i<n; i++)

if(MIN>array[i]) MIN=array[i];

return(MIN);

}

100 300 200 500 400

[0] [1] [2] [3] [4]

array

1. 기억장소의 크기

• 짧은 정수(short integer) 1개를 저장하는 데 2바이트가 필요하다고 가정하면 변수 MIN을 위해 2바이트, 배열 array를 위해 2 바이트ⅹ5=10바이트, 반복문 제어 변수 i 를 위해 2바이트 등 총 14바이트가 필요 함. 일반화하면 2(n+2) 바이트가 필요함 2. 수행 시간

• MIN=array[0]은 1회 수행됨

• return(MIN)은 1회 수행됨

• If(MIN>array[i]는 4회 수행되는데 지금은 데이터가 5개 있었기 때문에 4회이고, 데 이터가 10개 있었다면 9회, 20개 있었다 면 19회 수행되므로 일반화하면 n-1회 수행됨

<n이 5인 경우, 즉 데이터가 5개인 경우>

(6)

3. 알고리즘 분석

• 알고리즘의 효율성 분석 결과에 대한 해석

• 동일한 결과가 얻어지는 2개 이상의 알고리즘이 존재한다면 수행 회 수가 적은 알고리즘이 효율적인 것으로 평가함

• 동일한 알고리즘이라 하더라도 처리되는 데이터의 개수에 따라 수행 회수가 다를 수 있으므로 데이터의 수에 따라 효율적인 알고리즘을 달 리 선택하는 것도 좋은 전략임

(7)

• 알고리즘의 복잡성 분석 도구

• 1892년 독일의 수학자 바흐만이 처음 소개하고, 그 후 린다우가 처 음으로 사용하기 시작한 도구로 빅 오우(Big O) 표기법을 사용하고, 알파벳 대문자 O를 이텔릭체로 표현한

O

뒤에 수행 회수를 넣어 표 기함

• 예 :

O

(n),

O

(n²)

• 빅 오우 표기법은 차수가 다른 항이 여러 개 일 때 차수가 가장 높 은 항만 살리고 나머지 항은 모두 삭제하며, 계수가 있는 경우에는 계수도 삭제함

• 만일 어떤 알고리즘이 처리해야 하는 데이터의 개수가 n개이 고, 특정 명령 수행 회수가 3n³+2n²+1이라면 3차항 이하의 2n²+1은 모두 삭제하고, 최고차 항인 3차항의 계수 3도 삭제한 후 n³만 살려서

O

(n³)이라고 함

• 알고리즘의 복잡도로

O

(n!),

O

(2ⁿ)과 같은 결과가 나온다면 처 리 불능할 정도로 시간이 많이 걸림

4. 알고리즘의 복잡성

알고리즘의 복잡성

(8)

• 데이터의 수에 따른 함수의 증가값(그림 1)

• 데이터의 수 증가에 따른 각 함수의 증가 비율(그림 2)

4. 알고리즘의 복잡성

<그림 1> <그림 2>

(9)

5. 재귀 함수의 복잡성

재귀 함수의 복잡성

int sum(int n) {

if(n!=0) return(1+sum(n-1));

else return(0);

}

1. 재귀 함수 sum은 n이 0인지 아닌지를 if문으로 체크하여 만일 0이 아니면 n의 값을 n-1로 하여 다 시 자신을 호출함. 만일 n이 0이면 0을 반환함 2. f(0)은 단 1개의 문장을 수행하므로 f(0)=1이 되 고, 이를 일반화하면 f(0)=1, f(n)=1+f(n-1), 단 n≥1 임

• f(0)=1, f(1)=f(0)+1=1+1,

f(2)=f(1)+1=1+1+1, f(n)=f(n-1)+1=n+1

∴ O(n)

(10)

• 탐색(search)

• 주어진 데이터 집합에서 원하는 데이터의 존재 유무를 확인하는 과정

• 알고리즘 분석

• 순차 탐색 알고리즘 :

O

(n) 알고리즘

• 데이터가 정렬되어 있지 않은 상태에서 탐색 가능

6. 탐색 알고리즘

탐색

int seq_search(int array[], int search_num, int n) {

int i;

array[n]=search_num;

for(i=0; array[i]!=search_num; i++);

return((i<n)?i:-1);

}

i<n이면 i를 리턴하고, i=n이면 -1을 리턴함

100 300 200 500 400 ^찾으려는

값을 저장

[0] [1] [2] [3] [4]

array

<n이 5인 경우, 즉 데이터가 5개인 경우>

[5]

(11)

• 이진 탐색 알고리즘 :

O

(log₂n) 알고리즘

• 정렬되어 있는 배열의 중간에 위치한 데이터를 첫 번째 비교 대 상으로 삼고, 찾고자 하는 데이터의 값이 그보다 작으면 반대편 절 반을 포기하고 남은 절반을 이용하여 계속 동일한 작업을 반복함

• 전체집합을 반으로 줄여서 결과를 얻어 내는 분할과 정복 기법 (divide & conquer)을 사용함

6. 탐색 알고리즘

int binary_search(int array[], int search_num, int left, int right) {

int middle;

while(left≤right) {

middle=(left+right)/2;

if(array[middle]<search_num) left=middle+1;

elseif(array[middle]>search_num) right=middle-1;

else

return(middle);

}

return(-1);

}

(12)

6. 탐색 알고리즘

1 2 8 9 11 19 29

• 11을 검색하는 경우

1 2 8 9 11 19 29

① 11>9

1 2 8 9 11 19 29

② 11<19

1 2 8 9 11 19 29

③ 11=11

리스트의 중간에 있는 기준 값(9)보다 11이 크므로 리스트의 왼쪽 반을 버리고 오른쪽 반으로 계속 검 색

오른쪽 리스트의 중간에 있는 기준 값(19)보다 11이 작으므로 리스트의 오른쪽 반을 버리고 왼쪽 반으로 계속 검색

왼쪽 리스트의 중간에 있는 기준 값(11)과 11이 같 으므로 검색 종료

[0] [1] [2] [3] [4] [5] [6]

(13)

• 이진 탐색 트리(Binary Search Tree : BST)

• 다음과 같은 조건을 만족하는 이진 트리

• 모든 원소의 키(key)는 유일하다.

• 왼쪽 서브 트리의 키들은 루트의 키보다 작다.

• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.

• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

A

< <

left subtree (루트보다 작은 값)

right subtree (루트보다 큰 값)

18 7

3 26 12

27

31

6. 탐색 알고리즘

(14)

• 이진 탐색 트리에서의 탐색

• 루트와 제일 먼저 비교

• 탐색값과 루트가 일치하면 탐색 종료

• 탐색값이 루트보다 작으면 왼쪽 서브 트리로 이동하여 왼 쪽 서브 트리의 루트와 다시 비교

• 탐색값이 루트보다 크면 오른쪽 서브 트리로 이동하여 오 른쪽 서브 트리의 루트와 다시 비교

searchBST(bsT,x) p←bsT;

if(p=null) then return null;

if(x=p.key) then return p;

if(x<p.key) then

return searchBST(p.left,x);

else return searchBST(p.right,x);

end searchBST()

순환함수에 의한 이진 탐색 트리의 탐색

6. 탐색 알고리즘

(15)

• 정렬(sort)

• 데이터들을 일련의 순서로 늘어놓는 것

• 내부 정렬(internal sort) : 정렬할 데이터가 주기억장치에 있는 경우

• 외부 정렬(external sort) : 정렬할 데이터가 주기억장치와 보조기억 장치에 분산 저장된 경우

• 알고리즘 분석

• 버블 정렬(bubble sort) 알고리즘 :

O

(n²) 알고리즘

7. 정렬 알고리즘

정렬

void bubble_sort(int array[], int n) {

int i, j, temp;

for(i=0; i<n-1; i++) for(j=0; j<n-1;j++)

if(array[j]>array[j+1]) { temp=array[j];

array[j]=array[j+1];

array[j+1]=temp;

} }

(16)

• 버블 정렬(bubble sort)이란?

• 인접한 2개의 데이터를 비교하여 자리를 교환하는 방식으로 첫 번 째 데이터부터 마지막 데이터까지 반복하면 가장 큰 데이터가 마지막 자리에 오게 됨

버블 정렬의 이해

69 10 30 2 16 8 31 22 10 30 2 16 8 31 22 69

10 2 16 8 30 22 31 69 2 10 8 16 22 30 31 69

Original List

[0] [1] [2] [3] [4] [5] [6] [7]

7. 정렬 알고리즘

(17)

2 8 10 16 22 30 31 69 2 8 10 16 22 30 31 69

2 8 10 16 22 30 31 69

Final List

[0] [1] [2] [3] [4] [5] [6] [7]