Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

컴퓨터 공학에서의 추상 자료형(Abstract Data Type)

ADT라고도 불리는 이것은 컴퓨터 공학에서 흔히 등장하는 용어이다. 그런데 이 용어는 등장하는 영역에 따라서 의미상 약간의 차이가 있는 것처럼 느껴질 수 있다. 실제 의미에서 조금 확장된 개념으로 사용되기도 하기 때문이다. 하지만 실제로 차이를 보이는 것은 아니다. 

추상 자료형이란?

"구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것" 이것을 추상 자료형 또는 ADT라 한다.

'자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시할 수 있다. 따라서 추상 자료형이라 하여 그것에 기능 혹은 연산과 관련된 내용을 명시할 수 없다는 생각은 버려야 한다.

※ 추상 자료형을 명시하는데 있어 특정 언어에 의존적이지 않게 별도의 표기법을 활용하는 것이 좋지만 꼭 그래야 하는 것은 아니다. 명시해야 할 정보인 '기능'을 충분히 묘사하고 있다면 그 방법도 괜찮다.

# 리스트 자료구조의 학습 순서

1. 리스트 자료구조의 ADT를 정의한다.

2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다.

3. ADT를 근거로 리스트를 구현한다.

하노이 타워 문제는 재귀함수의 힘을 보이는 대표적인 예로 꼽힌다.

재귀적으로 접근하지 않으면 해결이 쉽지 않은 문제이다.

하노이 타워의 조건

1. 원반은 한 번에 하나씩만 옮길 수 있다.

2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

하노이 타워는 원반의 수가 늘어나도 해결방법에는 차이가 없다. 다만 원반의 수가 늘어날수록 일련의 과정을 더 많이 반복해야 할 뿐이다.

그래서 그 일련의 과정을 파악하면 해결할 수 있게된다.

원반 n개를 옮기는 과정

1. 작은 원반 n-1개를 A에서 B로 이동.

2. 큰 원반 1개를 A에서 C로 이동.

3. 작은 원반 n-1개를 B에서 C로 이동.

이렇듯 원반 n개를 이동하는 문제는 원반 n-1개를 이동하는 문제로 세분화되고, 또 원반 n-1개를 이동하는 문제는 원반 n-2개를 이동하는 문제로 세분화된다.

즉, 원반 n개를 이동하는 문제는 결국 원반 1개를 이동하는 매우 쉬운 문제로 세분화되는 것이다.

재귀함수를 정의하는데 있어서 반드시 생각해야 할 것은 재귀의 탈출조건이다. 

그런데 n개의 원반 이동이 n-1개의 원반 이동으로 세분화되어서 재귀를 구성하게 된 것으므로 탈출의 조건은 다음과 같다. 

"이동해야 할 원반의 수가 1개인 경우"

코드를 보면 너무나 간단해서 허탈한 기분이 든다. 이것이 재귀의 힘...

이진 탐색 알고리즘은 수식적으로 표현하기는 부적절하지만 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.

이진 탐색 알고리즘은 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다. 

때문에 알고리즘 자체는 재귀적인 성격을 지니고 있다. 그래서 재귀적으로 정의가 가능하다. 

# 이진 탐색 알고리즘의 반복 패턴

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인.

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작.

# 재귀 함수의 탈출 조건

"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"

이진 탐색 알고리즘을 성능이 떨어지는 재귀함수 기반으로 구현한 이유.

- 재귀함수에 익숙해지기 위함이다.

- 재귀 함수를 기반으로 구현된 위의 이진 탐색 알고리즘도 자연스럽게 이해할 수 있을 정도가 되어야 한다

재귀함수는 이해하는 것도 중요하지만 잘 정의하는 것도 중요하다. 그리고 재귀함수를 잘 정의하기 위해서는 사고의 전환이 필요하다.

# 피보나치 수열: Fibonacci Sequence

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

피보나치 수열의 n번째 위치의 값을 반환하는 함수는 수학적으로 다음과 같이 표현이 된다.

int Fib(int n)

{

if(n == 1)

return 0;

else if(n == 2)

return 1;

else

return Fib(n-1)+Fib(n-2);

}

여기서 중요한 것은 수학적 재귀의 표현이 그대로 코드로 옮겨졌으음을 인식하는 것이다.

