이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.

스택의 이해와 ADT 정의

스택은 자료구조중에 하나로서 흔히 박스를 쌓는 구조로 설명을 한다. 이를 그림으로 표현하면 다음과 같다.

위의 그림을 보면 2, 4, 6, 8, 10 의 순서로 삽입을 한 형태이다. 먼저 들어온 2가 바닥에 있고 나중에 넣은 10이 위에 있음을 알 수 있다. 이를 상자를 쌓았다고 가정해보자. 상자의 밑 부분 부터 뺄 수 없으므로 당연히 맨 위에 부분부터 뺄 수 있을 것이다. 스택 역시 마찬가지이며 10 부터 뺼 수 있음을 알 수 있다. 이를 후입선출이라 하며 영어로 LIFO(Last In First Out)이다. 그렇다면 스택의 ADT를 살펴보자. 다음과 같다.

void StackInit(Stack * pstack);
// 스택의 초기화를 진행한다.
// 스택 생성 후 제일 먼저 호출되어야 하는 함수이다.

int SIsEmpty(Stack * pstack);
// 스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

void SPush(Stack * pstack, Data data);
// 스택에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data SPop(Stack * pstack);
// 마지막에 저장된 요소를 삭제한다.
// 삭제된 데이터는 반환이 된다.
// 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data SPeek(Stack * pstack);
// 마지막에 저장된 요소를 반환하되 삭제하지 않는다.
// 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

이제 이 ADT를 기반으로 배열 기반, 연결 리스트 기반으로 구현해보자.

배열 기반 스택 구현

스택에서 구현해야 하는 함수는 push, pop이 있고 이를 top이라는 스택의 가장 윗 부분을 담당하는 변수를 이용하여 구현한다.
가장 중요한 함수는 push, pop으로 push의 경우 top을 한칸 올리고 top이 가리키는 위치에 데이터를 저장하고
pop의 경우 top이 가리키는 데이터를 반환하고, top을 아래로 한칸 내린다. push연산을 그림으로 표현하면 다음과 같다.

확인할 수 있는 점은 top의 시작은 -1 이며 하나의 데이터가 들어올 때 0이 된다는 것이다. 처음에 A를 추가할 때
top이 하나 증가한 뒤 해당 top의 위치에 원소가 추가되는것을 확인할 수 있으며 이후로도 마찬가지 이다.

pop연산역시 그림으로 표현하면 다음과 같다.

소스코드는 다음과 같다.

<ArrayBaseStack.h>

<ArrayBaseStack.h>

<ArrayBaseStackMain.c>

스택의 연결 리스트 기반 구현

앞서 스택을 배열로 구현하였는데 연결 리스트로도 구현할 수 있다. 단순하게 자료구조가 바뀐것 이외에는 개념적 단계에서의 구현에는 큰 차이가 없으므로 바로 헤더파일과 이를 통한 구현을 보일것이다.

<ListBaseStack.h>

<ListBaseStack.c>

<ListStackBaseMain.c>

이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.

연결 리스트의 개념적인 이해

먼저 연결 리스트를 배우기에 앞서서 배열 기반 리스트를 살펴보면 배열은 길이의 변경이 불가능하다는 것을 알 수 있다.
따라서 이러한 문제점을 해결한 게 연결 리스트(Linked List) 이다. 먼저 다음의 구조체를 살펴보자.

이 Node 구조체를 이용하여 필요할 때마다 하나씩 동적 할당하여 데이터를 저장하고 이들을 배열처럼 연결할 수 있는
연결 리스트가 되는 것이다. 여기에서 구조체 Node 변수를 노드라 하며 이를 그림으로 그리면 다음과 같다.

먼저 ADT를 살펴보자. ADT는 다음과 같다.

배열 리스트와 비교해보면 SetSortRule함수가 추가된 것을 볼 수 있으며 이는 Head에 추가할지 Tail에 추가할지 정하는 것이다. 장단점은 각각 다음과 같다.

또한 SetSortRule 함수의 매개변수를 보면 함수 포인터가 매개변수로 존재하는 것을 알 수 있는데 반환형이 int, LData형 2개를 전달받는 함수의 주소 값을 전달하는 것이다. 예를 들면 다음의 함수의 주소 값이 매개변수로 전달될 수 있다.

먼저 다음의 형태의 기본적인 노드의 연결 상태를 보고 단점을 파악해보자.

이 경우 노드의 추가 및 삭제 또는 조회의 방법에서 첫 번째 노드와 두 번째 노드의 연결에 차이가 있다. 따라서 이를 방지하기 위해 헤드의 바로 다음에 dummy node를 넣어 어떤 위치에 있던 방법을 일관화 할 수 있다.

