DKU/알고리즘 및 실습

정렬 알고리즘에는 여러가지 타입이 존재한다.정렬에는 요소들이 순차적으로 증가하게끔 만드는 오퍼레이션만 사용되며, 이는 요소의 쌍을 비교하면서 이루어진다. Exchange Sorting - Bubble Sort, Quick SortInsertion Sort Selection Sorting - Selection Sort, Heap SortMerge SortDistribution Sort - Bucket Sort, Radix Sort 정렬의 하한(lower bound)하한은 주어진 입력을 정렬하기 위해 필요한 최소 계산 작업을 의미한다. 비교 기반 정렬 알고리즘의 경우, 이 최소 비교 횟수는 보통 $\Omega(n\lg n)$이다. 여기서 어떤 비교 기반 정렬이 수행하는 비교 과정을 추상화한 것을 결정 트리 ..

Quick Sort최악의 경우 실행시간은 $O(n^2)$이다.평균적으로, 실행시간은 $O(n\lg{n})$이다. 이때의 숨겨진 상수 계수는 다른 알고리즘보다 작아서, 실제로는 매우 빠르게 동작하는 편이다. 퀵 정렬은 분할-정복 방식으로 작동한다.분할: 배열 A[q...r]을 피벗을 기준으로 두 개의 부분 배열로 나눈다. 앞 부분의 배열 A[p...q-1]의 모든 요소는 피벗 A[q] 보다 작거나 같고, 뒷 부분의 배열 A[q+1...r]의 모든 요소는 피벗 A[q]보다 크거나 같다.정복: 분할된 두 부분 배열을 재귀 호출을 통해 각각 정렬한다.결합: 퀵 정렬은 제자리 정렬이기 때문에, 두 부분 배열을 따로 결합할 필요는 없다.분할 과정은 PARTITION 이라는 절차를 이용해 이루어지며, 이 절차는 피벗..

힙은 자료구조 중 하나로, 완전 이진 트리 구조이다.힙의 높이는 루트에서 가장 깊은 리프노드까지의 경로를 나타낸다. 힙은 배열 A[1...n]으로 저장될 수 있으며,트리의 루트는 A[1] 이다.A[i]의 부모는 A[i/2] 이다.A[i]의 왼쪽 자식은 A[2i]이고, 오른쪽 자식은 A[2i + 1]이다.이진 표시의 구현은 컴퓨팅이 빠르다. 가장 큰 요소가 루트에 존재하는 max-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i)] $\geq$ A[i]이다.가장 작은 요소가 루트에 존재하는 min-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i) $\leq$ A[i]이다.힙정렬 알고리즘은 max-heaps를 사용하며, 힙은 이진트리가 아니라 k트리도 가능하다. 방금..

