5.2. 파이썬 알고리즘 기초

파이썬은 다양한 알고리즘을 구현하기에 적합한 언어로, 특히 정렬과 탐색 알고리즘은 데이터 처리의 핵심입니다. 이 글에서는 파이썬에서 기초적인 정렬 알고리즘(버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬)과 탐색 알고리즘(이진 탐색)에 대해 자세히 설명하겠습니다.

1. 정렬 알고리즘

정렬 알고리즘은 데이터를 정해진 순서로 배열하는 알고리즘입니다. 파이썬에서 가장 기본적인 정렬 알고리즘부터 시작하여 더 복잡한 알고리즘까지 살펴보겠습니다.

1.1 버블 정렬

버블 정렬은 인접한 두 요소를 반복적으로 비교하여 정렬하는 방식입니다. 가장 간단한 정렬 알고리즘 중 하나로, 데이터가 작은 경우에는 효율적이지만, 데이터가 큰 경우에는 시간복잡도가 O(n^2)로 느립니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

1.2 선택 정렬

선택 정렬은 데이터를 하나씩 선택하여 정렬하는 방식입니다. 선택한 데이터를 가장 작은 데이터와 교환하는 방식으로, 시간복잡도는 O(n^2)입니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

1.3 삽입 정렬

삽입 정렬은 데이터를 하나씩 삽입하여 정렬하는 방식입니다. 시간복잡도는 평균적으로 O(n^2)이나, 최선의 경우 O(n)입니다.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

1.4 퀵 정렬

퀵 정렬은 분할 정복 알고리즘을 사용하여 데이터를 정렬하는 방식입니다. 평균 시간복잡도는 O(n log n)으로, 가장 빠른 정렬 알고리즘 중 하나입니다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

2. 탐색 알고리즘

탐색 알고리즘은 데이터를 빠르게 찾는 알고리즘입니다. 이진 탐색은 가장 대표적인 탐색 알고리즘으로, 데이터가 정렬된 상태에서 사용됩니다.

2.1 이진 탐색

이진 탐색은 데이터를 반씩 나누어 탐색하는 방식입니다. 데이터가 정렬된 상태에서 사용하며, 시간복잡도는 O(log n)입니다.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

3. 정렬과 탐색의 비교

정렬 알고리즘과 탐색 알고리즘은 모두 데이터 처리의 중요한 부분입니다. 정렬 알고리즘은 데이터를 정해진 순서로 배열하는 반면, 탐색 알고리즘은 데이터를 빠르게 찾는 알고리즘입니다. 파이썬에서 각 알고리즘의 시간복잡도와 효율성을 비교하여 사용할 수 있습니다.

3.1 시간복잡도

• 버블 정렬, 선택 정렬: O(n^2)
• 삽입 정렬: 평균 O(n^2), 최선의 경우 O(n)
• 퀵 정렬: 평균 O(n log n)
• 이진 탐색: O(log n)

3.2 효율성

• 버블 정렬, 선택 정렬: 데이터가 작은 경우에 효율적이지만, 데이터가 큰 경우에는 느립니다.
• 삽입 정렬: 데이터가 정렬된 상태에서 효율적입니다.
• 퀵 정렬: 데이터가 큰 경우에 가장 빠른 정렬 알고리즘입니다.
• 이진 탐색: 데이터가 정렬된 상태에서 가장 빠른 탐색 알고리즘입니다.

4. 실습 예제

4.1 버블 정렬 실습

버블 정렬을 사용하여 데이터를 정렬하는 예제입니다.

arr = [64, 34, 25, 12, 22, 11, 90]
print("원본 배열:", arr)
arr = bubble_sort(arr)
print("정렬된 배열:", arr)

4.2 이진 탐색 실습

이진 탐색을 사용하여 데이터를 찾는 예제입니다.

arr = [2, 3, 4, 10, 40]
target = 10
index = binary_search(arr, target)
if index != -1:
    print("원소", target, "은(는) 배열에 있습니다.")
else:
    print("원소", target, "은(는) 배열에 없습니다.")

파이썬 알고리즘 기초는 데이터 처리의 핵심입니다. 정렬 알고리즘과 탐색 알고리즘은 모두 데이터 처리의 중요한 부분이며, 각 알고리즘의 시간복잡도와 효율성을 비교하여 사용할 수 있습니다. 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 이진 탐색 등 다양한 알고리즘을 사용하여 데이터를 효율적으로 처리할 수 있습니다.