tmxklab

1. 계수 및 기수 정렬 개념 1) 계수 정렬 각 원소를 사이에 비교하지 않는 정렬이며 안정성(stable)을 가짐 임시작업에 사용되는 메모리를 필요로 함 (각 숫자를 counting하여 누적시킬 배열과 정렬된 배열) 정렬할 배열의 원소와 숫자를 counting하여 누적시킨 후 그 값들을 정렬된 배열의 인덱스로 사용 2) 기수 정렬 자리 수를 비교해서 정렬하는 방식 가장 낮은 자리 수부터 비교하여 정렬 수행 (비교 연산을 하지 않음) 기수정렬이 올바르게 동작되기 위해 각 자리에 사용될 정렬 알고리즘이 안정적이어야 함 2. 계수 및 기수 정렬 예제 1) 계수 정렬 2) 기수 정렬 3. 계수 및 기수 정렬 특성 1) 계수 정렬 ① 장점 $n$이 $k$보다 클 경우 $O(n)$의 시간 복잡도를 가짐 평균적인 ..

1. 힙 정렬 개념 자료구조인 힙(Heap)의 사용하여 정렬을 수행하며 여기서는 최대 힙을 사용 입력 자료들을 최대 힙으로 구성(Build-Max-Heap : 정렬되지 않은 입력 자료들로부터 최대 힙을 만듦) 최대 힙을 구성하는 과정에서 힙 특성을 유지하는 역할이 포함되어야함(Max-Heapify : 힙 특성 유지) 구성된 최대 힙에서 Root부터 차례대로 힙에서 꺼내어 저장(Heap-Sort : 배열을 내부 정렬함) ※ 힙(Heap) 추가 개념 힙(Heap) : 완전 이진 트리이며 최대 힙과 최소 힙이 존재 완전 이진 트리(Complete binary tree) : 각각의 노드가 최대 두 개의 자식 노드를 가지며 자식 노드를 추가할 때 왼쪽부터 차례대로 채우는 트리 노드의 높이 : 해당 노드에서 리프에..

1. 합병 정렬 개념 존 폰 노이만(John von Neumann)이 개발한 정렬 알고리즘 비교 기반 정렬이며 분할 정복을 통해 정렬을 수행함 일반적인 방법으로 구현할 때 안정 정렬에 속함 임시로 저장할 리스트나 배열이 필요로 함 입력 자료들을 원소가 하나가 될 때까지 분할한 후, 합치는 과정에서 비교하여 정렬 수행 * 합병 정렬은 다음과 같은 분할 정복을 통해 정렬을 수행함 ① 분할 : 정렬할 $n$개 원소의 배열을 $n/2$개씩 부분 수열 두 개로 분할 ② 정복 : 합병 정렬을 이용하여 두 부분 배열을 재귀적으로 정렬 ③ 결합 : 정렬된 두 개의 부분 배열을 병합하여 정렬된 배열 하나로 만듦 2. 합병 정렬 예제 3. 합병 정렬 특성 1) 장점 안정적인 정렬 알고리즘 자료구조를 리스트로 구성하면 링크..

1. 퀵 정렬 개념 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발한 정렬 알고리즘 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하며 불안정 정렬 평균적으로 매우 빠른 수행 속도를 자랑하지만 정렬을 위해 $O(\lg n)$만큼의 메모리를 필요 분할 정복 방법을 통해 정렬 수행 입력 자료들 중 하나의 요소(이를 피벗(pivot)이라 함)를 선택한 후 피벗을 기준으로 피벗보다 작은 요소와 큰 요소들을 나눔 나눠진 2개의 입력 자료들은 위와 같은 방식으로 분할되지 않을 때까지 반복 * 퀵 정렬은 다음과 같은 분할 정복을 통해 정렬을 수행함 ① 분할(partition함수) : 배열 A[p, ..., r]을 두 부분 배열 A[p, ..., q-1]과 A[q+1, ...

1. 삽입 정렬 개념 손안의 카드를 정렬하는 방법과 유사(새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치에 삽입) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 key값은 2번째 인덱스부터 시작되며, key값이 자료의 길이만큼 이동되었을 때 정렬이 완성됨 2. 삽입 정렬 예제 3. 삽입 정렬 특성 1) 장점 안정한 정렬 방법(바로 옆의 데이터와 비교하기 때문) 자료의 수가 적을 경우 알고리즘 구현이 매우 간단 이미 정렬되어 있는 경우나 자료의 수가 적은 정렬에 매우 효율적 2) 단점 비교적 많은 레코드들의 이동을 포함 자료의 수가 많고 자..

