정렬 알고리즘 종류 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{..
모든 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..
