Debug.Log

소수판별1. 에라토스테네스의 체고대 그리스 수학자 에라토스테네스가 발견한 소수 찾는 방법.N보다 작은 소수들을 찾으려면, 2보다 크거나 같고 ​보다 작은 소수의 배수들만 지우면 된다.예를 들어, 120보다 작은 소수들을 모두 찾고 싶다면, ​ 이므로 2, 3, 5, 7의 배수만 지우면 남은 수는 모두 소수가 된다.작은 수의 소수를 판별하는 데 유용하다. def is_prime(num): if num

퀵 셀렉션 (Quick Selection) 파이썬으로 구현퀵 셀렉션은 리스트를 정렬하지 않고 K번째로 큰 수를 알고 싶을 때 쓰는 방법이다.전체적인 솔루션은 퀵 정렬과 매우 유사하다, 피벗을 하나 골라서 값을 비교하면서, 피벗보다 작은 리스트, 피벗 보다 큰 리스트로 나눈다.k번째 숫자가 속해있는 리스트만 가지고 다시 재귀적으로 반복한다.median 값을 찾을 때도 활용 가능.평균 시간복잡도는 O(n) def quick_selection(arr, kth): pivot = arr[(len(arr)+1)//2 - 1] left, mid, right = [], [], [] for i in range(len(arr)): if arr[i] pivot: right.append(arr[i]) else: mid.app..

이진 검색 (Binary Search) 파이썬으로 구현Binary Search 는 오름차순으로 정렬된 리스트에서 특정값의 위치를 찾는 알고리즘처음 중간의 임의 값을 선택하여, 그 값의 크고 작음을 비교시간복잡도는 O (log N) 이다. def binary_search(arr, value): low = 0 high = len(arr)-1 while (low value: high = mid - 1 elif arr[mid]

계수 정렬 (Counting Sort) 파이썬으로 구현계수 정렬은 비교 정렬이 아니다.K가 정수일 때 (즉, K가 어떤 최대값을 가질때), 입력 요소들이 1부터 K까지의 정수라고 가정.히스토그램과 같이 각 요소들이 전체 리스트에서 몇 개씩 존재하는 지를 세아려 테이블을 만든다.입력된 X 아래에 몇개의 정수들이 존재하는 지에 따라 X의 위치가 결정되는 알고리즘.(예를 들어, 5보다 작은 정수 (1,2,3,4) 가 10개 존재한다면, 5가 들어갈 위치는 11번째이다.)시간복잡도가 O(n)이다. def counting_sorted(arr, K): c = [0] * K sorted_arr = [0] * len(arr) for i in arr: c[i] += 1 for i in range(1,K): c[i] +=..

퀵 정렬 (Quick Sort) 파이썬으로 구현퀵 정렬은 분할 정복 알고리즘의 좋은 예이다.리스트 중 하나를 pivot으로 정하고, pivot보다 작은 아이템은 왼쪽, pivot보다 큰 아이템은 오른쪽으로 보내면서 pivot의 자리를 확정한다.그리고 왼쪽 리스트와 오른쪽 리스트에 대해서 재귀형식으로 진행.평균 시간복잡도는 O(n*log n), 최악의 시간복잡도는 O(n^2) def quick_sorted(arr): if len(arr) > 1: pivot = arr[len(arr)-1] left, mid, right = [], [], [] for i in range(len(arr)-1): if arr[i] pivot: right.append(arr[i]) else: mid.append(arr[i]) mi..

병합정렬 (Merge Sort) 파이썬으로 구현병합정렬은 분할정복 알고리즘의 가장 좋은 예이다.정렬할 리스트를 반으로 나누어 두 부분을 따로 정렬하여 다시 조합하는 과정이다.시간복잡도는 O(n*log n) def merge_sorted(arr): if len(arr)>1: mid = len(arr)//2 left = arr[:mid] right = arr[mid:] ​ l = merge_sorted(left) r = merge_sorted(right) return merge(l, r) else: return arr def merge(left, right): i = 0 j = 0 arr = [] while (i