이제 연결 리스트를 구현해보자. 다음의 구조체를 기반으로 정의한다.

헤더 파일은 다음과 같다.

<DLinkedList.h>

이를 기준으로 초기화와 삽입을 살펴보자. 초기화는 다음과 같다.

노드를 새로 추가하기 위한 함수는 다음과 같다.

여기에서 볼 수 있는 것은 comp 즉 노드를 정렬하기 위한 기준이 마련되어있느냐에 따라 FInsert, SInsert로 나뉜다는 것이다. 그러나 이들은 내부적으로 정의된 함수이기에 사용자가 직접 호출할 수 없는 함수이다.

먼저 FInsert는 다음과 같다.

그림으로 보면 다음과 같다.

데이터 조회 역시 배열 리스트의 그것과 비슷하지만 before과 Dummy node가 존재한다는 것에서 차이가 있다.
먼저 LFirst 함수를 보자.

역시 그림으로 나타내면 다음과 같다.

LNext 역시 보면 다음과 같다.

역시 그림으로 나타내면 다음과 같다.

노드의 삭제 역시 배열 기반 리스트의 삭제와 비슷하다.

전체의 코드는 각각 다음과 같다.
<DLinkedList.h>

<DLinkedList.c>

<DLinkedListMain.c>

원형 연결 리스트 (Circular Linked List)

단순 연결 리스트에서 마지막 노드가 첫 번째 노드를 가리켜서 원의 형태로 연결이 된 리스트를 원형 연결 리스트 라고 한다. 이를 그림으로 나타내면 다음과 같다.

위의 그림에서 head나 tail에 새로운 노드 1을 추가한다고 가정하면 1 -> 2 -> 4 -> 6 -> 8 -> 1 .... 의 형태 혹은
2 -> 4 6 -> 8 -> 1 -> 2.... 즉 서로 같은 형태가 되므로 head, tail의 구분이 명확히 존재하지 않는다.
유일한 차이점은 tail이 가리키는 노드가 다르다는 것 이다. 따라서 이를 머리에 추가하는 함수, 꼬리에 추가하는 함수는 각각 다음과 같다.

void LInsert(List* plist, Data data) { // tail에 추가
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if (plist->tail == NULL) { // 비어있는 경우
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
		plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가리키게 연결
		plist->tail = newNode; // tail이 새로 추가된 노드를 가르키게 함
	}
	(plist->numOfData)++;
}

void LInsertFront(List* plist, Data data) { // Head에 추가
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	if(plist->tail == NULL) { // 비어있는 경우
		plist->tail = newNode;
		newNode->next = newNode;
	}
	else {
		newNode->next = plist->tail->next; // 새 노드와 기존에 저장된 노드 연결
		plist->tail->next = newNode; // 기존 노드의 tail이 새 노드를 가르키게 연결
	}
	(plist->numOfData)++;
}

이번에는 조회를 살펴보자. 조회의 경우도 Fisrt, Next즉 두가지의 경우에 대한 함수가 존재한다.
LFisrt의 경우 Head가 없기 때문에 tail이 가리키는 다음 노드를 Cur로 한 뒤 이를 반환한다. 그림으로 표현하면 다음과 같다.

int LFirst(List* plist, Data* pdata) {
	if (plist->tail == NULL) { // 비어있는 경우
		return FALSE;
	}
	plist->before = plist->tail; // before가 tail을 가리키게 한다.
	plist->cur = plist->tail->next; // cur이 tail의 다음을 가리키게 한다

	*pdata = plist->cur->data; 
	return TRUE;
}

LNext의 경우도 단순히 before가 cur을 가리키게 하고 cur에 cur이 가리키는 다음 노드를 가리키게 하면 된다.
그 후 cur이 가리키는 노드를 반환하면 된다.마찬가지로 그림으로 나타내면 다음과 같다.

int LNext(List* plist, Data* pdata) {
	if (plist->tail == NULL) { // 비어있는 경우
		return FALSE;
	}
	plist->before = plist->cur; // before가 cur을 가리키게 한다
	plist->cur = plist->cur->next; // cur이 cur의 다음을 가리키게 한다.

	*pdata = plist->cur->data;
	return TRUE;
}

이 두가지 함수 모두 리스트에 원소가 없을 경우에 대해서 처리가 필요한데 단순하게 ADT를 참조하여 노드가 존재하지 않으면 False를 반환하면 된다.

이번에는 노드의 삭제에 대해서 알아보자.
노드의 삭제의 경우 두가지의 경우가 존재하는데 삭제할 노드가 tail인 경우 또는 아닌경우 삭제할 노드가 tail인 경우
노드가 하나밖에 없는 경우 역시 추가로 고려를 해주어야 한다. 다음의 코드를 살펴보자.

