매일 매일 미라클 코딩

리스트를 두 그룹으로 나누어 먼저 정렬하고, 두 그룹의 맨 앞부터 차례대로 병합하는 방식. 한 그룹의 자료가 모두 소진되면 남은 그룹의 정렬 상태 그대로 결과 리스트에 삽입하면 된다. 이렇게 주어진 문제를 절반으로 나눈다음 각각 재귀호출로 풀어가는 방식을 '분할정복'이라고 함 시간 복잡도 O(n logn)으로 O(n²)인 선택/삽입정렬보다 빠르다. 따라서 정렬해야할 자료의 개수가 많을 수록 병합정렬이 선택/삽입 정렬보다 좋은 성능을 보인다. def merge_sort(a): n = len(a) #종료 조건 if n

삽입정렬은 리스트의 두번째 인덱스 list[1] 부터 시작한다. list[n]일때 list[n-1], list[n-2], list[n-3]...순으로비교하며 자기보다 큰 값과 자리를 바꿔나가는 방식. (오름차순의 경우) 더 작은 값이 나오지 않으면 그자리에 삽입하고 다음 턴으로 넘어간다. 선택정렬과 같은 O(n²)의 복잡도를 가지며, 입력값이 크면 시간이 굉장히 오래 걸린다. def ins_sort(a): n = len(a) for i in range(1,n): temp = a[i] # i번 위치에 있는 값을 temp에 저장 j = i-1 # i 바로 전 인덱스 j에 저장 while j >=0 and a[j] > temp: a[j+1] = a[j] # i 자리에 j 인덱스값 이동 j -= 1 a[j+1]..

선택정렬은 첫번째 인덱스 부터 시작하여 뒤에 남은 값들과 하나씩 비교한다. 남은 값들 중 가장 큰(혹은 작은) 값이 정해지면 비교기준인 인덱스와 자리를 바꿔주는 방식 - 리스트 안의 자료를 한번씩 비교하기 때문에 계산 복잡도는 O(n²) - 이해하기 쉽고 간단하지만, 비교횟수가 입력크기의 제곱에 비례하기 때문에 입력크기가 커지면 시간이 오래걸린다. def sel_sort(a): n = len(a) for i in range(0,n-1): #n-2까지 확인 min_idx = i # i번 위치부터 끝까지 자료값중 최솟값의 위치를 찾음 for j in range(i+1,n): if a[min_idx]> a[j]: min_idx =j a[i], a[min_idx] = a[min_idx],a[i] # 찾은 인덱스..

노트북 환경이 마땅치 않을 때 코랩에서실행하면 된다. 단 학습시간은 최대 12시간을 지원한다 런타임 > 유형 변경 > GPU 로 셋팅한다