Hong's Programing World

ArrayBaseStack.c

ArrayBaseStack.h

ArrayBaseStackMain.c

- 배열 스택

ListBaseStack.c

ListBaseStack.h

ListBaseStackMain.c

- 리스트 스택

InfixToPostfix.c

InfixToPostfix.h

InfixToPostfixMain.c

ListBaseStack.c

ListBaseStack.h

- infix -> postfix

ListBaseStack.c

ListBaseStack.h

PostCalculator.c

PostCalculator.h

PostCalculatorMain.c

- postfix Calculator

LinkedRead.c

배열과 연결리스트 비교

정렬 기능이 추가된 리스트 자료구조의 ADT

void ListInit(List *pList);
- 초기화할 리스트의 주소 값을 인자로 전달한다.
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List *pList, LData data);
- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

int LFirst(List *pList, LData *pData);
- 첫 번째 데이터가 pData가 가리키는 메모리에 저장된다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

int LNext(List * pList, LData *pData);
- 참조된 데이터의 다음 데이터가 pData가 가리키는 메모리에 저장된다.
- 순차적인 참조를 위해서 반복 호출이 가능하다.
- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야한다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

LData LRemove(List *pList);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

int LCount(List *pList);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

void SetSortRule(List *pList, int (*comp)(LData d1, LData d2));
- 리스트에 정렬의 기준이 되는 함수를 등록한다.

CLinkedList.c

CLinkedList.h

CLinkedListMain.c

DBLinkedList.c

DBLinkedList.h

DBLinkedListMain.c

추상 자료형(Abstract Data Type)

- 기능의 완성 과정을 언급하지 않고 순수하게 기능이 무엇인지를 나열한것.

구조체 Wallet 

typedef struct _wallet
{
    int coin100Num;         //100원짜리 갯수
    in bill5000Num;         //5,000원짜리 갯수
} Wallet

Wallet의 추상 자료형

1) int TakeOutMoney(Wallet *pw, int coinNum, int billNum)
  - 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼낸다.
  - 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수를 전달한다.
  - 꺼내고자 하는 돈의 총액이 반환된다. 그리고 그만큼 돈은 차감된다.

2) void PutMoney(Wallet *pw, int coinNum, int billNum)
  - 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣는다.
  - 주 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수를 전달한다.
  - 넣은 만큼 동전과 지폐의 수가 증가한다.

* 추상 자료형을 명시하는데 있어 특정 언어에 의존적이지 않게 별도의 표기법을 활용하는 것이 좋겠지만 필수는 아니다. 그리고 구조체 Wallet의 정의는 꼭 포함하지 않아도 된다.
* 자료구조를 구현할때 가급적 다음의 순서를 따르길 바란다.
  - 구현하고자 하는 자료구조의 ADT를 정의한다.
  - ADT를 근거로 해당 자료구조를 활용하는 main함수를 정의한다.
  - ADT를 근거로 해당 자료구조를 구현한다.

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

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

1) ADT 정의하기. 
- ADT를 정의하기에 앞서 내가 정의하고자 하는 자료형에 대한 특성을 결정해야 한다. 리스트의 특성을 정의하자면, "데이터를 나란히 저장하고 중복된 데이터의 저장을 막지 않는다." 정도가 될것이다. 그럼 이를 기반으로 ADT를 정의해 보겠다.

ADT를 정의하기 위한 접근법으로 "일단 데이터를 나란히 저장해야 하니까..." 에서 시작해서 구현방법에 초점을 맞추는 경우가 있는데, 이는 잘못된 접근방식이다. 데이터를 어떻게 나란히 저장할지를 고민하는게 아니라, 나란히 저장된다는 특성을 기반으로 제공해야 할 기능들을 정의해야 하는 것이다.

2) 리스트 자료구조의 ADT

void ListInit(List *pList);
- 초기화할 리스트의 주소 값을 인자로 전달한다.
- 리스트 생성 후 제일 먼저 호출되어야 하는 함수이다.

void LInsert(List *pList, LData data);
- 리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다.

int LFirst(List *pList, LData *pData);
- 첫 번째 데이터가 pData가 가리키는 메모리에 저장된다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

int LNext(List * pList, LData *pData);
- 참조된 데이터의 다음 데이터가 pData가 가리키는 메모리에 저장된다.
- 순차적인 참조를 위해서 반복 호출이 가능하다.
- 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야한다.
- 참조 성공 시 TRUE(1), 실패 시 FALSE(0) 반환

LData LRemove(List *pList);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

int LCount(List *pList);
- 리스트에 저장되어 있는 데이터의 수를 반환한다.

3) 구현 소스 확인

- 구현 소스는 첨부 파일을 확인하기 바란다.
- 구현 소스 중 중요한 부분이나 주의해야할 부분에 대해서만 언급하겠다.

3-1. ArrayList.h

typedef int LData;
- 위와 같은 typedef 선언은 typedef선언의 변경만으로 다양한 데이터 저장을 쉽게 하기 위해서이다. 

