알고리즘 기초 - 정렬과 탐색

알고리즘 기초 - 정렬과 탐색

알고리즘 기초 - 정렬과 탐색

같은 문제도 풀이 방법에 따라 속도가 천지차이입니다. 알고리즘의 기본, 정렬과 탐색을 직접 구현해봅시다.

---

알고리즘이란?

알고리즘(Algorithm)은 문제를 해결하기 위한 단계별 절차입니다.

같은 요리를 만들더라도 레시피에 따라 시간이 다르듯, 같은 문제도 알고리즘에 따라 성능이 달라집니다.

---

시간 복잡도 - 빅오 표기법

알고리즘의 성능을 나타내는 방법입니다. 데이터가 n개일 때 연산 횟수를 표현합니다.

알고리즘 시간 복잡도

표기	이름	n=1000일 때	예시
O(1)	상수	1	딕셔너리 조회
O(log n)	로그	~10	이진 탐색
O(n)	선형	1,000	리스트 순회
O(n log n)	선형 로그	~10,000	파이썬 sort()
O(n²)	이차	1,000,000	버블 정렬

숫자가 클수록 느립니다. O(1)이 가장 빠르고, O(n²)은 데이터가 많으면 매우 느려집니다.

---

정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

옆에 있는 값과 비교해서, 작은 값을 앞으로 보내는 방식입니다.
거품이 올라오듯 큰 값이 뒤로 이동합니다.

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

numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))
# [11, 12, 22, 25, 34, 64, 90]

• 시간 복잡도: O(n²)
• 특징: 구현이 간단하지만 느림

2. 선택 정렬 (Selection Sort)

전체에서 가장 작은 값을 찾아 맨 앞에 놓는 방식입니다.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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

numbers = [64, 34, 25, 12, 22, 11, 90]
print(selection_sort(numbers))
# [11, 12, 22, 25, 34, 64, 90]

• 시간 복잡도: O(n²)
• 특징: 교환 횟수가 적음

3. 삽입 정렬 (Insertion Sort)

카드를 정리하듯, 하나씩 뽑아서 알맞은 위치에 끼워 넣는 방식입니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]  # 한 칸씩 뒤로 밀기
            j -= 1
        arr[j + 1] = key  # 알맞은 위치에 삽입
    return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(numbers))
# [11, 12, 22, 25, 34, 64, 90]

• 시간 복잡도: O(n²), 거의 정렬된 경우 O(n)
• 특징: 거의 정렬된 데이터에 효율적

---

정렬 알고리즘 비교

알고리즘	최선	평균	최악	안정성
버블 정렬	O(n)	O(n²)	O(n²)	안정
선택 정렬	O(n²)	O(n²)	O(n²)	불안정
삽입 정렬	O(n)	O(n²)	O(n²)	안정
파이썬 sort()	O(n)	O(n log n)	O(n log n)	안정

실전에서는 파이썬의 sort()와 sorted()를 사용하세요. 내부적으로 Timsort 알고리즘을 사용해 매우 빠릅니다.

---

탐색 알고리즘

1. 선형 탐색 (Linear Search)

처음부터 끝까지 하나씩 확인하는 방법입니다.

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i  # 찾으면 인덱스 반환
    return -1  # 못 찾으면 -1

numbers = [4, 2, 7, 1, 9, 3, 5]
print(linear_search(numbers, 7))   # 2
print(linear_search(numbers, 10))  # -1

• 시간 복잡도: O(n)
• 조건: 정렬되지 않아도 사용 가능

2. 이진 탐색 (Binary Search)

정렬된 데이터에서 중간값을 기준으로 절반씩 범위를 줄여가는 방법입니다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid       # 찾았다!
        elif arr[mid] < target:
            left = mid + 1   # 오른쪽 절반 탐색
        else:
            right = mid - 1  # 왼쪽 절반 탐색

    return -1  # 못 찾음

numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(numbers, 7))   # 3
print(binary_search(numbers, 10))  # -1

• 시간 복잡도: O(log n)
• 조건: 반드시 정렬된 데이터에서만 사용 가능

선형 탐색 vs 이진 탐색

100만 개의 데이터에서 값을 찾을 때:

• 선형 탐색: 최대 1,000,000번 비교
• 이진 탐색: 최대 20번 비교

이진 탐색은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어듭니다!

---

파이썬의 내장 정렬/탐색

# 정렬
numbers = [3, 1, 4, 1, 5, 9, 2, 6]

# 원본 변경
numbers.sort()
print(numbers)  # [1, 1, 2, 3, 4, 5, 6, 9]

# 새 리스트 반환
original = [3, 1, 4, 1, 5]
sorted_list = sorted(original)
print(original)     # [3, 1, 4, 1, 5] (원본 유지)
print(sorted_list)  # [1, 1, 3, 4, 5]

