코딩고치

퀵 정렬 (quick sort) 퀵 정렬 정렬 알고리즘의 핵심. 기준점 (pivot)을 정해서 pivot보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다. 각 왼쪽, 오른쪽으로 모인 수는 재귀 함수를 이용하여 위 과정을 반복한다. pivot 설정 나누기 왼쪽 오른쪽에서 각각 반복 합치기 알고리즘 작성 def qsort(list_num): if len(list_num) list_num[i]: left.append(list_num[i]) else: right.append(list_num[i]) return qsort(left) + [pivot] + qsort(right) import random list_num = random.sample(range(100), 10) qsort(l..

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 정의 동적 계획법 (DP) 큰 문제를 작은 부분 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘이다. 가장 최하위의 해답을 저장한 후 이를 이용하여 큰 문제를 풀어 나간다 (중복 문제 다시 계산 X). 이를 Memoization이라 한다. 분할 정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 나중에 다시 합쳐 문제의 답을 얻는다. 큰 문제를 풀기위해 큰 문제에서 작은 문제로 내려가면서 답을 구하는 방식이다. 주로 재귀 함수를 이용한다. 작은 문제들은 서로 중복되지 않는다. ex) 병합 정렬, 퀵 정렬 등 공통점과 차이점 공통점 문제를 쪼개어 작은 문제를 풀어 큰 문제를 해결한다. 차이점..

재귀 용법 (recursive call) 재귀 용법 함수 안에서 동일한 함수를 호출하는 형태이다. 팩토리얼 구하기 n! = n X (n-1)! n > 1 이면 return n X 함수(n - 1) n == 1이면 return n def factorial(num): if num > 1: return num * factorial(num - 1) else: return 1 for num in range(10): print(factorial(num)) 1 1 2 6 24 120 720 5040 40320 362880 시간 복잡도와 공간 복잡도 n - 1번 반복문을 호출한 것과 같다. 호출할 때마다 지역 변수 num이 생성된다. 시간 복잡도, 공간 복잡도 모두 O(n)이다. 재귀 호출은 스택의 예 파이썬에서는 재..

공간 복잡도 좋은 알고리즘의 기준 시간 복잡도: 얼마나 빨리 실행이 되는지에 대한 기준 공간 복잡도: 얼마의 저장 공간이 필요한지에 대한 기준 시간과 공간은 반비례적인 경향이 있다. 컴퓨터 용량이 커짐에 따라서 시간 복잡도의 중요도가 중요해 졌다. 빅데이터를 다루는 경우에는 공간 복잡도를 중요시 하기도 한다. 공간 복잡도 $S(P) = c + S_p(n)$ c: 고정 공간 알고리즘과 무관한 공간: 코드 저장 공간, 단순 변수 및 상수와 관련 $S_p(n)$ : 가변 공간 알고리즘이 실행되면서 동적으로 필요한 공간 빅 오 표기법으로 생각할 때 공간 복잡도는 가변 공간에 주로 영향을 많이 받는다. 공간 복잡도 계산 n! 구하기 def factorial(n): num = 1 for i in range(2, n..