Pw4ngC0

배열을 이용한 리스트의 구현

리스트의 이해

리스트라는 자료구조는 구현방법에 따라서 크게 두가지로 나뉜다.

- 순차 리스트 : 배열을 기반으로 구현된 리스트

- 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

리스트 자료구조의 기본적이고 중요한 특성

- 리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다.

리스트 자료구조의 ADT

void ListInit(List * plist);

-초기화 할 리스트의 주소 값을 인자로 전달한다.

-리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List * plist, LData data);

-리스트에 데이터를 저장한다. 매개 변수 data에 전달된 값을 저장한다.

int LFirst(List * plist, LData * data);

-첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.

-데이터의 참조를 위한 초기화가 진행된다.

-참조 성공시 TRUE(1), 실패시 FALSE(0) 반환

int LNext(List * plist, LData * pdata);

-참조된 데이터의

LData LRemove(List * plist);

-LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다.

-삭제된 데이터는 반환된다.

-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다. 

함수들에 대한 소스코드이다. list를 사용하기 위해서는 변수 들의 초기화에 해당하는 ListInit 함수를 호출해야한다. 이후 LInsert 함수를 통해 list에 데이터를 삽입 시킬 수가 있다.

데이터 참조에 사용되는 함수는 LFirst와 LNext이다. LNext가 호출되기 위해서는 반드시  LFirst가 호출되어야 한다. 이후 LNext를 호출하여 list를 순차적으로 참조할 수있다. LNext함수는 호출 할 때마다 다음에 저장된 데이터를 얻을 수 있다.

데이터 삭제에는 LRemove함수가 사용된다. LFrist나 LNext함수를 통해 참조된 데이터를 삭제하는데 사용된다.

LCount함수는 리스트에 저장되어있는 데이터의 수를 반환한다.

List를 이용한 문제 03-1

List를 이용한 문제 03-2

추상 자료형(Abstract Data Type)

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

특수한 자료형을 정의하고 이 자료형을 기반으로 하는 연산의 종류를 결정하는 것도 자료형 정의의 일부로 보아야 한다. 자료형과 연산의 종류가 결정되었을 때 자료형의 정의는 완성된다.

위에서 말하는 연산의 의미는 +, -와 같은 C언어에서 제공하는 연산을 의미하는 것이 아니고, 정의한 자료형을 기반으로 제공할 수 있는 기능 관련 연산을 의미하는 것이다. 즉, '자료형'의 정의에 '기능' 혹은 '연산'과 관련된 내용을 명시 할 수 있다는 것이다.

ex)

wallet 자료형의 구조체 정의

typedef struct _wallet

{

     int   coin100Num;

     int   bill5000Num;

}Wallet;

Wallet의  ADT

int TakeOutMoney(Wallet * pw, int coinNum, int billNum)

-첫번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.

-두번째 인자로 꺼낼 동전의 수, 세번째 인자로 꺼낼 지폐의 수를 전달한다.

- 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

void PutMoney(Wallet * pw, int coinNum, int billNum)

-첫번째 인자로 전달된 주소의 지갑에 돈을 넣는다.

-두번째 인자로 넣을 동전의 수, 세번째 인자로 넣을 지폐의 수를 전달한다.

- 넣은 만큼 동전과 지폐의 수가 증가한다.

wallet자료형의 정의에 '기능' 혹은 '연산'을 하는 TakeOutMoney 함수와 PutMoney함수가 ADT에 포함된다. 

하노이 타워 문제의 이해

하노이 타워 : 원반은 한번에 하나씩 옮길 수 있으며 옮기는 과정에서 작은원반위에 큰 원반이 올라가서는 안된다.

원반의 수가 많아질수록 하노이 타워의 문제해결이 어려워진다. 그러나 하노이 타워도 원반의 수가 늘어날 수록 일련의 과정을 더 많이 반복할 뿐이다.

하노이 타워 문제의 해결

막대 A,B,C가 있을 때, 막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정은 다음과 같이 재귀적으로 구성이 된다.

