이전 글에서 Heap Sort를 위해 필요한 Heap, Heapify 개념을 다루었다. Heap Sort는 배열이 주어졌을 때 다음과 같은 과정을 통해 정렬한다. ① 주어진 배열로 Max Heap을 만든다. ② Max Heapl에서 최대값(루트)를 가장 마지막 값과 바꾼다. (이때 가장 마지막 값은 정렬이 된 것이므로 힙의 일부가 아닌 것으로 간주함) ③ 루트노드에 대해서 Max-Heapify한다 ④ 남은 노드가 1개가 될 때 까지 ②,③을 반복한다 크게 생각한다면 Max Heap을 만들고(초기화), iterative하게 Max-Heapify하는 과정을 통해 배열을 정렬하는 것이다. 1. Heap Sort 과정 (1) Max Heap 만들기 정렬되지 않는 배열을 추상적으로 complete binary t..
0. Dynamic Set Dynamic Set은 여러 개의 키(key)를 저장하며 Insert(새로운 키 삽입), Search(키 탑색), Delete(키 삭제)와 같은 연산들을 지원하는 자료구조이다. 문제는 정렬되거나 정렬되지 않는 배열, 또는 연결 리스트를 사용할 때 insert, search, delete 중 적어도 하나는 $O(n)$의 시간복잡도를 피할 수 없게 된다. 때문에 이를 해결하고자 여러 방법들이 연구되었는데 그 해결방법들은 다음과 같다. 검색트리: 이진탐색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 등에 기반 해슁: 해쉬 테이블, Direct Address Table 등 1. 검색트리 Dynamic Set을 트리의 형태로 추상적으로 구현한 자료구조이다. 일..
0. 트리(Tree) 트리는 계층적인 구조를 표현하기 위한 자료구조(조직도, 파일시스템, 가계도 등)로, 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다. (1) 관련용어 부모, 자식 관계 형제관계: 루트노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가지며, 부모가 동일한 노드들을 형제관계라고 부름 리프(leaf) 노드: 자식이 없는 노드들 조상-자손 관계 부트리(sub-tree): 트리에서 어떤 노드와 그 노드의 자손들로 이루어진 트리(원래 트리의 일부분) 레벨(level): 트리에서 각 계층을 의미 높이: 트리의 높이는 레벨의 수를 의미 (2) 트리의 기본적인 성질 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다. 루트에서 어떤 노드로 가는 경로는 항상 유일하..
1. Heap이란? Heap은 heap property를 만족하는 complete binary tree이다. (1) complete binary tree binary tree는 자식 노드가 2개만 존재하며, 오른쪽 자식과 왼쪽 자식이 구분되는 tree이다. full binary tree: 모든 층(level)의 노드들이 꽉 차있는 형태 complete binary tree: 마지막 층(level)을 제외한 층의 노드들은 꽉 차 있으며, 마지막 층의 오른쪽부터 몇개의 노드가 비어있을 수 있음 (2) heap property 이 글에서는 max-heap property를 기준으로 다루고자 한다. max-heap property: 부모는 자식보다 크거나 같다 min-heap property: 부모는 자식보다 ..
정렬 알고리즘 종류 Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림) Merge Sort, Quick Sort, Heap Sort(빠름) Radix Sort(매우 빠름) 이 중 Merge Sort, Quick Sort, Heap Sort는 분할정복법을 적용하여 풀 수 있다. 분할: 풀고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복: 각각의 작은 문제들을 순환적으로 해결 합병: 작은 문제의 해들을 합하여 원래 문제에 대한 답을 구함(merging) 1. Merge Sort(합병정렬) 1) 정렬과정 - ① 분할: 배열의 길이가 1이 될때 까지 배열을 반복적으로 반으로 나눔($n \rightarrow \frac{n}{2} \rightarrow \frac{..
정렬 알고리즘 종류 Bubble Sort, Selection Sort, Insertion Sort(간단하지만 느림) Merge Sort, Quick Sort, Heap Sort(빠름) Radix Sort(매우 빠름) 1. Selection Sort(선택 정렬) 1) 정렬 과정 ⓪하나의 원소만 남을 때 까지 아래 루프를 실행한다.($O(n-1)$) - ①최대값 원소를 찾는다($O(n-1), O(n-2) \cdots O(1)$) - ②맨 오른쪽 원소를 최대값 원소로 교체한다($O(1)$) - ③정렬 대상인 배열에서 맨 오른쪽 원소를 제한다 2) 실행시간 ⓪루프는 $n-1$번 실행하며 ①최대값 원소를 찾는 과정은 $n-1, n-2,,, 1$번 실행한다. 시간복잡도: $T(n) = (n-1) + (n-2) + ..
모든 Recursion은 Iterative 함수로 표현이 가능하다. 그 역도 성립한다. 두개를 비교해보면 Recursion을 어떻게 설계하는게 좋을지 알 수가 있다. 1. Recursion 설계 포인트 1) 임시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라 2) 적어도 하나의 base case(순환이 종료되는 시점)이 존재해야 하며, 모든 recursive case가 base case로 수렴해야 한다. Recursion 설계 예시 1) 이진탐색 - Iterative version def binary_search_iterative(data, target): n = len(data) assert n > 0 begin = 0 end = n-1 while bigin end: ret..
순환하는 알고리즘을 익숙하게 받아들이기는 쉽지가 않은 것 같다. 함수의 출력물이 함수라고 생각되기 때문이다. 순환 알고리즘을 생각하기 위해서는 '바로 직전 스텝에서의 함수의 출력물을 사용한다', 또는 '현재 스텝에서의 함수의 출력물을 바로 다음 스텝에서 사용한다'는 방식의 사고가 필요하다. 즉 brute force처럼 스텝별로 탐색하도록 설계하는 것이다. (1) 문자열의 길이 계산 def string_length(string): assert type(string) == str if string=='': # base case return 0 else: return 1 + string_length(string[1:]) # recursive case (2) 문자열의 프린트 def print_forward(st..
1. 순환 알고리즘 개념 Recursion이란? 자기 자신을 호출하는 함수 def func(o): ... func(o2) ... 다음은 recursion을 적용하여 $0 \cdots N$의 정수 배열의 합을 구하는 함수를 구현한 것이다. def array_sum(N): if N == 0: return 0 else: return N + array_sum(N-1) Recursion은 무한루프에 빠지기 쉽다. 때문에 다음 조건은 거의 필수적이다 base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.(terminal condition 등) recursive case: recursion을 반복하면서 base case로 수렴해야 한다 Recursion은 점화식처럼 생각할 수 있다...
