Algorithms

by Kwang-Soo Hahn, kshahn@kmu.kookmin.ac.kr
Dept. of Computer Science, Kookmin University
910-4794, http://kshahn.kookmin.ac.kr

Objectives

대표적인 알고리즘 예를 통하여 알고리즘 개발 절차를 공부한다.
대부분의 문제들은 여러 다른 알고리즘으로 해결 가능함을 인식한다.
알고리즘의 효율성에 관한 개념을 이해한다.
알고리즘의 오류 검사에 대해 공부한다.

Algorithm: 문제 해결을 위한 체계적인 절차로 다음 특성을 지녀야 한다.

둘 이상의 의미로 해석 가능하지 않도록 명확하게 정의되어야 한다. (clear and unambiguous)
실행 가능한 유한 개의 단계들로 구성되어야 한다. (finite executable steps)
유한 개의 실행 단계를 거치면 궁극적으로 문제의 해에 도달해야 한다. (correct)

예 1) 어떤 수 n이 prime number (소수: 1과 그 자신으로만 나누어지는 양의 정수) 인지 아닌지 검사하는 알고리즘

알고리즘 1)

1과 n 사이의 모든 수를 선택하여 그 수가 n을 나머지 없이 나눌 수 있나 검사한다.
n을 나눌 수 있는 수가 발견될 때마다 count를 1 증가시킨다.
모든 수 검사 결과 count가 2이면 n은 prime number

bool IsPrime(int n)
{
    int divisors, i;

    divisors = 0;
    for (i = 1; i <= n; i++) {
        if (n % i == 0) divisors++;
    }
    return (divisors == 2);
}

위 알고리즘은 명확하고, 정확하고, 효율적인가?

명확성: 인간이 사용하는 언어는 많은 경우 둘 이상의 의미로 해석될 여지가 있으므로 알고리즘 표현 수단으로는 부적합하다. 프로그래밍 언어는 명확한 표현 수단이며 둘 이상의 의미로 해석될 여지가 없다.

정확성: 프로그램의 정확성검사는 일반적으로 다음 두 방법을 많이 사용한다.

프로그램 코드를 한 줄 한 줄 철저히 살펴가며 오류가 있는지 검사한다. (Desk-checking)
프로그램에 특정 자료들을 입력하여 그 자료들에 대한 처리 결과가 정확한지 검사한다. (Testing)

위의 두 방법도 프로그램의 정확성에 대한 신뢰도를 높여줄 뿐 완벽한 프로그램 오류 검사 방법은 없다.

위 알고리즘을 1에서 1000 까지의 데이타로 시험한 결과는 정확함을 알 수 있다.

효율성: 위 알고리즘을 사용하여 1000이 prime number 인지 검사하려면 1 부터 1000 사이의 수를 모두 검사하여 1000을 나눌 수 있는지 검사하여야 한다. (1000000이 prime number인지 검사할 경우는?) 그러나 2로 1000을 나누어 떨어짐을 알 때 1000이 prime number가 아님을 바로 알 수 있다. 그러므로 위 알고리즘 보다 더 효율적인 알고리즘이 존재함을 알 수 있다.

위 알고리즘의 개선 방안

n이 prime number인지 검사하기 위해 1에서 n 사이의 모든 수로 n을 나누어볼 필요는 없다. 1과 n 이외의 수로 n이 나누어 지면 n은 prime number가 아니다.
만일 n이 2로 나누어지지 않으면 2의 배수로도 나누어지지 않는다. 이 경우 홀수만 검사하면 된다.
n은 n/2 보다 큰 수로는 나누어지지 않는다. 그러므로 n/2 보다 작은 수만 검사한다. (좀 더 생각하면 n의 제곱근 보다 큰 수로는 나누어지지 않음을 알 수 있을 것이다.)

위의 개선 방안을 고려한 새로운 알고리즘

bool IsPrime(int n)
{
   int  i;

   if (n % 2 == 0) return (FALSE);   // n이 2로 나누어지면 n은 prime number가 아님
   for (i = 3; i <= sqrt(n); i += 2) {   // 3 부터 n의 제곱근까지 홀수만 검사
      if (n % i == 0) return (FALSE);
   }
   return (TRUE);   // 위의 경우로 나누어지지 않으면 n은 prime number?
}