1.작은 원반 n-1개를(가장 큰 맨 아래 원반을 제외한 나머지 원반)A에서 B로 이동

2.큰 원반(맨 아래의 원반) 1개를 A에서 C로 이동

3.작은 원반(가장 큰 원반 제외) n-1개를 B에서 C로 이동.

위를 재귀로 구성할 때 탈출 조건은 "이동해야할 원반의 수가 1개"인 경우이다. 이동해야할 원반의 수가 1개이면 그냥 옮기면 되기 때문이다.

하노이 타워 함수

위 함수의 매개변수 from에 꽂혀있는 num개의 원반을 by를 거쳐서 to로 이동한다는 의미의 변수들이다.

HanoiTowerMove(num-1, from, to, by);

위 함수는 n-1개의 원반을 A에서 B로 이동하는 함수이다. 이후 printf()함수를 통해 가장 큰 원반(맨 아래의 원반)1개를 A에서 C로 이동한다.

HanoiTowerMove(num-1, by, from, to);함수를 통해 B에 있는 n-1개의 원반을 C로 이동시킨다.

재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수

ex)

void Recursive(void)

{

    printf("Recursive call! \n");

    Recursive();

}

Recursive 함수내의 Recursive 함수가 호출되면, Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 재귀함수를 진행한다.

함수를 구성하는 명령문은 CPU로 이동이 되어서(복사가 되어서)실행이 된다. 그런데 이 명령문은 얼마든지 CPU로 이동이(복사가) 가능하다. 즉 Recursive함수의 중간까지 명령문을 실행하다가 다시 Recursive함수의 앞부분에 위치한 명령문을 CPU로 이동시키는 것은 문제가 되지 않는다.

또한 위 코드처럼 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한일이다.

재귀의 활용

피보나치 수열 : Fibonacci Sequence

피보나치 수열은 재귀적인 형태를 띄는 대표적인 수열로서 앞엣것 두개를 더해서 현재의 수를 만들어가는 수열이다. 첫번째, 두번째 값은 0,1로 고정이고 세번째부터 앞의 두수를 더하여 수열을 만들어간다.

피보나치 수열 수학적 표현

위 수식의 코드

int Fibo(int n)

{

     if(n == 1)

         return 0;

     else if(n== 2)

         return 1;

     else

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

}

위 코드의 함수 호출 순서를 정리하기 위한 코드

return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

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

위 순서대로 재귀함수들이 실행된다 즉 return Fibo(n-1)+Fibo(n-2); //return Fibo(6)+Fibo(5);

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

이진 탐색(Binary Search) 알고리즘 소개

이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 이진 탐색 알고리즘은 탐색의 대상을 반복해서 반씩 떨구어내 탐색 대상을 찾아내는 알고리즘 이다.

정렬된 배열에서 탐색의 시작 위치를 first, 탐색의 마지막 위치에 해당하는 인덱스 값을 last로 표기한다. 이진 탐색 알고리즘이 진행되면 first와 last는 점차 가까워진다.

이진 탐색은 first가 last보다 큰경우 종료된다. 이렇게 종료되는 경우는 탐색에 실패한 경우이다.

if(target < ar[mid])

     last = mid -1;

else

     first = mid + 1;

이진 탐색 알고리즘에서 위처럼 구성해야 하는 이유는 한번 탐색한 대상을 포함하지 않기 위함과 탐색의 대상이 배열에 존재하지 않는 경우를 위함이다.

if(target < ar[mid])

    last = mid;

else

    first = mid;

위처럼 알고리즘이 구성되어 있을 때, 탐색의 대상이 배열에 존재하지 않는다면 프로그램은 끝나지 않을것이다. 탐색의 대상이 존재하지 않을때 이진 탐색을 끝내는 경우는 first가 last보다 커졌을 때 이기 때문이다.

이진 탐색 알고리즘의 시간 복잡도 계산(worst case 기준)