※ 시간이 지나서 재귀함수에 익수해지면 누구나 함수의 호출순서에 신경을 쓰지 않게 된다.

위에서 보이듯이 피보나치 수열의 7번째 값의 출력을 위해서 25회의 함수호출이 동반되었다. 

때문에 성능상의 불리함은 분명 존재한다.

+ 연산자의 왼편에 있는 Fibo 함수호출이 완료되어야 비로소 + 연산자의 오른편에 있는 Fibo 함수호출이 진행이 된다.

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이고, C언어는 이렇듯 중요한 재귀를 지원하는 언어이다.

재귀함수란, 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

"재귀 함수를 실행하는 중간에 다시 재귀 함수가 호출되면, 재귀 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다."

실제로 함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서) 실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 

따라서 재귀 함수의 중간쯤 위치한 명령문을 실행하다가 다시 재귀 함수의 앞 부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다. 그래서 재귀적인 형태의 함수호출이 가능한 것이다.

위의 코드에서 Recursive 함수에 0이 전달도면서 '재귀의 탈출조건'이 성립되어 함수가 반환하기 시작한다. 

이렇듯 재귀함수의 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

재귀함수의 디자인 사례

- 재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다. 무엇보다도 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다.

# 팩토리얼

위의 식에서 보이듯 f(0)에 해당하는 0!이 1이므로 이것이 재귀함수의 탈출조건이 된다. (수학적으로 0!과 1!은 모두 그 값이 1로 동일하다) 따라서 이제 위의 식은 재귀함수를 이용해서 그대로 코드로 옮길 수 있다.

함수의 코드만 이해하려  하지 말고 그 과정을 이해하려고 노력해야 한다.

순차 탐색 알고리즘의 T(n) 함수:     

이진 탐색 알고리즘의 T(n) 함수:      

                                           →                 

                   →                

※  의 알고리즘을  의 알고리즘으로 개선시키는 것은 약간의 개선이 아닌, 혁신적인 성능의 개선으로 간주된다.

# 비교를 위한 실험의 원칙

- 최악의 경우를 대상으로 비교하는 것이 목적이니 탐색의 실패를 유도한다.

- 탐색의 실패가 결정되기까지 몇 번의 비교연산이 진행되는지를 센다.

- 데이터의 수는 500, 5000, 50000 일 때를 기준으로 각각 실험을 진행한다.

 인 순차 탐색 알고리즘의 경우, 실험을 통하지 않아도 비교연산의 횟수가 500, 5000, 50000 임을 알 수 있다. 선형 빅-오이기 때문에!

두 알고리즘의 비교연산횟수 비교

위의 표에 정리된 결과는  의 알고리즘과  의 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지를 보여준다.

데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 그리고 오차 없이 구하는 것은 대부분의 경우 쉽지 않다. 

그래서 Big-Oh 표기법을 사용한다.

빅-오라는 것은 함수 T(n) 에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다. 

이때 사용되는 표기법에 대문자 O, 그러니까 큰 O가 사용되기 때문에 빅-오라고 하는 것이다.

  이것을   이렇게 근사치(approximation) 식을 구성해도 문제가 되지 않는다. 

그 이유는 표를 통해서    에서   이 차지하는 비율을 확인하면 알 수 있다.

 이 차지하는 비율의 증가를 나타내는 표

표에서 보이듯이  이 차지하는 비율은 절대적이다.   이 조금만 증가해도 이내  이 차지하는 비율은 99%를 넘어선다.

따라서,  은  으로 간략화 할 수 있다.

그리고 이것을 빅-오 표기법으로 표현하면 다음과 같다.

         =>            빅-오 오브         =>            

정리하면 함수  의 빅오는  이며, 이는  의 증가 및 감소에 따른  의 변화 정도가  의 형태를 띰을 의미한다.

예를 들면,

                                      ▶                 

                                     ▶                

                    ▶                

그리고 이것을 일반화화면 다음과 같다.

                 ▶                

즉, 다항식으로 표현된 시간 복잡도 함수 T(n)에서 실제로 큰 의미를 갖는 것은  '최고차항의 차수' 라는 이야기다.

