1.1 Algorithms
Text Book: Foundations of Algorithms - Richard E. Neapolitan
An algorithm is a self-contained step-by-step set of operations to be performed
알고리즘은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 풀기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉, 문제풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램 명령어의 집합을 의미하기도 한다.
알고리즘을 만드는 이유는 유한한 컴퓨터 자원과 시간을 효율적으로 사용하기 위함이다.
알고리즘 과목에서 주로 하는 것은 1. Design, 2. Analysis, 3. Computational Complexity (계산 복잡도)를 구하는 것이다.
알고리즘의 예)
- 문제: 전화번호부에서 "홍길동" 찾기
- 알고리즘:
- 순차검색: 홍길동을 첫 쪽부터 검색해 나올 때까지 반복
- 수정된 이분검색: 전화번호부는 "ㄱㄴㄷ" 순서로 되어있고 "ㅎ"은 뒤에 있으므로 넘겨본 후 앞뒤로 찾는다.
- 분석: 어떤 알고리즘이 좋은가?: 만약 전화번호부에 '홍'씨만 있을 경우에는 "홍길동"은 홍 씨 중 앞에 있으므로 순차 검색이 좋다. 따라서 데이터의 특성에 따라 적절한 알고리즘을 취사선택해야 한다.
1.2 The Importance of Developing Efficient Algorithms
효율적인 알고리즘을 비교하기 위해 2개의 알고리즘을 비교함으로써 알고리즘의 중요성을 파악해보자.
이 교재에서 사용한 언어는 pseudo code 이므로 인덱스가 1부터 시작한다. 그리고 C++에 유사한 의사 코드를 사용한다. 의사 코드를 사용하는 이유는 언어간의 종속성을 없애기 위함이다.
■ Sequential Search vs Binary Search
- Sequential Search
- 문제: n개의 수로 된 리스트 S에 x라는 수가 있는가?
- 입력(parameters): S, 양수 n, x (target)
- 출력: location (없으면 0)
void seqSearch(int n, const keytype S[], keytype x, index& location)
{
location = 1;
while (location <= n && S[location] != x)
location++;
if (location > n)
location = 0;
}Sequential Search (순차 검색)은 배열의 크기 대로 연산 순위가 그대로 늘어난다. 예를 들어 배열의 크기가 n이면 순차 검색도 n번 하게 된다.
- Binary Search
- 문제: n개의 수로 된 "정렬된" 리스트 S에 x라는 수가 있는가?
- 입력(parameters): S, 양수 n, x (target)
- 출력: location (없으면 0)
void binSearch(int n, const keytype s[], keytype x, index& location)
{
index low, high, mid;
low = 1; high = n;
location = 0;
while (low <= high && location == 0)
{
mid = (low + high) / 2;
if (x == S[mid])
location = mid;
else if (x < S[mid])
high = mid - 1;
else
low = mid + 1;
}
}while 문을 수행할 때 마다 검색하는 대상의 사이즈가 반씩 줄어들어서 약 log n 번만 검사하면 된다.
Sequential Search (순차 검색)와 Binary Search (이분 검색)를 비교하면 아래와 같다.
순차 검색은 자료형의 크기에 따라 그대로 검색을 해야 하는데 이분 검색은 약 log n만큼 줄어들어 연산 횟수가 적다.
■ 피보나치의 recursive (재귀) vs 반복적 방법
- 문제: n번째 피보나치 수를 구하라 (재귀)
- 입력: 양수 n
- 출력: n번째 피보나치 수
int fib(int n)
{
if (n <= 1)
return n;
else
return fib(n-1) + fib(n-2);
}재귀 알고리즘은 수행속도가 매우 느린데, 이유는 같은 피보나치 수를 중복해서 계산하기 때문이다.
당장 fib(4)를 계산하기 위해 오른쪽 하단 fib(4)가 또 실행되고 마찬가지로 fib(3)도 중복실행... 많은 중복 실행을 볼 수 있다. 그리고 함수 실행 의 모습을 보면 삼각형 모양이 아니라 어느 한쪽으로 치우쳐진 삼각형 모양이다.
fib(n) 함수의 호출 횟수를 계산해 보겠다.
T(n) = fib(n)을 계산하기 위하여 fib 함수를 호출하는 횟수이다. 즉, 재귀 트리 상의 마디(node)의 개수를 의미한다.
T(n)은 T(n-1)와 T(n-2)의 문제로 나뉘고 덧셈을 한번 진행하기 때문에 1을 더해줬다. T(n-1) + T(n-2) + 1는
반드시 2 * T(n-2)보다 크다. 이렇게 전개해가다 보면 2^n/2가 나온다. 이 계산은 추정을 한 계산이므로 반드시 증명이 필요하다.
증명 방법은 Induction(귀납법)을 사용한다. Induction도 그냥 Induction과 Strong Induction으로 나뉜다.
fibonacci 같은 경우에는 T(n) = T(n-1) + T(n-2) + 1 인데, sub problem이 다르기 때문에 storng Induction을 사용한다.
- 정리: 재귀 알고리즘으로 구성한 재귀 트리의 마디의 수를 T(n)이라고 하면, n >= 2인 모든 n에 대해서 T(n) > 2^n/2이다.
- 증명: n에 대해 strong induction으로 증명
1.3 Analysis of Algorithms
1.4 Order