이진 탐색 알고리즘에서 데이터 수가 n개일 때, 최악의 경우 비교연산 횟수는 얼마인가?

n일때 1회

데이터 개수가 n/2일때 1회

데이터 개수가 n/4일때 1회

데이터 개수가 n/8일때 1회

....

개수가 1일때 1회이다.

위 과정을 정리하면 n이 1이 될때까지 2로 나눈 횟수 k회, 이진 탐색에서 비교연산 k회를 진행,

데이터가 1개 남았을 때 비교연산 1회

즉 최악의 경우에 대한 시간복잡도 함수 T(n)은 T(n) = K+1 이 된다.

n이 1이 되기까지 2로 나눈 횟수가 k이다.

n과 k에 관한식

-> n x (1/2)^k = 1

위 식을 정리하면

n x (1/2)^k =1 -> n x 2^(-k) = 1 -> n = 2^k

(^는 제곱이다.)

n = 2^k에서 양변에 log2를 취해준다.

log2 n = klog2 2 -> log2 n = k

위 식은 이진 탐색 알고리즘의 worst case 시간 복잡도 함수이다. 즉 T(n) = log2 n이 된다.

정확하게는 T(n) = log2 n +1이지만 +1은 중요하지 않다.

n이 증가함에 따라 연산횟수가 로그적으로 증가한다는 것이 중요하다.

위처럼 식(T(n))을 구성함으로써 데이터 수의 중가에 따른 연산횟수의 변화 정도를 판단할 수 있게 된다.

빅-오 표기법(Big-Oh Notation)

빅-오 : 시간복잡도 함수 T(n)에서 가장 영향력이 큰부분

T(n) = n^2 + 2n + 1

위 식에서 n이 커짐에 따라 2n + 1이 미치는 영향은 미미해지므로 T(n) = n^2으로 간략화 할 수 있다.

이를 빅-오 표기법으로 표현하면 O(n^2)이며, 읽을 때는 "빅-오 오브 n^2(Big-Oh of n^2)"이라고 읽는다.

단순하게 빅-오 구하기.

T(n)이 다항식으로 표현된 경우, 최고차항의 차수가 빅-오가 된다.

ex)

T(n) = n^2 + 2n + 9               ->      O(n^2)

T(n) = n^4 + n^3 + n^2 + 1    ->      O(n^4)

T(n) = 5n^3 + 3n^2 + 2n + 1   ->      O(n^3)

위를 일반화 하면 다음과 같다.

T(n) = a(m)n^m + a(m-1)n^(m-1) + ... a(1)n^1 + a(0)     -> O(n^m)

시간 복잡도 함수가 n^2인 경우에도, 9999n^2인 경우에도 O(n^2)이다. 빅-오는 '데이터 수의 증가에 따른 연산횟수의 증가 형태(패턴)'을 나타내는 표기법 이기 때문이다.

O(log n)의 경우 데이터 수 증가에 따라 로그 그래프와 유사한 형태를 띤다.

대표적인 빅-오

1.O(1)

상수형 빅-오 이다. 데이터 수와 상관없이 연산횟수가 고정인 알고리즘이다. 데이터 수와 상관없이 3회 진행되는 알고리즘일지라도 O(1)이 된다. O(1)는 연산횟수가 고정인 알고리즘이라는 의미가 담겨있다.

2.O(log n)

로그형 빅-오 이다. '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘을 의미한다. 매우 바람직한 유형이다. 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 알고리즘 성능 관점에서는 매우 미미하기 때문에 대부분의 경우 무시된다.

3.O(n)

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

4.O(nlog n)

선형로그형 빅-오 이다. 이는 데이터의 수가 두배로 늘 때, 연산횟수는 두배를 조금 넘게 증가하는 알고리즘을 의미한다.

5.O(n^2)

데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 데이터양이 많은 경우 부적절하다. 이중으로 중첩된 박복문 내에서 연산이 진행되는 경우 발생한다.

6.O(n^3)