3-2. ArrayList.m
3-2-1. LData LRemove(List *plist) 

- 함수 안에서 (plist->curPosition)--;를 통해 참조위치를 하나 되돌린다.
이유는 위에서 정의한 ADT를 잘 살펴보기 바란다. LNext의 ADT를 보면 참조된 데이터의 다음 데이터를 가리킨다고 되어있다. 즉, 삭제후 LNext호출할 때 ADT의 정의를 만족시키려면 삭제 후 참조위치를 하나 되돌려야 한다.(코드를 보고 정확히 이해하기 바란다.)
- 그리고 왜 LRemove함수가 삭제된 데이터를 반환해야 하는지 의문이 들수도 있다. 이는 3-3의 설명을 보기 바란다.

3-3. PointListMain.c

- Point 구조체를 동적 할당하고 있다. 그리고 Point데이터를 삭제하고 나서 free(ppos); 메모리 해제를 메인함수안에서 하고 있다. 바람직한 방법인가? List 구조체의 LRemove함수안에서 메모리 해제까지 책임져야 하는것이 아닌가? 
- > Point의 경우 동적할당을 하기 때문에 메모리 해제가 필요하지만 동적할당 되지 않은 데이터의 경우 메모리 해제가 필요없다. List가 이런 부분까지 체크해서 메모리 해제의 책임까지 떠맡기에는 무리가 있다고 본것이다. 그래서 메모리 해제의 책임을 List를 사용하는 쪽에 전가하기 위해 LRemove함수는 삭제된 데이터를 반환하는 것이다.

ArrayList.c

ArrayList.h

ListMain.c

PointListMain.c

복잡도

- 시간 복잡도(Time Complexity)
 : 얼마나 빠른가(CPU에게 얼마나 부담이 가는가?)

- 공간 복잡도(Space Complexity)
 : 얼마나 메모리를 많이 사용하는가?

- 일반적으로 알고리즘을 평가할 때는 메모리의 사용량 보다 실행속도(시간 복잡도)에 초점을 둔다. 공간복잡도는 알고리즘을 평가하는데 있어서 보조적인 열할을 한다. 메모리를 얼마나 쓰느냐는 것은 메모리에 데이터를 썼다 지웠다 하는 작업을 얼만큼 하느냐이다. 일반적으로 시간복잡도에 비래 메모리 access 시간이 극히 적게 걸리기 때문에 그리 중요하지 않다는 것이다.

순차 탐색(Linear Search) 알고리즘과 시간 복잡도 분석의 핵심요소

int LSearch(int arr[], int len, int target)
{
    int i;
    for (i=0; i<len; i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;
}

* 위 함수에서 수행되는 연산은 '<', '++', '==' 이다. 그럼 위에 for문이 한번 돌아갈때 마다 3번의 연산횟수를 모두 세야 하는가? 결론적으로 말하면 그렇지 않다. 저 세개의 연산중 핵심연산을 찾아 그 연산의 횟수만 세면 된다. 그렇다면 핵심연산을 찾는 기준을 알아야 할것이다. 핵심 연산이라는 것은 주변 연산의 실행 여부를 결정짓는 결정권자 라는 것이다. 위 코드로 예를 들면, '<', '++' 연산은 '==' 연산의 결과에 따라 실행 될수도 있고 되지 않을 수도있다. 그렇기 때문에 '==' 연산이 핵심 연산이라는 얘기이고, 복잡도를 계산할때 '=='연산의 횟수만 고려하면 된다.

최선의 경우? 평균적인 경우? 최악의 경우?

알고리즘의 성능을 판단할 때, 어떠한 경우를 기준으로 성능을 측정해야 할 지 궁금해 하는 사람들이 있을거이다. 먼저 최선의 경우는 고려할 필요가 없다. 대부분 알고리즘의 최선의 경우는 복잡도가 O(1)일 것이기 때문이다. 그렇다면 논리적으로 평균적인 경우를 기준으로 잡고 알고리즘을 측정해야 정확한 성능 측정이라고 말할 수 있는것 아닌가? 논리적으로 말하면 그렇지만 일반적으로 알고리즘의 평균적인 경우에 대한 복잡도를 측정하는것이 매우 힘들고, 어떠한 상황이 평균적인 경우라고 정의하는것 조차 애매하기 때문이다. 그래서 보통 알고리즘을 측정할 때는 최악의 경우(Worst Case)를 기준으로 측정한다.

* 위 순차탐색 알고리즘의 경우 데이터 갯수(배열안에 존재하는 데이터의 갯수)가 n개일때 최악의 경우 핵심연산을 n번 수행해야 하기 때문에 O(n)의 복잡도를 갖는다고 할 수 있다.

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

int BSearch(int arr[], int len, int target)
{
    int first = 0;
    int last = len - 1;
    int mid;

    while (first <= last)
    {
        mid = (first + last) / 2;
        
        if (target == arr[mid])
        {
            return mid;
        }
        else
        {
            if (target < arr[mid])
                last = mid - 1;
            else
                first = mid + 1;
        }
    }
    
    return -1;
}

위 이진탐색 알고리즘의 복잡도는 O(log n)이다. 위 알고리즘의 핵심연산이 한번씩 수행될 때 마다 내가 고려해야 되는 데이터 갯수는 1/2로 줄어든다. 그러므로 데이터의 갯수 n이 1이 되기까지 2로나눈 횟수가 알고리즘의 복잡도이다. 이것을 수식으로 나타내면 log n이 되는것이다.(밑이 2인 log)

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

만약 어떤 알고리즘의 시간복잡도가 정확히 "T(n) = n^2 + n + 1" 이라면 빅오 표기법으로 표현할 때, O(n^2)으로 표현한다. 즉 빅오 표기법은 주어진 알고리즘 다항식에서 최고차항의 차수만 뽑아 표현하는 것이다.

T(n) = n^2 + 2n + 1                --> 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)