재귀함수는 하나 이상의 기본 사례에 의해 정의되고, 더 작은 인수를 사용하여 자기 자신으로 정의되는 함수이다. Methods for sloving recurrences: 재귀함수를 푸는 메서드Repeated Substitution Method(반복 치환) 위 재귀함수식을 어디서 많이 봤을 텐데, merge sort에서 등장했었다.반복 치환 메서드는 말 그대로 치환을 반복하면서 식을 유도해나가는 방식이다. merge sort 알고리즘은 먼저 원소가 한개 남을 때까지 배열을 쪼갠다.$T(n) = 2T(n/2) + n$의 식을 쪼개보면,$T(n) = 2(2T(n/2^{2}) + n/2) + n = 2^{2} T(n/2^{2}) + 2n$이다.한번 더 쪼개보자.$T(n) = 2^{2}(2T(n/2^{3}) + ..

거품 정렬(bubble sort)는 정렬 알고리즘의 하나로, Selection Sort 알고리즘과 유사하다.서로 인접한 두 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 거품 정렬은 첫번째 원소와 두번째 원소 → 두번째 원소와 세번째 원소 → 세번째 원소와 네번째 원소 ・・・ 처럼 인접한 두 원소를 비교하며 정렬한다. 마지막 두개의 원소의 크기를 비교하여 정렬을 마치면 1회전이 끝난 것이고, 제일 큰 원소가 맨 마지막에 위치하게 된다. 2회전을 시작할 때는 이미 정렬된 맨 마지막 원소를 제외하고 비교를 시작한다. 이렇게 회전 수가 늘어날 마다 정렬해야하는 배열에서 제외되는 원소 수가 늘어난다. i가 1부터 배열 A의 길이까지 반복하고,j가 배열A의 길이에서 i+1이 될때까지..

Gorwth of Functions: 함수의 성장함수의 행동을 한계에서 설명하는 방식을 asymptopic effciency(점근적 효율성)이라고 한다.이 방식에서는 저차항과 상수계수를 무시하고 중요한 부분에 집중하여 알고리즘의 실행시간을 나타낸다.알고리즘의 실행시간으로는 함수의 크기(알고리즘의 성능)를 비교할 수 있다. 위 사진은 $\Theta, O, \Omega$ 표기법의 그래프 예시다.각 부분에서, $n_0$의 값은 가능한 작은 값이며, 이보다 더 큰 값도 동일한 역할을 할 수 있다.여기서 역할이란, f(n)과 g(n)을 비교하는 임의의 시작점이다. (a) 빅세타(Big Θ) 표기법양의 상수 $n_{0}, c_{1}, c{2}$가 존재하며, $n_0$의 오른쪽에서 $f(n)$의 값이 항상 $c_{1..

합병 정렬(merge sort)알고리즘이란, 분할 정복(divide and conquer) 기반인 정렬 알고리즘이다.쉽게 말하자면, 더 이상 쪼개질 수 없을 정도의 단위로 쪼갠 후에, 합병하면서 정렬하는 것이다. 일단 합병 정렬 알고리즘의 실행시간은 재귀적 표현을 가지고 있기 때문에, 값을 직접적으로 알 수 없다는 특징이 있다.e.g. T(n) = T(n-1) + 2 자, 먼저 배열을 최소 단위로 먼저 쪼개는 방법이다.배열 A가 p부터 r까지의 원소를 가진다면, 그 중간값인 q를 먼저 찾는다.⌊⌋이런 기호가 보이는데, floor연산이며 안의 값보다 크지 않는 최대의 정수(내림)값을 찾는 연산이다.그리고 나눠진 배열에서의 각각 중간값을 찾는 과정을 반복한다(재귀). $n_1$에는 배열A의 처음 원소부터 중..

삽입 정렬 알고리즘은 주어진 배열의 2번째 요소부터 앞의 모든 요소들과 비교하여 알맞은 곳에 삽입시키는 알고리즘이다. 배열 A = {5, 2, 4, 6, 1, 3} 이 주어졌다고 가정하자.회색 칸은 이미 정렬이 된 원소이고, 검은색 칸은 현재 정렬해야할 key값이다. 흰색 칸은 각 단계에서 사용할 필요가 없는 원소이다.흰색 칸을 아직 정렬되지 않은 칸으로만 볼 수 있지만, 그림(c)를 보면 이미 정렬된 2, 4 또한 흰색으로 칠해져 있다. key값인 6이 5와 비교되면 바로 자리에 삽입되기 때문에 2, 4와 비교될 필요가 없다. 이처럼 삽입 정렬 알고리즘에서의 비교횟수는 불규칙적이다. 2번째 요소부터 마지막 6번째 요소까지 비교 반복을 해주면, (f)그림처럼 잘 정렬된 배열이 완성된다.나는 수도 코드 읽..

알고리즘 공부 좀 미리 해둘걸ㅠㅅㅠ 이 과목은 철저한 복습과 암기가 살 길이라는 것을 2주차에 직감했다... 진짜 행복하네수업시간에 모르는 것들이 나오면 따로 공부해서 추가적인 포스팅을 하도록 하겠슴미다. Insertion Sort: 삽입 정렬삽입 정렬 알고리즘이란 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하고 정렬하는 알고리즘이다.쉽게 말하자면, 카드 정리라고 할 수 있다. 나는 원카드 게임을 할 때 패를 받으면 오름차순으로 정렬을 한다(2, 5, 8, 9). 또 새로운 카드를 손에 넣었을 때 숫자 크기를 비교하여 알맞은 위치에 카드를 꽂아넣는다(2, 5, 7(new!), 8, 9). 이게 삽입 정렬이다.  삽입 정렬 알고리즘의 알맞게 수행..

알고리즘이란?입력을 가지고 출력을 생산하는 논리적인 계산 절차입력을 출력으로 변환하는 계산적인 단계의 절차잘 명시된 계산적인 문제를 해결하는 도구입력이란 주어진 문제의 인스턴스 즉, 처리대상을 뜻한다.출력이란 주어진 문제의 해결방법을 뜻한다. 좋은 알고리즘(정답인 알고리즘?)에는 몇가지 조건이 존재한다.모든 입력 인스턴스에 대하여 알맞은 출력과 함께 알고리즘이 멈춰야한다.따라야할 계산 절차를 정확하게 설명해야한다.좋은 알고리즘이란 당연히 주어진 문제를 해결할 수 있는 알고리즘이고, 멈추지 않거나 목표한 답과는 다른 답을 가지고 멈추는 알고리즘은 틀린 알고리즘이다.문제를 해결하는 방법 데이터 구조(data structures)를 사용하여 효율적인 알고리즘을 구현할 수 있다.데이터 구조란 데이터를 저장하고 ..