Taking baby-developer steps

퀵정렬 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는데에 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 함수를 이용한다. '리스트'의 형태를 가지기 때문에, 마치 배열처럼 표현 할 수 있다. 연결리스트 혹은 배열을 이용해 구현 가능하다. 스택의 구현 스택은 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어져..

#include #include typedef struct { int data; struct Node *prev; struct Node *next; } Node; Node *head, *tail; void insert(int data){ Node *node = (Node*)(malloc(sizeof(Node))); node->data = data; Node *cur; cur = head->next; while(cur->data next; } Node* front = cur->prev; front->next = node; node->prev = front; cur->prev = node; node->next = cur; } void removeFront(){ Node *front = head->next; ..

양방향 연결 리스트 양반향 연결 리스트의 동작 원리와 구현 방법에 대해서 학습하고, 포인터에 유의하며 구현해 본다. 양방향 연결리스트는 머리(Head)와 꼬리(Tail)를 모두 가진다. 양방향 연결리스트의 각 노드는 앞 노드와 뒤 노드의 정보를 모두 저장하고 있다. 이러한 구조의 양방향 연결 노드를, 데이터를 '오름차순'으로 저장하는 형태로 구현해 보면 다음과 같다. 양방향 연결 리스트 선언하기 #include #include typedef struct { int data; struct Node *prev; struct Node *next; } Node; Node *head, *tail; Node라고 이름지은 구조체를 만든다. 각 노드는 정수형 데이터 1개와 앞노드와 뒷노드를 가리키는 포인터를 각 2개씩..

저번 연결리스트 포스팅의 예제들에서, 모든 노드값을 출력하는 부분이 상당히 긴것을 볼 수 있는데, 이것을 다음과 같이 모든 노드값을 출력하는 함수 showAll()을 만들어 출력하도록 하면 훨씬 효율적이다. void showAll(Node *root){ Node *curr = head->next; while (curr != NULL){ printf("%d ", curr->data); curr = curr->next; } printf("\n"); } 연결 리스트의 전체 원소 메모리를 할당 해제하는 함수는 다음과 같다. void freeAll(Node *root){ Node *cur = head->next; while(cur != NULL){ Node *next = cur->next; free(cur); c..

연결리스트 연결리스트의 필요성과 쓰임새에 대해 학습한다. C언어를 활용하여 연결 리스트를 구현하는 방법에 대해서 공부한다. 연결 리스트는 데이터를 선형적으로 저장하고 처리하는 한 방법이다. 기존에 배열을 이용했을 때보다 삽입과 삭제가 많은 경우에서 효율적이다. 다만 특정한 인덱스에 바로 참조해야 할 때가 많다면 배열을 이용하는 것이 효율적이다. 연결리스트의 필요성 일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고, 나열할 수 있다. 배열을 사용하는 경우, 메모리 공간이 불필요하게 낭비 될 수 있다. 배열 기반의 리스트 데이터를 순차적으로 저장하고, 처리할 때는 배열 기반의 리스트를 다음과 같이 간단히 이용 할 수 있다. #include #define INF 10000 int arr[INF]; int..

#include #define INF 10000 int arr[INF]; int count = 0; void addBack(int data){ arr[count] = data; count++; } void addFirst(int data){ for(int i = count; i>=1; i--){ arr[i] = arr[i-1]; } arr[0] = data; count++; } void removeAt(int index){ for(int i = index; i=index; i++){ arr[i]=arr[i-1]; } arr[index] = data; count++; } void show(){ for(int i=0; i