※ 빅-오는 "데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)" 을 나타내는 표기법이다.

 이것은 다음과 같이 이해해야 옳다.

- "데이터 수의 증가에 따른 연산횟수의 증가 형태를 좌표평면상에 그려놓으면, 증가하는 추세가 둔화되는 형태를 띤다. 즉, 로그 그래프와 유사한 형태를 띤다."

빅-오는 성능 분석에 좋은 도구가 된다.

대표적인 빅-오

'데이터 수의 증가'에 따른 '연산횟수의 증가 형태를 표현한 것'이 빅-오이다 보니, 데표적인 빅오 표기가 존재한다. 이것들은 알아둘 필요가 있다.

상수형 빅-오라 한다. 이는 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다. 연산횟수가 고정인 유형의 알고리즘을 대표한다.

로그형 빅-오라 한다. 이는 '데이터 수의 증가율'에 비해서 '연산횟수의 증가율' 이 훨씬 낮은 알고리즘을 의미한다. 따라서 매우 바람직한 유형이다. 

참고로 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만, 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무기가 된다.

선형 빅-오라 한다. 이는 데이터의 수와 연산횟수가 비례하는 알고리즘을 의미한다.

선형로그형 빅-오라 한다. 이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘을 의미한다. n과 logn을 곱한 형태라서 난해해 보이지만, 알고리즘 중에는 이에 해당하는 알고리즘이 적지 않다.

데이터 수의 제곱에 해당하는 연산홧수를 요구하는 알고리즘을 의미한다. 따라서 데이터의 양이 많은 경우에는 적용하기가 부적절하다.

이는 이중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 

즉, 중첩된 반복문의 사용은 알고리즘 디자인에서 그리 바람직하지 못하다고 할 수 있다.

데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다.

이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다. 이 역시 그냥 적용하기에는 무리가 있는 알고리즘이다.

지수형 빅-오라 한다. 이는 사용하기에 매우 무리가 있는... 사용한다는 것 자체가 비현실적인 알고리즘이다.

'지수적 증가' 라는, 매우 무서운 연산횟수의 증가를 보이기 때문이다. 처음 알고리즘을 개발했을 때 이러한 성능을 보인다면, 개선의 과정을 거쳐서 현실적인 연산횟수를 보이는 알고리즘으로 수정되어야 한다.

빅-오 표기들의 성능(수행시간, 연산횟수) 의 대소를 정리

   <    <     <     <    <    <  

이진 탐색 알고리즘은 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 알고리즘이다.

하지만 배열을 대상으로 이진 탐색 알고리즘을 적용하기 위해서는 다음의 조건을 만족해야만 한다.

"배열에 저장된 데이터는 정렬되어 있어야 한다."

즉, 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다 (정렬의 기준 및 방식과는 관계없다).

만약 길이가 9인 배열이 있다고 가정하면...

이진 탐색 알고리즘의 첫 번째 시도:

1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다.

즉, 배열의 중앙에, 찾는 값이 저장되어 있는지 확인하는 것이 이진 탐색 알고리즘이다.

이진 탐색 알고리즘의 두 번째 시도:

1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다.

2. 대소의 비교결과는 arr[4] > 3 이므로 탐색의 범위를 인덱스 기준 0~3으로 제한한다.

3. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

두 번째 시도 과정에서 주의 깊게 살펴볼 것은 탐색의 대상을 반으로 줄였다는 사실이다. 이는 어디까지나 배열에 데이터가 정렬된 상태로 저장되었기 때문에 가능한 일이다.이것이 바로 이진 탐색 알고리즘의  핵심이다.

이진 탐색 알고리즘의 세 번째 시도:

1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.

2. 대소의 비교결과는 arr[1] < 3 이므로 탐색의 범위를 인덱스 기준 2~3으로 제한한다.

3. 2와 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

이렇듯 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복할 뿐이다. 하지만 세 번째 시도를 진행하면서 탐색 대상인 3을 찾게 되니, 이로써 탐색은 마무리가 된다.

이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘이다. 때문에 순차 탐색 알고리즘에 비해 좋은 성능을 보인다.

위의 이진 탐색 알고리즘에서 last = mid-1; 과 first = mid+1; 에 감소와 증가가 없다면 어떻게 될까?