Data LRemove(List* plist) {
	Node* rpos = plist->cur;
	Data rdata = rpos->data;

	
	if (rpos == plist->tail) { // 삭제하려는 노드가 tail인 경우
		if (plist->tail == plist->tail->next) { // 노드가 하나인 경우
			plist->tail == NULL;
		}
		else {
			plist->tail = plist->before;
		}
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;
	
	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

위에서 볼 수 있듯 삭제하려는 노드가 tail이 아닌 경우는 다음의 그림처럼 삭제를 진행하면 된다.

 그러나 삭제하려는 노드가 tail인 경우는 단순하게 tail을 하나 앞으로 이동시키면 된다.

단순히 plist->tail = plist->before;을 통해서 말이다.

전체의 코드는 각각 다음과 같다.
<CLinkedList.h>

<CLinkedList.c>

<CLinkedListMain.c>

양방향 연결 리스트

양방향 연결 리스트의 경우 앞서서 구현했던 단순 연결 리스트에서 좌측 혹은 우측을 연결하는 포인터 변수의 존재가 큰 차이점 이다. 그렇다면 헤더파일과 그림을 보고 양방향 연결 리스트를 구현해보자. 헤더파일은 다음과 같다.

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dbLinkedList
{
	Node * head;
	Node * cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);

int LCount(List * plist);

#endif

리스트의 초기화는 각각의 포인터 변수를 NULL로 초기화 하면 된다. 다음과 같다.

void ListInit(List* plist) {
	plist->head = NULL;
	plist->cur = NULL;
	plist->numOfData = 0;
}

삽입의 경우 2가지의 경우가 존재하는데 각각 리스트가 비어있을때, 비어있지 않을 때 이다.
이를 코드로 작성하면 다음과 같다.

void LInsert(List* plist, Data data) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head;
	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

데이터의 조회의 경우 양방향 연결 리스트의 특성으로 좌측, 우측을 모두 조회할 수 있다.
이를 함수료 표현하면 각각 LFisrt, LNext, LPrevious 이며 다음과 같다.

int LFirst(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;
	*pdata = plist->head->data;
	return TRUE;
}

int LNext(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;
	return TRUE;
}

int LPrevious(List* plist, Data* pdata) {
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;
	return TRUE;
}

전체의 코드는 각각 다음과 같다.
<DBLinkedList.h>

<DBLinkedList.c>

<DBLinkedListMain.c>

이 포스팅은 윤성우 님의 열혈 자료구조를 기반으로 합니다.

추상 자료형: Abstract Data Type

추상 자료형은 간단히 ADT라고 불리며 기능만 언급하며 기능의 과정은 포함하지 않는다.
이번에 배울 배열기반 리스트 자료구조의 ADT는 다음과 같다.

리스트에는 크게 두가지의 종류가 있고 이는 다음과 같다.

• 순차 리스트
• 연결 리스트

리스트 자료구조는 데이터를 나란히 저장한다는 점과 중복 데이터의 저장을 허용한다는 큰 특성이 있다.
이제 위의 ADT를 기반으로 main함수를 작성하면 다음과 같다.

<ListMain.c>

위의 ListMain.c를 기반으로 하는 ArrayList.h, ArrayList.c도 다음과 같다.
<ArrayList.h>

먼저 배열 리스트의 데이터 삭제를 살펴보자
배열의 특성상, 그리고 리스트의 특성상 데이터가 나란히 존재해야 하므로 다음의 그림처럼 되는 것을 확인할 수 있다.

또한 가장 최근에 참조가 이루어진 데이터의 인덱스 정보를 담는 변수 curPosition 역시 참조하던 데이터가 삭제되면
앞의 데이터를 참조해야 한다. 이는 다음의 그림과 같다.

실제로 리스트에는 예시의 정수 이외에 다른 자료들도 들어간다. 이번에는 그렇다면 구조체 변수의 주소 값을 저장하여 보자 구조체는 다음과 같다.

<Point.h>

<Point.c>

이 후 ArrayList.h, ArrayList.c를 기반으로 위의 Point 구조체를 저장할 수 있도록 하면 이 과정에서
헤더 파일은 변경이 되어도 되지만 소스파일은 변경이 되면 안 된다.
헤더 파일에서 달라진 점은 typedef int LData; 에서 typedef Point * LData; 으로 변경되었다.
또한 ArrayList.h의 선언문에 #include "Point.h" 를 추가한다. 이제 main함수는 다음과 같다.
<PointListMain.c>

이제 정리해보자.

• 배열 기반 리스트의 단점
  • 배열의 길이가 초기에 결정되어야 한다. 또한 변경이 불가능하다.
  • 삭제의 과정에서 데이터의 이동이 일어난다. (마지막 경우가 아닌 경우)
• 배열 기반 리스트의 장점
  • 데이터의 참조가 쉽다. 인덱스를 기준으로 한 번에 참조가 가능하다.

이 포스팅은 윤성우님의 열혈 자료구조를 기반으로 합니다.

2-1 함수의 재귀적 호출의 이해

재귀 함수란 함수 내에서 자기 자신을 다시 호출하는 함수를 말하며 동작 과정은 다음과 같다.
먼저 다음의 재귀함수 코드를 보자.

이를 그림으로 표현하면 다음과 같다.

Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다. 재귀 함수의 중요한 점은 바로 탈출 조건을 설정해야 한다는 것이다.
위의 코드의 경우 탈출 조건이 없으므로 무한 호출이 된다. 다음의 코드에서는 탈출 조건을 설정하여 3번 출력이 되는것을 확인할 수 있다.

<RecursiveFunc.c>

<실행결과>

재귀함수의 예시로 팩토리얼 함수를 들 수 있다. 먼저 팩토리얼의 수식을 쓰면 다음과 같다.

이를 코드적인 관점에서 생각해보면 n이 1인 경우는 1을 반환하고 그 이외의 경우는 n-1을 반환하면 되는 것이다. 

코드로 작성하면 다음과 같다.

<RecursiveFactorial.c>

2-2 재귀의 활용

재귀의 또다른 예로 피보나치 함수가 존재한다. 피보나치의 경우 0 1 1 2 3 5 8 13 21....로 1번째와 2번째를 제외하고 전 수와 전전 수를 합하여 현재의 수를 만드는 것이다. 이를 코드 적인 관점에서 생각하면 n이 1인 경우는 0, 2인 경우는 1로 설정하고 그 외의 경우는 n-1번째 수+ n-2번째 수로 하면 된다. 코드로 작성하면 다음과 같다.

<FibonacciFunc.c>

<실행결과>

앞선 포스팅에서 다루었던 이진 탐색의 경우 반복문을 통해 작성하였다. 이 또한 방금 배운 재귀를 이용하여 작성할 수 있다. 반복문에서는 while(first <= last) 의 조건을 통해 구현하였으니 이를 탈출 조건으로 작성하면 된다.

소스코드로 나타내면 다음과 같다.

<RecursiveBinarySearch.c>

<실행결과>

다만 이진탐색의 경우 중복으로 호출하는 구간이 존재하므로 코드의 시간 복잡도의 측면에서는 비효율적이다.

하노이 타워: The Tower of Hanoi

재귀함수의 또 다른 예시로 하노이 타워가 있다. 하노이 타워란 다음의 사이트에서 확인하길 바란다.

어쨌든 우리가 알아야 할 것은 원반은 한 번에 하나만 옮길 수 있고 작은 원반 위에 큰 원반이 놓여서는 안 된다는 것이다. 이를 자세하게 살펴보면 하노이 역시 일련의 과정을 반복하므로 재귀를 통해 구현할 수 있다는 것을 알 수 있다.

간단하게만 알아보아도 될 예시이므로 바로 소스코드를 보인다.

<HanoiTowerSolu.c>

<실행결과>

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

시간 복잡도는 속도에 관한 것이며 공간 복잡도는 메모리 사용량에 관한 것이다. 시간 복잡도는 연산 횟수로 구한다.

데이터의 개수가 n이하는 알고리즘 A가 유리하고 n이상은 알고리즘 B가 유리한것을 확인할 수 있다.
따라서 상황에 맞게 적절한 알고리즘을 택해야 한다. 다음의 코드를 살펴보자.

이 경우 최악의 시간복잡도는 O(N)이다. 최선, 평균, 최악이 있지만 최악을 기준으로 잡는다.
이번에는 이진 탐색(Binary Search)알고리즘을 보자. 순차 탐색에 비해 좋은 성능을 내지만 정렬이 되어있어야 한다는 제약 조건이 존재한다.

이진탐색 (Binary Search)

이진탐색을 먼저 그림으로 나타내면 다음과 같다.

이진탐색의 코드는 다음과 같다.

이 경우 최악의 시간 복잡도는 O(logN)이다.

각 빅 - 오 표기법들의 성능 비교

각 빅-오 표기법들의 성능은 다음과 같다.

순서대로 O(1) < O(logN) < O(N) < O(NlogN) < O(𝑁^2) < O(2^N) < O(N!) 이다.