여기서 드는 의문, 아니 n^2 + 2n + 1의 경우 2n + 1을 맘대로 없애버려도 알고리즘을 정확히 측정했다고 할 수 있는가?
이 질문에 대답하기 전에 우리가 왜 알고리즘을 측정하는가에 대해서 고찰해 볼 필요가 있다. 처리해야 하는 데이터 갯수가 많지 않을때 알고리즘의 성능을 측정하는것이 의미가 있는가? 난 아니라고 본다. 데이터가 많지 않을경우는 왠만큼 알고리즘의 성능이 나빠도 큰 문제없이 프로그램을 돌아가기 마련이다. 우리가 알고리즘 성능 측정을 하는 이유는 데이터의 갯수가 아주 많을 때, 즉 기하 급수적으로 늘어날 때 프로그램의 성능을 떨어뜨릴만한 성능적으로 안좋은 영향을 미칠 수 있는가 또는 프로그램의 성능을 향상시킬 수 있는가에 대해서 알아보려고 하는것이다. 
자 그러면, 위에 언급한 정의대로라면 알고리즘 성능 측정은 데이터 갯수가 많을때 의의가 있다. 아래 표를 보자.

T(n) = n^2 + 2n + 1 이라 가정.

요즘 알고리즘에서 데이터 갯수가 1000개 10000개라고 해도 그렇게 많은 데이터 갯수가 아니다. 그럼에도 불구하고 빅오 표현법에서 살아 남는 n^2의 비율이 T(n)의 99프로 이상을 차지한다. 그렇기 때문에 과감하게 최고차항의 차수를 제외하고 성능을 고려해도 아무 문제가 없다는 것이다.

O(1) 
- 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다.
0(logn)
- 로그형 빅-오, 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 그 차이는 알고리즘의 성능관점에서 매우 미미하기 때문에 대부분의 경우에 있어서 무시가 된다. 일반적으로 매우 만족스러운 속도의 알고리즘이다.
0(n)
- 선형 빅-오, 데이터의 수와 연산횟수가 비례하는 알고리즘이다.
0(nlogn)
- 선형 로그형 빅-오, 알고리즘 중에 이에 해당하는 알고리즘이 적지 않다.
0(n^2)
- 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘, 중첩 반복문이 보통 이 형태를 띈다. 따라서 알고리즘 디자인에서 그리 바람직하지 못한 형태이다.
0(2^n)
- 지수형 빅-오, 가장 성능이 좋지않은 알고리즘이다. 

*성능: O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n)

*순차 탐색 VS 이진 탐색 알고리즘 성능 비교

Introduction

- 프로그램이란 데이터를 포현하고, 그렇게 표현된 데이터를 처리하는 것이다.

위에서 말한 '데이터의 표현'은 '데이터의 저장'을 포함하는 개념이다. '데이터의 저장 및 표현'이 바로 자료구조라고 할수 있다. 그리고 '데이터의 처리'는 알고리즘이라고 말할 수 있을것이다.

넓은 의미에서 int형 변수도, 구조체의 정의도 자료구조에 속한다. 각각 모두 데이터를 표현 및 저장하는 하나의 방법이기 때문이다.

자료구조의 분류

1) 선형구조
: 선형 자료구조는 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다.
- 리스트
- 스택
- 큐

2) 비선형구조
: 비선형 자료구조는 데이터를 나란히 저장하지 않는 구조이다.
- 트리
- 그래프

3) 파일구조
- 순차파일
- 색인파일
- 직접파일

4) 단순구조
- 정수
- 실수
- 문자
- 문자열

*자료구조 학습에 있어서 기억할 것 두가지

1) 자료구조의 모델을 그림으로 우선 이해하라.
- 그림을 많이 그려봐라! 정말중요!
2) 실제로 구현해봐라!
- 처음부터 끝까지 구현해 보는것도 좋지만, 빈칸 채우기도 괜찮다!