코딩고치

병합 정렬 (merge sort) 재귀 함수를 함수를 이용한 정렬이다. 리스트를 자른다. 각 데이터를 두개씩 묶어서 정렬한다. 이를 반복하여 정렬을 한다. 참고 주소: https://visualgo.net/en/sorting 데이터가 4개 일 때 두 부분으로 나눈다 또다시 각각 두 부분으로 나눈다 각각의 부분을 정렬해서 합친다 두 번째 부분의 0번 인덱스를 첫 번째 부분의 숫자와 비교하여 정렬한다. 이것을 반복한다. 알고리즘 구현 def merge(part_a, part_b): merged = list() a_index, b_index = 0, 0 # 데이터가 아직 남아있을 때 while len(part_a) > a_index and len(part_b) > b_index: if part_a[a_inde..

퀵 정렬 (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)이다. 재귀 호출은 스택의 예 파이썬에서는 재..