# 내림차순
print(sorted(original, reverse=True))  # [5, 4, 3, 1, 1]

# 키 함수로 정렬
words = ["banana", "apple", "cherry"]
print(sorted(words, key=len))  # ['apple', 'banana', 'cherry']

students = [("김철수", 85), ("이영희", 92), ("박민수", 78)]
print(sorted(students, key=lambda x: x[1]))
# [('박민수', 78), ('김철수', 85), ('이영희', 92)]

bisect 모듈 (이진 탐색)

import bisect

sorted_list = [1, 3, 5, 7, 9, 11]

# 삽입 위치 찾기
pos = bisect.bisect_left(sorted_list, 7)
print(pos)  # 3 (인덱스 3에 7이 있음)

# 정렬 유지하며 삽입
bisect.insort(sorted_list, 6)
print(sorted_list)  # [1, 3, 5, 6, 7, 9, 11]

---

직접 해보기

문제 1: 버블 정렬 카운터

버블 정렬에서 교환이 몇 번 일어나는지 세는 함수를 만드세요.

numbers = [5, 3, 8, 1, 2]

정답 보기

def bubble_sort_count(arr):
    n = len(arr)
    count = 0
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                count += 1
    return arr, count
‍
numbers = [5, 3, 8, 1, 2]
result, swaps = bubble_sort_count(numbers)
print(f"정렬 결과: {result}")
print(f"교환 횟수: {swaps}")
‍
# 정렬 결과: [1, 2, 3, 5, 8]
# 교환 횟수: 7

문제 2: 이진 탐색 단계 출력

이진 탐색 과정에서 매 단계의 범위와 중간값을 출력하세요.

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23

정답 보기

def binary_search_verbose(arr, target):
    left, right = 0, len(arr) - 1
    step = 0
‍
    while left <= right:
        step += 1
        mid = (left + right) // 2
        print(f"[{step}단계] 범위: arr[{left}]~arr[{right}] = {arr[left]}~{arr[right]}, 중간값: arr[{mid}] = {arr[mid]}")
‍
        if arr[mid] == target:
            print(f"  → 찾았습니다! 인덱스: {mid}")
            return mid
        elif arr[mid] < target:
            left = mid + 1
            print(f"  → {arr[mid]} < {target}, 오른쪽 탐색")
        else:
            right = mid - 1
            print(f"  → {arr[mid]} > {target}, 왼쪽 탐색")
‍
    return -1
‍
numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
binary_search_verbose(numbers, 23)
‍
# [1단계] 범위: arr[0]~arr[9] = 2~91, 중간값: arr[4] = 16
#   → 16 < 23, 오른쪽 탐색
# [2단계] 범위: arr[5]~arr[9] = 23~91, 중간값: arr[7] = 56
#   → 56 > 23, 왼쪽 탐색
# [3단계] 범위: arr[5]~arr[6] = 23~38, 중간값: arr[5] = 23
#   → 찾았습니다! 인덱스: 5

문제 3: 성적 순 정렬

학생 딕셔너리 리스트를 점수 기준 내림차순으로 정렬하고, 등수를 매기세요.

students = [
    {"name": "김철수", "score": 85},
    {"name": "이영희", "score": 92},
    {"name": "박민수", "score": 78},
    {"name": "최지연", "score": 95},
    {"name": "정우진", "score": 88}
]

정답 보기

students = [
    {"name": "김철수", "score": 85},
    {"name": "이영희", "score": 92},
    {"name": "박민수", "score": 78},
    {"name": "최지연", "score": 95},
    {"name": "정우진", "score": 88}
]
‍
# 점수 기준 내림차순 정렬
ranked = sorted(students, key=lambda x: x["score"], reverse=True)
‍
for rank, student in enumerate(ranked, 1):
    print(f"{rank}등: {student['name']} ({student['score']}점)")
‍
# 1등: 최지연 (95점)
# 2등: 이영희 (92점)
# 3등: 정우진 (88점)
# 4등: 김철수 (85점)
# 5등: 박민수 (78점)

---

오늘의 정리

개념	설명
시간 복잡도	알고리즘 성능을 나타내는 빅오 표기법
버블/선택/삽입 정렬	O(n²) 기본 정렬 알고리즘들
선형 탐색	O(n) - 처음부터 끝까지 순서대로 탐색
이진 탐색	O(log n) - 정렬된 데이터에서 절반씩 줄이며 탐색
sort() / sorted()	파이썬 내장 정렬 (Timsort, O(n log n))

---

다음 편 예고

다음 편에서는 주소록 프로그램을 만듭니다. 지금까지 배운 모든 것(클래스, 파일I/O, 자료구조, 예외처리)을 총동원하는 종합 프로젝트입니다!

---

파이썬 Python 파이썬독학 알고리즘 정렬 탐색 이진탐색 시간복잡도 코딩테스트 파이썬실전 IT교육