알고리즘 (3) 썸네일형 리스트형 03. Divide & Conquer 분할정복 분할 정복 어떤 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고, 다시 합병하여 문제의 답을 얻는 알고리즘 크기가 작아질 뿐 문제 자체는 변하지 않기 때문에, 분할은 재귀적 분할 재귀적으로 나타낼 수 있기에 수행시간 $T(n)$은 점화식으로 표현될 수 있음 Selection에서 배운 quick_select, MoM 알고리즘 모두 분할 정복 알고리즘 $a^n$ 계산하기 선형 재귀 호출 def power1(a, n): if n == 1: return a return a * power1(a, n - 1) 수행시간 2. 이진 재귀 호출 def power2(a, n): if n == 1: return a if n == 0: return 1 if n % 2 == 0: return power2(a, n // 2) .. 02. Selection Selection Problem 입력 : 리스트에 n개의 수와 1과 n 사이의 자연수 k가 주어진다 출력 : k번째로 작은 수 를 찾아 리턴한다 목적 : 비교횟수를 되도록 줄인다 상한과 하한 상한(upper bound) : 어떠한 값 x가 있고 집합 A의 모든 원소보다 크거나 같을 때, x를 상계라고 한다. 그리고 이러한 상계들의 집합에서 최소원소를 상한이라고 한다. 알고리즘에서 수행시간의 상한은 최악의 경우에서 문제를 수행하는데 걸리는 시간을 의미. 즉, 항상 해당 시간 이하로 답을 찾을 수 있다는 것을 내포. 우리가 말하는 점근적 표기법에서 $Big-O$ 표기법이 상한을 나타내는데 사용된다. 하한(lower bound) : 어떠한 값 x가 있고 집합 A의 모든 원소보다 작거나 같을 때, x를 상계라고.. 01. Recursion 재귀 재귀 함수란, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀함수는 매 호출시마다 입력값이 변한다. 입력값의 변화가 없는 호출은 무한히 반복된다. 입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 종료된다. 따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다. 재귀 함수의 구조는 크게 2가지로 나눌 수 있다. 종료 조건 (base case) 재귀 함수가 무한 호출에 빠지지 않게 해주는 조건을 명시하는 것이다. 이는 곧 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우를 뜻한다. 재귀 조건 (recursive case) 종.. 이전 1 다음