제 44강) 정렬 알고리즘 - 셀 정렬 오늘은 정렬 알고리즘의 마지막 시간으로 "셀 정렬(Shell sort)"에 대해서 알아봅니다. 셀 정렬은 삽입 알고리즘을 보완한 알고리즘입니다. 셀 정렬이란 (사진 출처 : 위키백과 - 셸 정렬) 셀 정렬은 "Donald Shell(도널드 셀)"이 고안해낸 알고리즘으로 삽입 정렬을 보완한 알고리즘입니다. 먼저 데이터를 여러 분류로 나누어 삽입정렬을 진행합니다. 요런식으로 일정 구간을 정하여 각각의 분류(그룹)를 만들어서 해당 분류 내에서 정렬을 시킵니다. 위에서 3개의 분류로 나뉜 값들을 각각 분류를 기준으로 정렬을 시켰습니다. 이렇게 정렬된 배열을 더 낮은 개수의 분류로 나눕니다. 이제 한 번 더 분류를 기준으로 정렬을 시킵니다. 이 정도까지 하면 대략 가장 큰 ..
제 43강) 정렬 알고리즘 - 힙 정렬3 오늘은 정렬 알고리즘의 여섯 번째 시간으로 "힙 정렬"에 대해서 알아봅니다. 드디어 이전에 배운 것들을 가지고 힙 정렬을 시도합니다. 힙(Heap) 정렬이란 힙은 크게 "Max heap"과 "Min heap"으로 나뉩니다. "Max heap"(왼쪽)의 경우에는 가장 큰 요소가 맨 위에 올라와 있고, "Min heap"(오른쪽)의 경우에는 가장 작은 요소가 맨 위에 올라와 있습니다. 이렇게 1차적으로 정렬된 힙에서 맨 위의 요소(부모)를 하나씩 제거합니다. 그리고 맨 마지막 요소를 맨 위로 올립니다. 제거한 요소는 새로운 배열에 하나씩 차곡차곡 쌓습니다. 이렇게 바뀐 힙을 다시 재정렬 합니다. 이렇게 재정렬 되어진 힙에서 다시 맨위의 요소를 제거하여 이 과정을 계속..
제 42강) 정렬 알고리즘 - 힙 정렬2 오늘은 정렬 알고리즘의 세번째 시간으로 "삽입 정렬"에 대해서 알아봅니다. 기본적으로 삽입 정렬은 배열에서 사용합니다. 오늘은 힙(Heap)에 대해서 알아볼겁니다. 힙(Heap) 이란 힙은 지난 시간에 배운 "이진트리(binary tree)" 중에서도 "완전 이진트리(complete binary tree)"를 기반으로 한 자료구조입니다. 자료 구조 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, �� ko.wikipedia.org 힙은 다음과 같은 조건을 만족합..
제 41강) 정렬 알고리즘 - 힙 정렬1 오늘은 정렬 알고리즘의 세번째 시간으로 "삽입 정렬"에 대해서 알아봅니다. 기본적으로 삽입 정렬은 배열에서 사용합니다.오늘은 정렬 알고리즘의 여섯 번째 시간으로 "힙 정렬"에 대해서 알아봅니다. 힙정렬에 대해서 알기 전에 우리는 "이진 트리"를 먼저 선행학습해야합니다. 그럼 "힙 정렬"의 첫 시간으로 이진 트리부터 알아봅시다. 트리란? 이진트리를 알아보기 전에 트리(Tree)부터 알아봅시다. 트리란 위와 같이 트리형태(나무모양)의 그래프의 일종으로 각각의 요소를 노드라고 칭하고, 여려개의 노드가 한 노드를 가리킬 수 없는 구조로 되어있습니다. 최상단에 있는 노드를 루트 노드(Root Node)라고 합니다. 맨 아래의, 더 이상의 연결된 요소가 없는 노드를 단말 노..
제 40강) 정렬 알고리즘 - 퀵 정렬 오늘은 정렬 알고리즘의 다섯번째 시간으로 "퀵 정렬"에 대해서 알아봅니다. 기본적으로 퀵 정렬은 배열에서 사용합니다. (Quick Sort라고 불립니다.) 퀵 정렬이란 (사진 출처 : 위키 백과 - 퀵정렬) 퀵 정렬은 말 그대로 퀵(Quick), 빠른 정렬입니다. 퀵 정렬은 "분할 정복(Divide and conquer)" 라는 것에 기반한 알고리즘인데요. 말이 어렵지 사실상 합병 정렬의 기본원리를 따릅니다. 퀵 정렬은 "피벗" 이라는 임의의 기준값을 잡게 됩니다. (이 기준값에 따라서 성능이 좌우됩니다.) 이 임의의 값을 기준으로 큰 값은 피벗의 오른쪽으로, 작은 값은 왼쪽으로 정렬하게 됩니다. 여기서 이동된 값을 다시 오름차순 또는 내림차순으로 정렬하기 위해서 ..
제 39강) 정렬 알고리즘 - 합병 정렬 오늘은 정렬 알고리즘의 네번째 시간으로 "합병 정렬"에 대해서 알아봅니다. 기본적으로 합병 정렬은 배열에서 사용합니다. (Merge Sort라고 불립니다.) (합병 정렬 혹은 병합 정렬이라고 불립니다.) 합병 정렬이란 (사진 출처 : 위키 백과 - 합병 정렬) 합병 정렬은 배열을 계속 쪼개어 최소 단위인 2개일때 선행적으로 정렬을 한 뒤에 다시 합병하여 정렬, 합병하여 정렬을 반복하는 정렬방식입니다. 일단 배열을 원소의 크기가 최대 2개가 될 때까지 쪼갭니다. 이 쪼개지는 과정을 크게 "왼쪽 부분"과 "오른쪽 부분"으로 구분할 수 있습니다. 이렇게 9와 11은 왼쪽으로 2번 나뉘어진 부분이 되고 8은 왼쪽으로 한 번, 오른쪽으로 한 번 나뉘어진 부분이 되며, 2와..
제 36강) 정렬 알고리즘 - 버블 정렬 오늘은 정렬 알고리즘의 첫 시간으로 "버블 정렬"에 대해서 알아봅니다. 기본적으로 버블 정렬은 배열에서 사용합니다. 버블 정렬이란 (사진 출처: 위키 백과 - 거품 정렬) 버블 정렬은 구현하기가 가장 쉽지만 성능을 기대하기 어려운 정렬입니다. (실질적으로 안쓰는 정렬 중 하나) 버블 정렬은 해당 인덱스와 그 다음 인덱스와의 크기를 비교하여 바꾸는 정렬로 결과적으로 한 사이클이 지날때 마다 가장 큰 인덱스의 값은 맨 뒤로 옮겨집니다. 위의 그림에서 첫 번째 사이클에서 이미 가장 큰 수인 11이 맨 뒤로 옮겨집니다. 그렇기 때문에 두 번째 사이클에서는 11을 제외한 4개의 숫자를 가지고 다시 정렬을 합니다. 그렇기 때문에 버블 정렬의 비교 횟수는 T(n) = n(n ..
제 37강) 정렬 알고리즘 - 선택 정렬 오늘은 정렬 알고리즘의 두번째 시간으로 "선택 정렬"에 대해서 알아봅니다. 기본적으로 선택 정렬은 배열에서 사용합니다. 선택 정렬이란 (사진 출처 : 위키백과 - 선택 정렬) 선택 정렬 또한 버블 정렬과 마찬가지로 성능을 기대하기 어려운 정렬 중 하나입니다. 또한 구현하기도 어렵지 않은 정렬입니다. 매 사이클마다 배열에서 가장 큰 수를 찾습니다. 그렇게 찾은 큰 수를 맨 뒤에서 사이클의 반복횟수만큼 뺀 위치의 원소와 자리를 바꿉니다. (그 이유는 첫 사이클을 제외한 사이클에서는 맨 뒤에있는 수는 이미 정렬이 끝난 가장 큰 수이기 때문입니다.) 사실 위의 과정은 상당히 간략화 되었지만 자세히 들여다 보겠습니다. 선택 정렬은 각 사이클마다 위의 과정처럼 최대 수를 찾..
제 38강) 정렬 알고리즘 - 삽입 정렬 오늘은 정렬 알고리즘의 세번째 시간으로 "삽입 정렬"에 대해서 알아봅니다. 기본적으로 삽입 정렬은 배열에서 사용합니다. 삽입 정렬이란 (사진 출처 : 위키 백과 - 삽입 정렬) 삽입 정렬은 매 사이클마다 해당 원소가 들어가야할 위치를 찾아서 삽입하기위해 나머지를 뒤로 미루는 정렬입니다. 매 사이클마다 차례대로 변수를 선택합니다. 그리고 해당 변수를 임시의 변수공간에 두고 해당 변수의 앞에 있던 변수들과 비교를 해가며 위치를 찾아갑니다. 이렇게 본다면 선택정렬과 유사합니다. 단지 선택정렬은 위치는 정해져 있고 변수값을 찾아가지만, 삽입정렬은 변수값은 정해져있고 위치를 찾아간다는 점이죠. (알고리즘 시험보기 위해서 저는 위와 같이 외웠습니다.) 이렇게 되어 삽입 정렬..
제 35강) 라이브러리 함수3 - 날짜 및 시간 오늘은 "강의에서 다루지 않았던"의 다섯번째 시간입니다. 이번 시간에는 라이브러리 함수3인 날짜 및 시간 라이브러리에 대해서 다뤄보려고 합니다. C언어에서 제공하는 "날짜 및 시간" 라이브러리는 time.h를 포함하면 사용이 가능합니다. 자료형 time.h 에는 다음과 같이 4개의 자료형을 선언하고 있습니다. 이름 자료형 원형 기능 clock_t Tick 수를 샐 수 있는 시계 전용 자료형(시스템 시간을 잴 때 사용) size_t unsigned int 부호 없는 정수 자료형으로 바이트 단위의 크기를 나타낼 때 사용 time_t 시간을 나타내기 위한 자료형 struct tm 시간을 받아서 저장하는 구조체 여기서struct tm을 좀더 자세히 봅시다. 멤버..
