[Algorithm] 정렬
1. 정렬 알고리즘이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. (정렬 알고리즘은 이진 탐색의 전처리 과정이기도하니 제대로 알고 넘어가자.) 파이썬에서는 내림차순 리스트를 제공하고, 이는 O(N) 복잡도로 수행가능하니, 오름차순만 우선 공부해보자. 2. 선택 정렬 선택정렬의 아이디어는 매번 ' 가장 작은 것을 선택한다. ' 이다. 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 가장 작은 데이터를 N - 1번 반복하면 정렬이 완료되는 것을 알 수 있다. array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)):..
[Algorithm] 공간 복잡도
1. 공간 복잡도란? 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양을 말한다. 공간의 복잡도를 결정하는 것으로 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀함수 인지 등이 있다. 총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있다. 2. 고정 공간, 가변 공간 고정 공간은 입력과 출력의 횟수나 크기에 관계없는 공간의 요구를 말한다. ex) 코드 저장 공간, 단순 변수, 변수, 상수 저장 가변 공간은 프로그램 실행 중에 요구되는 요소이다. ex) 배열 전달, 재귀 호출, 회귀 주소 함수 호출시에 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요한데, 특히 재귀함수의 경우 매 함수 호출마다 매개변수, 지역변수, 함수의 복..