※ 재귀트리(Recursion Tree Method) → 좋은 추측식을 고안해내기 위한 직접적인 방법(치환법으로 추측이 불가능할 때) → 각 노드가 재귀호출되는 하위 문제 하나의 비용을 나타냄 → 레벨당 비용의 집합을 얻기 위해 트리의 각 레벨마다 그 비용을 합한 후, 재귀의 모든 레벨에서의 총 비용을 결정하기 위해 모든 레벨당 비용을 합함 Example 1) 1단계 : 재귀트리를 이용하여 추측식을 구함 ■ Recurrence : $T(n) = 3T(\left\lfloor n/4 \right\rfloor) + \Theta(n^2)$ 1) 위 Recurrence식 수정 $T(n) = 3T(n/4) + cn^2$ // 내림과 올림은 그리 중요하지 않으므로 제거, $c > 0$사용 2) 재귀트리 사용 $n$이..

※ 치환법 2단계 ① 해의 모양을 추측한다. ② 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다. Example) ■ Recurrence : $T(n) = 2T(\left\lfloor n/2 \right \rfloor) + n$ ▶ Guess : $T(n) = O(n \lg n)$ ▶ Prove by induction : $T(n) \le c \cdot n \lg n$, 어떤 상수 $c>0$에 대해 만족해야 함 $O(g(n)) =$ {$f(n): n_{0} \le n, 0 \le f(n) \le c \cdot g(n)$} ▶ Inductive assumption : $n < k$가 참이면, (즉, $T(n) \le c\cdot n\lg n $) $n=k$ 또한 참임을..

1. 점화식(Recurrence) 더 작은 입력에 대해 자신의 값으로 함수를 나타내는 방정식 또는 부등식 분할정복 알고리즘의 수행시간을 자연스럽게 표현 가능 ex) $T(n)=T(n-1)+\Theta(1)$ 해석 : 각 재귀 호출에 걸리는 시간 ($T(n)$)은 "상수시간($\Theta(1)$) + 새로운 재귀 호출이 필요한 시간($T(n-1)$)" $T(n) = a\cdot T(n/b)+f(n)$ 해석 : 각 부분문제($a\cdot T(n/b)$)는 크기가 원래 문제의 $1/b$이고 분할과 결합 과정은 합쳐서 $f(n)$시간 걸림 2. 점화식을 푸는 방법 1) 치환법(substituition method) 한계를 추측한 후 그 추측식이 옮음을 증명하기 위해 귀납법 사용 문제가 쉬운 경우에만 적용(단점)..

1. 알고리즘 설계 1) 점진적 방법(Incremental design) 반복적(Iterative) ex) insertion sort 2) 분할정복(Divde and Conquer) 재귀적(Recursive), 재귀호출 방법으로 해결 -> Recurrence(점화식) ex) merge sort 주어진 문제를 풀기 위해 자기자신을 재귀적으로 여러번 호출함으로써 밀접하게 연관된 부분 문제를 다룸 즉, 문제의 범위를 더 작은 단위로 쪼개어 해결한 뒤 다시 합쳐 문제를 해결하는 방법 3) 분할정복 세 가지 단계 분할(Divide) : 현재의 문제를 같은 문제를 다루는 다수의 부분문제로 분할 정복(Conquer) : 부분문제를 재귀적으로 풀어서 정복, 충분히 작아지면 직접적인 방법으로 해결 결합(Combine) ..

1. 알고리즘 정의 어떤 입력을 어떤 출력으로 변환하는 일련의 잘 정의된 계산과정 알고리즘은 원하는 입/출력 관계를 구하기 위한 구체적인 계산과정을 설명 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 타당하다(correct)고 함 2. 점근적 표기법(Asymptotic Notation) 알고리즘의 점근적 효율성 : 입력 크기가 극한으로 증가할 때 어떤 알고리즘의 수행 시간이 어떻게 증가하는지 관심 알고리즘의 점근적 수행시간은 자연수들의 집합에 한해서 N={0, 1, 2,...}인 함수들로 정의 점근적 표기는 주로 알고리즘의 수행시간을 나타내기 위해 사용 1) $O$-Notation(Big-oh) Worst case 점근적 상한, $f(n) = O(g(n))$ 정의 : $O(g(n))$ $=..