값을 하나 빼거나 더해서 그 결과를 변수 last와 first에 저장하지 않으면, mid에 저장된 인덱스 값의 배열요소도 새로운 탐색의 범위에 포함이 된다. 그런데 이는 불필요한 일이다. mid의 배열요소에 탐색 대상이 저장되어 있는지 검사가 이미 끝난 상태이기 때문이다.

그런데 더 큰 문제가 존재한다. 무엇이냐면... 

문제는 탐색의 대상이 배열에 존재하지 않는 경우... 무한루프를 형성하며 프로그램이 종료되지 않는다는 것이다.

탐색의 대상이 배열에 존재하지 않을 경우 first에 저장된 값이 last보다 커져서 반복문을 탈출할 수 있어야 하는데, 위와 같이 코드를 수정하고 나면 결코 first에 저장된 값은 last 보다 커질수 없다 (last는 first보다 작아질 수 없다). 

때문에 무한루프를 형성하게 되는 것이다.

감소나 증가를 하지 않는다면...기본적으로 세 변수에 저장된 인덱스 값은 항상 다음의 식을 만족하도록 알고리즘이 디자인된다.

감소나 증가를 뺀다면, mid에 저장된 값을 가감 없이 first 또는 last에 저장하는 것이 전부이다. 그래서 first는 결코 last보다 커질 수 없고, last는 결코 first보다 작아질 수 없다.

이진 탐색 알고리즘의 시간 복잡도 계산하기 : 최악의 경우(Worst Case)를 기준

우선, 연산횟수를 대표하는 연산이 무엇인지 찾아야 한다.

그런데 이 역시 탐색 알고리즘이니 순차 탐색 알고리즘과 마찬가지로 == 연산을 연산횟수를 대표하는 연산으로 볼 수 있다.

"데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교연산의 횟수는 어떻게 되는가?"

- 데이터의 수 n이 n/2, n/4, n/8... 이렇게 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행한다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다. 그러니까 데이터의 수가 8개였다면 8,4,2,1 이렇게 줄어드니 총 4회 비교연산이 진행된다.

위와 같이 답을 내릴 수 있다. 하지만! 이 정도의 정보는 성능의 분석 및 비교에 사용할 수 없다.

이 정도의 정보를 가지고 앞서 다른 탐색 알고리즘과의 객관적 성능 비교는 가능하지 않다.

위의 데이터의 수가 8개인 상황에서의 비교연산 횟수는 다음과 같이 정리할 수 있다.

# 8이 1이 되기까지 2로 나눈 홧수 3회, 따라서 비교연산 3회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

↓↓↓↓↓ 다시 정리하면...

# n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행.

# 데이터가 1개 남았을 경우, 이때 마지막으로 비교연산 1회 진행.

이로써 비교연산의 횟수를 구했으니, 최악의 경우에 대한 시간 복잡도 함수 T(n)은 다음과 같이 정리된다.

# 최악의 경우에 대한 시간 복잡도 함수 :        T(n) = k + 1

2로 나눈 횟수 k 구하기.

n이 1이 되기까지 2로 나눈 횟수가 k이니, n과 k에 관한 식을 다음과 같이 세울 수 있다.

     =>     n에 8을, k에 3을 대입하면 식은 성립된다. ex) 8 * pow((1/2.0), 3)  하면 1이 나올 것이다. 이 식은 2로 몇 번을 나누어야 1이 되는가에 대한 답을 주는 수식이다.

     ▶         ▶   

※  과 같기 때문에..  이런식이 나올 수 있다.

이제 정리된 최종 수식의 양 변에 밑이 2인 로그를 취한다.

  ▶  ▶   ▶ 

이렇듯 k는 log2n 이다. 따라서 이진 탐색 알고리즘의 최악의 경우에 대한 시간 복잡도 함수 T(n) 은 다음과 같다.

그런데.. 위에 +1이 있었다. 하지만 +1은 중요하지 않다. 

중요한 것은 데이터의 수 n이 증가함에 따라서 비교연산의 횟수가 로그적(logarithmic)으로 증가한다는 사실이다.

"식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다."

즉, n에 대한 식 T(n)을 구성하는 목적은 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단하는 것이므로 +1은 중요하지 않다.