위 프로그램은 정확하고 효율적인가?

2는 정의에 의해 prime number. 그러나 위 프로그램은 n이 2일 경우 FALSE를 return.
1은 prime number가 아님.
sqrt(n)은 한번만 계산하면 되나 위 프로그램은 for-loop 내에서 반복 계산한다.
sqrt(n) 같은 실수 연산은 오차가 있을 수 있다. (49의 제곱근은 계산 결과 7이 아닐 수 있다)

최종 프로그램

bool  IsPrime(int n)
{
   int  i, limit;

   if (n <= 1)  return (FALSE);
   if (n == 2)  return (TRUE);
   if (n % 2 == 0)  return (FALSE);
   limit = sqrt(n) + 1;
   for (i = 3; i <= limit; i += 2) {
      if (n % i == 0)  return (FALSE);
   }
   return (TRUE);
}

위 알고리즘과 첫번째 알고리즘의 차이는? (알고리즘 분석)

두 알고리즘의 장단점은? (알고리즘의 비교, Tradeoffs)

어떤 알고리즘을 선택할 것인가? (알고리즘 선택 기준)

예 2) 두 양의 정수 x, y 사이의 최대공약수 (Greatest Common Divisor; GCD)를 구하는 알고리즘

알고리즘 1) Brute-force algorithm

알고리즘 2) Euclid's algorithm

제곱근, 삼각함수, 지수함수, log함수, 미적분 방정식, 연립방정식 등을 계산하는 알고리즘이 존재하거나 library function으로 제공된다. (수치 해석; Numerical analysis)

Searching and Sorting

Searching: Array에서 특정 요소를 찾는 작업

Sorting: Array에 저장된 값을 특정 순서에 따라 정렬시키는 작업

Searching

특정 값(key)을 갖는 array element를 찾는 문제

예) 특정 값에 해당하는 미국 동전 이름 찾기 (findcoin.c)

값 (cent) 동전 이름

1 penny

5 nickel

10 dime

25 quarter

50 half-dollar

Searching algorithm

Linear search: Array element 값을 처음부터 끝까지 key 값이 발견될 때까지 비교. 평균적으로 N/2번의 비교가 필요하다.
Binary search: Array에 저장된 값들의 중간 값과 key 값을 비교하여 그 결과에 따라 array의 전반부 혹은 후반부로 찾는 범위를 좁혀가는 알고리즘. Array가 정렬되어 있어야 적용 가능하며 평균 log₂N 번의 비교가 필요하다.

Sorting

Array에 저장된 값을 특정 순서(보통 작은 값에서 큰 값, 또는 큰 값에서 작은 값)에 따라 정렬

Sorting algorithm (작은 값에서 큰 값 순으로; ascending order)

Selection sort (sort.h, sort.c)

전체 array에서 제일 작은 값을 찾아 첫번째에 저장
두번째에서 마지막까지의 배열 값중 제일 작은 값을 찾아 두번째에 저장
...
N-1번째에서 마지막까지의 배열 값중 제일 작은 값을 찾아 N-1번째에 저장

Bubble sort

배열 처음부터 끝까지 인접한 요소 값들을 비교하여 앞의 값이 뒤의 값보다 크면 서로 교환 (swap)
배열 처음부터 N-1까지 인접한 요소 값들을 비교하여 앞의 값이 뒤의 값보다 크면 서로 교환
...
배열 첫번째 값과 두번째 값을 비교하여 첫번째 값이 두번째 값보다 크면 서로 교환

Quick sort, shell sort, heap sort, ...

실습 1) Prime number, GCD algorithm 구현

실습 2) 배열에 저장된 값을 크기순으로 정렬하는 프로그램 작성

Insertion sort 방법 사용: (isort.c, tabins.c)

값 (cent)	동전 이름
1	penny
5	nickel
10	dime
25	quarter
50	half-dollar