리스트 리스트는 데이터를 순서대로 나열한 자료구조이다. 리스트의 데이터는 노드(node) 혹은 요소(element)라고 하며, 가장 단순한 구조를 가진 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다. 오늘 나는 연결리스트를 직접 구현해 볼 예정이다. 연결리스트의 노드들은 다음 노드의 포인터만 가지고 있어서 1번 노드에서 3번노드에게 가려면 2번을 거쳐가야한다. [LinekdList.h - 선언] struct Node { int data; Node* nextNode; }; struct List { Node* headNode; Node* curNode; }; 일단 값과 다음 노드의 포인터를 가지고있는 Node라는 구조체와 headNode(리스트의 맨 앞 노드) 포..

큐(Queue)란? 큐도 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO : First In First Out)의 구조를 가지고 있다. 많은 예시로 은행의 대기열을 예시로 든다. 나같은 경우는 큐를 알림시스템에 사용해서 들어온 순서대로 알림이 출력되게 하거나, 들어온 순서대로 오브젝트를 재사용하는 오브젝트 풀링을 구현할때 사용했던 자료구조다. [Queue.h - 선언] #pragma once class Queue { private: int myQueue[1000] = { 0, }; int num = 0; //큐에 담긴 값의 갯수 int* firstNum = nullptr; // 첫번째 값의 포인터 public: Queue(); v..

스택(stack)은 후입선출(LIFO, Last In First Out)의 구조를 가지고있다. 스택사용의 예라고 한다면 우리가 인터넷 브라우저를 사용할때 쓰는 뒤로가기가 있다. C++의 STL, C#의 Collection에서 기본으로 구현되어있는 스택만 쓰다가 자료구조들을 한번 다시 점검&공부하는 느낌으로 스택을 직접 정말 간단하게 구현해봤다. [ MyStack.h - 선언 ] #pragma once class MyStack { private: int pointer = 0; int stack[1000] = { 0, }; public: int Count(); bool IsEmpty(); void Push(int value); int Pop(); void Clear(); }; [MyStack.cpp - 정의..

기본 버전 #define swap(type,x,y) do{type t = x; x = y; y = t;} while(0) void buuble(int a[],int n) { for (int i = 0; i i; j--) if (a[j - 1] > a[j]) swap(int, a[j - 1], a[j]); } } 기본버전은 요소-1만큼 반복문이 돌아가며 한번의 반복이 끝나 i가 1이 늘어나면, 확정 된 0번 인덱스의 자리를 제외하고(j > i까지이기 때문) 나머지 자리에서의 비교,교환이 계속 이루어진다. 다시 얘기하면 뒤에 값들이 정렬이 되어있는 상태라도 계속 비교 교환을 한다는 얘기다. 알고리즘 개선 - 1 #define swap(ty..

셸 정렬(Shell Sort)은? 단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘 도널드 셀(D.L.Shell)이 고안했다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동횟수를 줄이는 방법이다. 퀵정렬이 나오기 전까지는 가장 많이 쓰였다고 한다. 여기서 말하는 단순 삽입정렬의 장점과 단점은 장점 - 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. 단점 - 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 셸정렬은 이 단점을 해결하고 장점을 이용하기 위해 만들어졌다. 코드로 만들어보기 //배열 a와 요소의 수 n void shell(int a[], int n) { ..

단순 선택 정렬(Straight Selection Sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 배열의 첫번째부터 검색하면서 더 작은수(큰 수를 찾는다면 큰 수)가 있다면 , 스왑을 해주어 정렬을 한다. 바로 코드로 보자. void Selection(int a[], int element) { int i, j; for (i = 0; i < element - 1; i++) { int min = i; for (j = i + 1; j < element; j++) { if (a[j] < a[min]){ min = j; } } int temp = a[i]; a[i] = a[min]; a[min] = temp; } 1. 첫번째 for문은 총 요소의 -1만큼 돌려준다. 버블정렬때..