데이터 수의 세제곱에 해당하는 연산 횟수를 요구하는 알고리즘이다. 이는 삼중으로 중첩된 반복문 내에서 알고리즘에 관련된 연산이 진행되는 경우에 발생한다.

7.O(2^n)

지수형 빅-오 이다. '지수적 증가'라는 무서운 연산횟수의 증가를 보인다. 이러한 성능을 보이는 알고리즘이라면 개선의 과정을 거쳐서 현실적인 알고리즘으로 수정해야 한다.

빅-오 성능 대소관계

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n)

순차 탐색 알고리즘과 이진 탐색 알고리즘 비교

순차 탐색 알고리즘 : T(n) = n

이진 탐색 알고리즘 : T(n) = log2 n + 1

각각의 빅-오

순차 탐색 알고리즘 : O(n)

이진 탐색 알고리즘 : O(log2 n)

O(n)의 경우 실험을 하지 않아도 비교연산 횟수와 데이터 수가 같음을 알 수 있다.

이진 탐색 알고리즘 실험 코드

위 실행결과를 통해 순차탐색 알고리즘과 이진 탐색 알고리즘 연산 횟수 비교

                     n                           순차 탐색 연산횟수                             이진 탐색 연산횟수

                    500                                 500                                                   9

                   5000                               5000                                                  13 

                  50000                              50000                                                 16

위 결과를 통해 O(n)과 O(log n) 알고리즘의 연산횟수에 얼마나 큰 차이가 있는지 알 수 있다.

자료구조 : 데이터의 표현 및 저장 방법

자료구조의 분류

선형 구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식

비선형 구조 : 데이터를 나란히 저장하지 않는 구조

자료구조와 알고리즘

자료구조가 '데이터의 표현 및 저장 방법' 이라면, 알고리즘은 표현 및 저장된 데이터를 대상으로 하는 '문제 해결 방법'이다.

-> 자료구조가 결정되면 그에 따른 효율적인 알고리즘을 결정할 수 있다.

     알고리즘은 자료구조에 의존적이다.

알고리즘 성능 분석 방법

잘 동작하고 좋은 성능을 보장받기를 원한다면 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다.

자료구조와 알고리즘을 평가하는 두가지 요소는 '속도'와 '메모리 사용량' 이다.

속도에 해당하는 수행시간 분석결과를 '시간 복잡도(time complexity)' 라고 하고, 메모리 사용량에 대한 분석 결과를 '공간 복잡도(space complexity)'라고 한다.

알고리즘 수행 속도 평가 방식

1.연산의 횟수

2.데이터의 수 n에 대한 연산횟수 T(n) 구성.

함수 T(n)을 구성하면 데이터 수의 변화에 따른 연산 횟수 변화를 한눈에 파악할 수 있어, 둘 이상의 알고리즘을 비교하기 용이해진다.

데이터 수에 따라 연산횟수도 달라지기 때문에 상황에 맞는 알고리즘을 찾아야 한다.

탐색 알고리즘에서는 == 연산을 적게 수행하는 탐색 알고리즘이 좋은 탐색 알고리즘이다.

비교 연산의 수행횟수가 줄어들면 < 연산과 ++ 연산의 수행횟수도 줄어들고, 비교연산의 수행횟수가 늘어나면 < 연산과 ++ 연산의 수행횟수도 늘어나기 때문에 다른 연산들은 == 연산에 의존적이다.

위 탐색 알고리즘은 == 연산의 횟수를 대상으로 시간 복잡도를 분석하면된다.

=> 알고리즘의 시간 복잡도를 계산하기 위해서는 핵심이 되는 연산이 무엇인지 잘 판단해야 한다.

모든 알고리즘에는 가장 행복한 경우와 가장 우울한 경우가 각각 존재하며, 이를 '최선의 경우(best case)'와 '최악의 경우(worst case)'라 한다. 그러나 알고리즘을 평가하는데 있어서 '최선의 경우'는 관심 대상이 아니다. 알고리즘의 성능을 판단하는데 있어서 중요한 것은 '최악의 경우' 이다.