다크 엔지니어

LinkedList 를 이용하여 선형 Queue를 구현해 보았다. 배열을 이용한 큐의 경우 배열 Buffer Size 의 제약을 받기 때문에 원형으로 만들어도 제약이 있다. Linked List 를 이용하면 크게 제약에 어느정도 벗어날 수 있다. 또한 Select 기능을 넣으면 중간에 삽입또한 매우 간편하다. 단점은 구현이 배열방식보다는 포인터라 조금 까다롭고.. 결국 Queue Buffer 가 늘어날수록 Heap Memory 영역을 할당하기 때문에 메모리의 부담은 여전히 존재한다. #include #include typedef struct Node { unsigned int data; struct Node *link; void SetNode(int nData) { data = nData; link = ..

Circular Queue 는 원형 큐로 일반적인 선형 큐의 단점을 보완한 방식이다. 선형 큐의 단점은 front가 증가하여 Size 에 도달했을때 다시 빈 공간을 활용할 수 없다는 단점이 있었다. 원형 큐에서는 원형으로 배열 요소를 접근하게 하여 빈 공간에 다시 재 할당할 수 있게 한다. 이런 원형큐의 장점이 있는 반면 결국 한정된 사이즈 안에서만 가능하다는 단점이 존재한다. LinkedList 로 구현하면 이러한 크기제한이 풀리게 된다. 원형 큐의 구현은 (rear + 1) % QUEUE_SIZE 의 방식을 사용하게 되는데 결국 rear 과 front 가 계속 증가해도 QUEUE_SIZE 로 나머지를 구하기 때문에 결국 QUEUE_SIZE 에 한정된 요소 안에서 반복되게 된다. 본인은 배열의 0번째를..

Queue 를 구현해 보았다. Queue 는 FIFO 구조로 가장 먼저들어온 요소가 가장 먼저 나가게 된다. 그렇다보니 주로 Buffer 에서 자주 사용된다. Buffer 는 먼저 들어온 요소를 먼저 처리해야 하기 때문이다. 펌웨어의 경우 Task ISR 에서 Queue 라는 buffer 를 생성하여, 여러 Interrupt 에 따른 Signal 이 발생하였을 때 여러 Signal 을 Queue Buffer 에 저장해 두어 처리해 나아간다. 그렇게 해당 Task 는 Signal 을 받아 wait_Sig 에서 탈출하여 해당 Task 의 루틴을 동작하게 된다. 일반적인 Queue 의 경우 단점은 rear 이 메모리 끝에 도착했을 때, 데이터가 넉넉히 비어있음에도 불구하고 더 이상 삽입 할 수 없는 상황이 벌..

병합정렬을 구현해 보았다. Quick 정렬과 비슷하게 분할을 통해 정렬해 나아간다. 시간복잡도는 nlogn 으로 Quick 과 비슷한 수준이다. Quick 의 단점인 Pivot 설정에 따라 최악의 경우 O(N^2 ) 이 되는 경우가 있을 수 있었지만 Merge 의 경우 무조건 절반으로 나누기 때문에 항상 O(NlogN) 을 갖는 장점이 있다. 정렬 알고리즘 중 가장 효율적인 방법이라고 볼 수 있다. 단점을 보자면 아래에서 보다시피 Tempdata 라는 메모리를 할당하게 된다. 그러다 보니 매우 광범위한 data 인경우 혹은 메모리를 할당 할 수 없는 상황에서는 적합하지 않을 수 있다. 그럴 경우에는 오히려 Quick 방식이 적합할 수 있다. 아래 사진과 같이 아주 작은 요소부터 시작한다. 이는 재귀함수를..

Quick Sort 는 시간복잡도가 N log N 으로 Select, Bubble의 N^2 에 비해 확실히 빠르다. Quick Sort는 Pivot 이라는 기준점을 기준으로 Left Right 에서 Pivot 으로 이동하면서 정렬하는 방식이다. 기준점인 Pivot을 선택하는데 있어서 첫 번째, 중간, 마지막, 랜덤 선택을 할 수가 있다. 본인은 중간을 선택하여 코딩을 해보았다. 한가지 방법을 알면 모두 적용이 가능하다. L의 경우 Pivot 보다 큰 요소를 찾으며, 못 찾을 경우 L 을 증가시키며 Pivot과 R 에게 접근한다. 반대로, R의 경우 Pivot 보다 작은 요소를 찾으며, 못 찾을 경우 R을 감소시키며 Pivot과 L 에게 접근한다. L 이 먼저 Pivot에 접근하면 범위를 늘리기 위해 R을..

Select Sort 에 이어서 Bubble Sort 를 구현해 보았다. Bubble Sort 는 말그대로 Bubble 처럼 n, n+1 을 Compare 하여 Sort 한다. 본인은 오름차순 정렬을 하여 첫 번째 for 문 이 큰 수 에서 점차 줄어드는 형식이다. 그 이유는 이중 for문을 다돌면 오름차순 이므로 n, n+1끼리 비교하여 가장 큰 수는 -> 방향으로 이동하게 된다. 그래서 첫 번째 for 문은 하나씩 줄여간다. 설명에서 느끼다 싶이 시간복잡도가 높다.. Select Sort 보다도... 장점을 말하자면 구현이 비교적 간단하다. Select Sort 와 비슷한 구현정도랄까 단점은 Select Sort 보다도 복잡도가 높으며, 그렇게 실용성이 있는 방식은 아니다. 아래는 Visual Stu..

이중 연결 리스트를 C언어로 구현해 보았다. LinkedList 는 stack, queue 에 비해 유연하다. 유연하다는 것은 중간에 삽입이 간편하다는 것이다. 주로 펌웨어에서 Taks Contorl Block 에서 사용된다. context swiching 이 일어날 때 TCB 는 Task 를 Double LinkedList 로 관리하고 있다. Head 를 통해 List 를 관리하기 때문에 접근성이 좋다. 하지만, 노드가 늘어날 수록 메모리를 추가해 줘야 하기 때문에 Task 의 수가 많아진다면 당연히 메모리에 부담이 된다. 펌웨어에서 메모리가 늘어나면 매우 치명적이라... 후 #include #include #include typedef struct listNode { struct listNode *l..

Select Sort 를 구현해 보겠다. 선택정렬은 오름차 정렬 시 한가지를 Select 하여 선택된 값과 최소값을 찾아 Swap 하는 방식이다. 장점은 비교적 구현이 간단하며 Bubble Sort에 비해 복잡도가 빠르다. 하지만 Sort Size가 커질수록 느려진다는 단점이 있다. #include #define DATA_SIZE 10 int main(void) { int data[DATA_SIZE] = { 10, 21, 41, 31, 2, 5, 9, 26, 27, 29 }; int i, j, temp, tempValue; for (i = 0; i < DATA_SIZE -1; i++) { tempValue = i; for (j = i + 1; j < DATA_SIZE; j++) { if (data[tem..

자료구조인 Stack 에 관하여 코딩을 해보았다. Stack 은 보통 History 나 보관용에 자주 사용된다. 펌웨어 분야에서는 context switching 시 task 를 switching 할 때 stack 영역에 옮겨 다시 가져가는 작업이 필요한데 그때 도 사용이 된다. #include #include #define STACK_SIZE 7 typedef struct stack { int _stack[STACK_SIZE]; int top; }Stack; Stack *StackCreate() { Stack *q = (Stack*)malloc(sizeof(Stack)); q->top = -1; return q; } bool Empty(Stack *q) { if (q->top < 0) return 1;..