코딩고치

퀵 정렬 (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) 병합 정렬, 퀵 정렬 등 공통점과 차이점 공통점 문제를 쪼개어 작은 문제를 풀어 큰 문제를 해결한다. 차이점..