본문 바로가기

퀵정렬

[Computer Science] Divide and Conquer(분할 정복) - 퀵정렬과 병합정렬(Quick Sort and Merge Sort) Divide and Conquer(분할 정복) 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법. 비슷한 크기로 문제를 분할하고, 해결된 문제를 제외하고 동일한 크기로 문제를 다시 분할한다. 병렬적으로 문제를 해결할 수 있다. 단점: 동일한 문제를 다시 푼다. 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용된다. !!! 재귀호출과 분할정복의 차이 !!! 재귀호출은 같은 함수코드를 재호출하는 것(같은 함수코드 사용) 분할정복은 비슷한 작업을 재진행하는 것(같은 함수코드는 아닐 수 있음) ''' 1부터 10까지의 합 구하기 ''' #재귀 함수 사용 def r_func(num): if num < 1: return 0 else: return num + r_func(num-1) print('.. 더보기
[Computer Science] Iterative Sorting(반복 정렬) - Selection Sort(선택정렬), Insertion Sort(삽입정렬), Bubble Sort(버블정렬), Count Sort (계수 정렬) / 시간 측정 비교 모든 알고리즘의 기본 원리는 숫자와 조건을 활용하면서 발전시킨다고 생각하면, 어려운 알고리즘에 대해 배우는 관점이 달라질 수 있다. Selection Sort(선택정렬) 선택정렬은 가장 작은 노드(최소값)를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것. 선택정렬 정리 : 최소노드 선택 -> 왼쪽부터 비교 -> 교환 단점 : 버블정렬과 달리 서로 이웃하지 않은 노드를 교환하므로, 안정적이지 않다. '''선택 정렬 소스 코드 ''' array = [7, 5, 9, 0, 3, 1, 6, 2, 8, 4] for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스로 지정 for j in range(i+1, len(array)): #j는 .. 더보기

티스토리툴바