퀵 정렬 Quick sort 분할 정복의 알고리즘 종류중 하나다 ( 분할 하여 정렬함) 정렬 알고리즘의 꽃으로 빠르다 기준점(pivot)을 정해서, 기준점 보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)로 모으는 함수를 사용 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수로 호출하여 위 작업을 반복함 return 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 원리 list = [46, 97, 53, 3, 33, 65, 62, 52], Quick sort 1. pivot 선택 기본적으로 index 0을 pivot로 선택함 2. pivot을 기준으로 왼쪽(left)는 작은 수 오른쪽(right)는 큰 수로 둠, 나눈 것에 index 0을 p..
계산 복잡도 시간 복잡도 Time Complexity: 얼마나 빠른지 (속도), 알고리즘에 사용되는 연산 횟수의 총량 공간 복잡도 Space Complexity : 얼마나 많은 저장공간이 필요한지(메모리), 알고리즘에 사용되는 메모리 공간의 총량 시간 복잡도와 공간 복잡도는 반비례적인 성향을 띄고 있음 최근 대용량 시스템이 보편화 되면서 시간 복잡도를 우선시 함 (빅 데이터를 다룰때 공간 복잡도 또한 신경씀) 필요한 이유 하나의 문제를 푸는 알고리즘은 다양할 수 있는데 어느 알고리즘이 더 좋은지 분석해봐야함 이 때 사용하는 것이 계산 복잡도임 예시) 절대값 구하기 정수값 제곱 후 루트 음수일 때, -1 곱하기 등 다양한 풀이법이 나옴 간단한 문제라 복잡도에 차이가 없음 알고리즘 성능 표기법 Big O (..
Sort 데이터를 임의의 순서대로 나열하는 것 대표적인 정렬 버블 정렬 (Bubble Sort) 삽입 정렬 (Insertion Sort) 선택 정렬 (Select Sort) 버블 정렬 (Bubble Sort) https://visualgo.net/en/sorting 두 인접한 데이터를 앞의 데이터가 더 크다면 두 데이터의 자리를 바꾸는 정렬 알고리즘 코드 def bubble_sort(num_list): for i in range(len(num_list)): for j in range(len(num_list)-i-1): if num_list[j] > num_list[j+1]: num_list[j], num_list[j+1] = num_list[j+1], num_list[j] return num_list -..
순차 탐색 Sequential Search 데이터가 담겨있는 list를 앞에서부터 하나 씩 비교해서 원하는 데이터를 찾는 방법 알고리즘을 잘 몰라도 간단하게 구현할 수 있는 알고리즘 구현 def sequential(data_list, find_data): print(data_list) for i in range(len(data_list)): if data_list[i] == find_data: return i return -1 sequential(data_list, 32) 시간 복잡도 최악의 경우 모든 list를 다 확인해야 할 수 있음 \( O(n) \)
Binary Search 정렬된 리스트에서 범위를 줄여가며 결과값을 찾는 알고리즘 정렬된 상태에서만 사용이 가능하지만 탐색할 때마다 탐색 범위가 줄기 때문에 속도가 빠름 직관 Up & Down 게임 1 ~ 100 사이의 숫자라고 할 때 1 부터 추리하기보다는 50부터 추리하여 탐색 범위를 줄임 순차 탐색과 이진 탐색 비교 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 (Divide and Conquer) Divide : 문제를 하나 또는 둘 이상으로 나눈다. Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고 그렇지 않다면 다시 Divide 이진 탐색 알고리즘 (Binary Search) Divide : 리스트를 두개의 서브 리스트로 나눈다. Conquer 검색 숫자 Searc..
동적 계획법 (DP) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결하는 알고리즘, 문제 해결 패러다임 상향식 접근법, 최하위 해답을 구하고 이를 이용하여 상위 문제를 풀어감 Memorization 기법 사용 프로그램 실행 시 이전 계산 값(작은 문제)을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술임 큰 문제를 작은 문제로 쪼개서 답을 저장하고 재활용 하기에 '기억하며 풀기' 라고도 불림 ex) 피보나치 수열 재귀함수와 다른 점은 \((F_{2}\) 가 여러번 사용되는데 동적 계획법은 저장하여 다시 계산하지 않고 재귀함수는 하나하나 다 계산하여 시간이 오래 걸린다 \( O(n^{2}) \to O(f(n)) \) 분할 정복 큰 ..
재귀용법 함수 안에서 동일한 함수를 사용하는 것 여러 알고리즘 작성시 사용되기 때문에 익숙해지는 것이 좋음 고급 정렬 알고리즘에서 사용함 일정 패턴이 존재함 재귀함수의 깊이는 1000으로 제한 2개의 재귀 함수 비교 def func_1(num): if num 1: a = num * factorial(num-1) print('b',num) return a else: return num print(factorial(4)) a 4 a 3 a 2 a 1 b 2 b 3 b 4 24 코드 형태 #case 1 def function(input): if input > threshold: return function(input -1) # 상황에 맞게 변경해주기 else return input # 상황에 맞게 변경해주기 ..
Heap 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 Complete Binary Tree 완전 이진 트리 Complete Binary Tree node 삽입시 최하단 왼쪽 node부터 차례대로 삽입하는 Tree 사용하는 이유 배열의 최대값 최소값 찾기 복잡도 \( O_{n} \) (데이터 넣고 빼는 거 까지) heap의 최대값 최소값 찾기 복잡도 \( O_{logn} \) (데이터 넣고 빼는 거 까지) 우선 순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 경우에 사용함 구조 Max Heap : 최대값을 구하기 위한 구조 Min Heap : 최소값을 구하기 위한 구조 2가지 조건 Max Heap의 경우 각 node의 값은 해당 mode의 자식 node가 가진 값보다 크거나 같아야 함.(..
