1,2장 정리
- 순차탐색 - sequential search
- 이진탐색 - binary search
- 동전거스름돈 -> 그리디알고맂므
- Big-oh -> 상한 / Big-omega -> 하한 / theta -상한,하한
정렬
6.1 버블정렬
- 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복
- 입력을 전체적으로 한번 처리하는 것을 패스라고 한다.
- 포문 2개, A[i-1] > A[i] //위의 원소가 아래원소보다 크면 // 서로 자리를 바꾼다
(여기서는 위가 더 첨자가 작은 배열의 원소에 속한다 즉 a[5]라면, 가장 바닥은 a[5]이다. )
6.2 선택 정렬
- 입력 배열 전체에서 최솟값을 ‘선택’하여 배열의 0번 원소와 자리를 바꾸는 방법으로 오름차순 정렬하는 과정 반복(그 다음은 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 배열의 1번 원소와 자리를 바꾼다.)
- a[i] ~ a[n-1]에서 최솟값을 찾고, a[i] <-> a[min] min이 최솟값이 있는 인덱스이므로 값을 바꿔준다.
6.3 삽입정렬
배열을 정렬된 부분(앞부분)과 정렬이 안 된 부분(뒷부분)으로 나누고, 정렬이 안 된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 삽입하려 정렬되도록 하는 과정을 반복한다.
6.4 쉘 정렬
삽입정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 ‘빠르게’ 이동시키고 동시에 앞부분의 큰 숫자는 뒷부분을 이동시키며 가장 마지막에 삽입정렬을 수행
6.5 힙 정렬
heap : 힙조건을 만족하는 완전이진트리 힙조건 : 각 노드의 값이 자식 노드의 값보다 크다. 값이란 우선순위를 말함. 따라서 힙의 루트에는 가장 높은 우선순위(가장 큰 값)가 저장되어 있다.
완전이진트리 : 깊이가 k인 이진트리에서 ①레벨 k-1까지는 2개의 자식을 가진 정 이진트리이고 ②레벨 k에서는 왼쪽부터 노드가 순차적을 채워져있는 이진트리
트리에서는 부모노드와 자식노드의 관계를 배열의 인덱스로 쉽게 표현 가능
6.6
참고자료
파이썬으로 웹 크롤러 만들기 (라이언 미첼 지음, 한선용 옮김, 한빛 미디어)
이진석 선생님 강좌 사이트 nomade