Taking baby-developer steps

우선순위 큐의 필요성 우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용되고 있다. 우선순위 큐는 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우선순위 큐와 큐의 차이점 일반적인 형태의 큐는 선형적인 형태를 가지고 있지만, 우선순위 큐는 트리(Tree) 구조로 보는 것이 합리적이다. 일반적으로 우선순위 큐는 최대 힙을 이용해 구현한다. (+우선순위 큐는 '완전 이진 트리'를 이용해서 구현한다.) 최대 힙(Max Heap) 최대 힙은 모든 부모 노드가 자식 노드보다 값이 큰 완전 이진 트리를 의미한다. 최대 힙의 루트 노드는 전체 트리에서 가장 큰 값을 가진다는..

이진트리의 구현 및 순회 이진트리의 구현 방법과 순회의 개념에 대해서 이해한다. 이진 트리를 C언어로 구현하는 방법에 대해서 학습한다. 이진 트리 이진 트리는 부모가 왼쪽 자식, 오른쪽 자식을 가질 수 있다는 점에서, 포인터를 이용해서 구현하면 효과적인 데이터 관리가 가능하다. 이진트리 구조체(노드) 만들기 / 초기화 함수 #include #include typedef struct Node{ int data; //실제로는 이것보다 많은 양의 데이터가 들어가는 경우가 많다. struct Node *leftChild; struct Node *rightChild; }Node; //특정한 노드를 초기화하는 함수 Node* initNode(int data, Node* leftChild, Node* rightChi..

이진트리 이진 트리의 필요성과, 이진 트리와 관련한 다양한 용어를 이해한다. 트리 트리(Tree)는 나무의 형태를 뒤집은 것과 같은 형태의 자료구조이다. 루트 노드와 리프 노드 트리에서 가장 위에 존재하는(가지가 뻗어나가기 시작하는) 노드를 루트노드, 가장 아랫단 즉 끝에 있는 노드들을 각각 리프노드라고 부른다. 부모 노드, 자식 노드, 형제 노드 트리에서 각각의 노드는 부모-자식 관계를 가지며, 부모가 같은 노드들은 형제노드라고 부른다. 트리의 길이, 깊이, 높이 트리에서 길이(Length)란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다. 깊이(Depth)란 루트 노드에서 특정 노드까지의 길이를 의미한다. 트리의 높이(Heifht)란 루트 노드에서 가장 깊은 노드까지의 길이를 말한다. ..

기수정렬 기수정렬(Radix Sort)는 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘이다. 각 데이터를 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도를 가진다. 그런데, 자릿수가 10개를 넘어가야 억단위가 넘어가기 때문에, 왠만해선 D는 그렇게 큰 값이 아닐 경우가 많다. 따라서 O(DN)은 사실상 O(N)의 시간복잡도를 가진다고 볼 수 있을 정도이므로, 계수 정렬만큼 처리속도가 빠르다. 계수 정렬보다 약간 더 느릴 순 있으나, 숫자가 매우 큰 상황에서도 사용할 수 있으므로, 계수정렬보다 활용할 수 있는 상황이 더 다양하다. 기수정렬의 원리 다음과 같은 원소 배열이 있을때, 기수 정렬은 다음과 같이 수행된다. 먼저 정렬할 배열의 '원소의 1의 자리를 기준..

계수정렬 계수정렬(Counting Sort)는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘이다. 각 데이터를 크기를 기준으로 바로 분류하므로, O(N)의 시간 복잡도를 가진다. 퀵 정렬이나 다른 정렬 알고리즘에 비해서 많은 메모리(값의 크기만큼 인덱스를 모두 가져야하므로)를 요구하는 한편, 빠르게 동작한다. 상당히 많은 메모리 소모가 있기 때문에 크기 제한(정렬하고자하는 Data가 가질 수 있는 가장 큰 값에 대한)이 존재해야 한다. 계수정렬 구현하기 #define _CRT_SECURE_NO_WARNINGS #include #define MAX_VALUE 10001 //정렬할 data가 가질 수 있는 가장 큰 값 int n, m; int a[MAX_VALUE]; int main(){ scanf("..

퀵정렬 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로 평균적으로 O(NlogN)의 시간 복잡도를 가진다. 원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리이다. 각각의 부분 배열들이 각자 정렬을 수행하는 점에서, 퀵정렬의 이러한 구조는 완전 이진트리와 흡사하다. 완전 이진 트리 형태는 컴퓨터 공학에서 가장 선호하는 이상적인 형태이다. 퀵정렬 - 배열선언 #define _CRT_SECURE_NO_WARNINGS #include #define SIZE 1000 int a[SIZE]; int swap(..

선택정렬 선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로, O(N^2)의 시간 복잡도를 가진다. 선택정렬 - 배열 선언 #define _CRT_SECURE_NO_WARNINGS #include #include #define SIZE 1000 int a[SIZE]; int swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } //정렬은 두개의 원소의 위치를 바꾸는 경우가 많으므로, 미리 swap 함수를 만들어 두는게 현명하다. 선택정렬 수행하기 int main(void){ int n, min, index; // min = 한번 검색 할 때마다 발견되는 가장 작은..

큐 큐(Queue)는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료 구조(Data Structure)이다. 이러한 특성 때문에 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용된다. 큐는 크게 2가지 함수로 구성된다. push : 큐에 데이터를 넣는다. pop : 큐에서 데이터를 빼낸다. C언어를 이용해 큐 자료구조를 직접 구현해 보고, 큐 자료구조의 개념과 활용 방법을 이해한다. 큐는 다음과 같은 명령어 세트가 존재할때, 그림과 같이 동작한다. 큐의 구현 큐(Queue)는 배열을 이용한 구현 방법, 연결리스트를 이용한 구현 방법이 있다. 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편이다. 먼저 배열을 이용한 구현 방법은 다음과 같다. 배열을 이용한 큐 구현 큐의 선언 #include #define SI..

스택을 활용한 계산기 만들기 스택을 활용해 계산기를 만들어 본다. 중위 표기법 중위 표기법이란 일반적으로 사람이 수식을 표기할 때 사용하는 표기 방법이다. 중위 표기법의 예시 : 7 * 5 + 3 (2개의 피연산자 사이에 연산자가 들어간다.) 후위 표기법 후위 표기법이란 컴퓨터가 계산하기에 편한 수식의 형태이다. 후위 표기법에서 연산자는 뒤쪽에 위치한다. 후위 표기법의 예시 : 7 5 * 3 + 스택을 활용해 수식을 계산하는 방법 수식을 후위 표기법으로 변환한다. 후위 표기법을 계산하여 결과를 도출한다. 스택 구현하기 -스택의 정의 #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef struct Node { char data[100]; ..

스택(Stack) 스택 자료구조의 개념과 활용 방법에 대해서 이해한다. C언어를 이용해 스택 자료구조를 직접 구현해 본다. 스택은 수식계산, 다양한 알고리즘 분야 등에서 활용도가 높기 때문에, 반드시 숙지해야 후에 나오는 심화 과정에서 어려움이 없다. 스택은 한쪽으로 들어가서 한쪽으로 나오는 자료 구조이다. 이러한 특성 때문에 수식 계산 등의 알고리즘에서 다방면으로 활용 되므로 반드시 알고 있어야 하는 자료구조이다. 스택에 데이터를 넣는 push함수와 스택에서 데이터를 빼내는 pop 함수를 이용한다. '리스트'의 형태를 가지기 때문에, 마치 배열처럼 표현 할 수 있다. 연결리스트 혹은 배열을 이용해 구현 가능하다. 스택의 구현 스택은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어져..