Taking baby-developer steps

이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란, 이진 탐색이 항상 동작하도록 구현해서 탐색 속도를 극대화 시킨 자료구조이다. 이진 탐색 트리의 동작 방식 이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다. 위의 이진트리에서 37이라는 원소를 찾는 다면, 37이 루트노드(30)보다 큰 값이기 때문에, 루트노드의 왼쪽자식들은 탐색할 필요가 없다. 따라서 오른쪽 자식 중 48보다 작으므로 48의 왼쪽 자식만 탐색하면 된다. 이진 탐색 트리의 탐색 위의 예제에서 볼 수 있듯이, 이진 탐색 트리에서는 한번 확인할 때마다 탐색해야하는 원소의 개수가 절반씩 줄어든다는 점에서, O(logN)의 시간 복잡도를 가진다. 이진 탐색 트리에서, 찾고자 하는 값이 부모..

깊이 우선 탐색(DFS/Depth First Search) 깊이 우선 탐색은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘이다. 기본적으로, 전체 노드를 맹목적으로 탐색할 때 사용한다. 깊이 우선 탐색 알고리즘은 스택(Stack)자료구조에 기초한다. 빠르게 모든 경우의 수를 탐색하고자 할때 사용한다. 깊이 우선 탐색 알고리즘 탐색 시작 노드를 스택에 삽입하고 방문처리 한다. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ex) 깊이 우선탐색 알고리즘 1을 최상단 노드라고 가정하고 시작. 1과 연결된 노드..

그래프의 개념과 구현 그래프(Graph)란 사물을 정점(Vertex)와 간선(Edge)으로 나타내기 위한 도구이다. 그래프는 아래의 두 가지 방식으로 구현할 수 있다. 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식 인접 리스트(Adjacency List) : 리스트를 사용하는 방식 인접행렬(Adjacency Matrix) 2차원 배열로서 그래프를 표현한다. 무방향 비가중치 그래프와 인접 행렬 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다. 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다. 무방향 비가중치 그래프가 주어졌을 때, 연결되어 있는 상황을 인접 행렬로 출력할 수 있다. #define _CRT_SECURE_NO_WARNINGS #incl..

순차 탐색 순차 탐색(Sequential Search)은 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법이다. 찾을 문자열 깜보 인덱스 0 1 2 3 4 원소 코코 왕자 다롱 깜보 뽀랑 (인덱스 0부터 해당 원소를 찾을 때까지 하나하나 탐색한다.) 순차탐색은 데이터 정렬 유무에 상관 없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점에서 O(N)의 시간 복잡도를 가진다. 문자열 순차 탐색 구현 #define _CRT_SECURE_NO_WARNINGS #include #include #include #define LENGTH 1000 char **array; //2차원 배열(2중 포인터) int founded; //해당 값을 발견 했는지에 대한 정보 int main(void){ int..

우선순위 큐의 필요성 우선순위 큐는 '우선 순위'를 가진 데이터들을 저장하는 큐를 의미한다. 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나온다는 특징이 있어 많이 활용되고 있다. 우선순위 큐는 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등의 다양한 기술에 적용되고 있다. 우선순위 큐와 큐의 차이점 일반적인 형태의 큐는 선형적인 형태를 가지고 있지만, 우선순위 큐는 트리(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(..