[Python Algorithm] Ch3. 억지 기법과 완전 탐색

3.1 선택 정렬

정렬이란?

레코드들을 키(key) 순서대로 재배열 하는 것

정렬 문제
리스트에 n개의 항목들이 있다. 이들을 키(key) 순서에 따라 오름차순으로 재배치하여라.

• 억지 기법(기본 전략): 입력 리스트를 n번 돌아가면서 가장 작은 항목을 찾고 이를 다른 리스트에 저장
• 제자리 정렬: 입력 리스트에서 최솟값을 선택하고, 이를 첫 번째 요소와 교환

선택 정렬 알고리즘

def selection_sort(A):
    n = len(A)

    for i in range(n - 1):
        least = i
        for j in range(i + 1, n):
            if (A[j] < A[least]):
                least = j
        A[i], A[least] = A[least], A[i]     # 항목 교환
        # printStep(A, i + 1)

• 선택 정렬 알고리즘의 복잡도는 O(n^2)

3.2 순차 탐색

탐색이란?

주어진 항목들 중에서 “탐색키”라 불리는 원하는 값을 가진 항목을 찾는 것

탐색 문제
n개의 항목을 가진 리스트에서 “탐색키”를 가진 항목을 찾아라. 찾은 경우 그 항목의 인덱스 반환, 없을 시 -1 반환

순차 탐색 알고리즘

배열의 첫 항목부터 순서대로 키 값을 비교

• 순차 탐색 알고리즘의 복잡도(최선/평균/최악): O(1), O(n), O(n)

3.3 문자열 매칭

문자열 매칭 알고리즘

• 문자열 매칭 알고리즘의 복잡도(최선/최악): O(m), O(nm)

3.4 최근접 쌍의 거리

최근접 상의 거리 문제 알고리즘

• 최근접 상의 거리 문제 알고리즘의 복잡도: O(n^2)