코딩고치

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

삽입 정렬 삽입 정렬 (insertion sort) 2번째 인덱스부터 시작해서 앞의 숫자를 비교. 비교 숫자보다 크면 자리를 바꿈 작은 숫자가 나오면 멈춤 참조 (visualgo.net/en/sorting) 데이터가 2개 일 때 index 1과 index 0 만 비교 데이터가 3개일 때 데이터가 4개일 때 def insertion_sort(data): for trial in range(len(data) - 1): for i in range(trial + 1, 0, -1): if data[i] < data[i - 1]: data[i], data[i - 1] = data[i - 1], data[i] else: break return data import random num = random.sample(ran..

선택 정렬 (selection sort) 선택 정렬이란 데이터에서 최솟값을 찾아 가장 맨 앞에 위치한 값과 교체하는 방법 참조 (visualgo.net/en/sorting) 데이터의 길이가 n일 때 총 n-1번 시행을 한다. 반복문을 돌면서 가장 작은 수가 들어있는 인덱스를 저장할 변수를 만든다. 반복문을 시행한 뒤 자리바꿈을 실행한다. def selection_sort(data): for trial in range(len(data) - 1): first = trial for i in range(trial + 1, len(data)): if data[first] > data[i]: first = i data[first], data[trial] = data[trial], data[first] return ..

버블 정렬 (bubble sort) 버블 정렬: 인접한 두 데이터를 이용하여 대소 관계를 비교하여 순서대로 정렬하는 알고리즘이다. 참조 (visualgo.net/en/sorting) 데이터가 2개일 때 데이터가 3개일 때 이런 식으로 규칙을 찾아 나가면 총데이터가 n개일 때 최악의 경우 데이터를 1번 시행에서 총 n-1번 대소 검사를 하고 n-1번 반복을 한다. 1번 시행을 하면 가장 큰 데이터가 가장 뒤로 이동한다. 이때 굳이 가장 마지막 데이터를 비교할 필요가 없어지므로 데이터의 길이를 시행 횟수만큼 빼준다. 1번 시행했을 때 자리바꿈이 일어나지 않으면 중지를 한다. def bubblesort(data): for trial in range(len(data) - 1): change = False # 자..