[알고리즘] Week 3: 정렬 알고리즘 II - 삽입 정렬 및 고급 정렬 알고리즘

Day 1: 삽입 정렬 (Insertion Sort)

• 강의 내용:
  • 삽입 정렬의 개념
    • 삽입 정렬의 정의 및 작동 원리
    • 삽입 정렬의 시간 복잡도 분석 (최선의 경우 O(n), 최악의 경우 O(n^2))
  • 삽입 정렬의 장단점
    • 소규모 데이터셋에 효율적
    • 이미 정렬된 데이터에 매우 효율적
• 실습:
  • 삽입 정렬 알고리즘 구현 및 예제

# 삽입 정렬 알고리즘 구현
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# 삽입 정렬 예제
data = [12, 11, 13, 5, 6]
insertion_sort(data)
print("삽입 정렬 결과:", data)  # [5, 6, 11, 12, 13]

 

Day 2: 퀵 정렬 (Quick Sort)

• 강의 내용:
  • 퀵 정렬의 개념
    • 퀵 정렬의 정의 및 작동 원리 (분할 정복)
    • 시간 복잡도 분석 (평균 O(n log n), 최악 O(n^2))
  • 피벗 선택 전략
    • 첫 번째 요소, 마지막 요소, 중간 요소, 랜덤 선택
• 실습:
  • 퀵 정렬 알고리즘 구현 및 피벗 선택 전략 비교

# 퀵 정렬 알고리즘 구현
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

# 퀵 정렬 예제
data = [3, 6, 8, 10, 1, 2, 1]
sorted_data = quick_sort(data)
print("퀵 정렬 결과:", sorted_data)  # [1, 1, 2, 3, 6, 8, 10]

 

Day 3: 병합 정렬 (Merge Sort)

• 강의 내용:
  • 병합 정렬의 개념
    • 병합 정렬의 정의 및 작동 원리 (분할 정복)
    • 시간 복잡도 분석 (O(n log n))
  • 병합 정렬의 장단점
    • 안정적인 정렬 알고리즘
    • 추가적인 메모리 공간 필요
• 실습:
  • 병합 정렬 알고리즘 구현 및 예제

# 병합 정렬 알고리즘 구현
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 병합 정렬 예제
data = [38, 27, 43, 3, 9, 82, 10]
merge_sort(data)
print("병합 정렬 결과:", data)  # [3, 9, 10, 27, 38, 43, 82]

 

Day 4: 퀵 정렬 vs 병합 정렬 비교

• 강의 내용:
  • 퀵 정렬과 병합 정렬의 비교
    • 각 알고리즘의 장단점
    • 사용 사례 및 데이터셋 특성에 따른 선택
  • 퀵 정렬과 병합 정렬의 성능 비교
• 실습:
  • 퀵 정렬과 병합 정렬의 성능 비교 실험

# 성능 비교 예제
import time

def measure_time(sort_func, arr):
    start_time = time.time()
    sort_func(arr)
    end_time = time.time()
    return end_time - start_time

data1 = [38, 27, 43, 3, 9, 82, 10]
data2 = data1.copy()

print("퀵 정렬 시간:", measure_time(quick_sort, data1))
print("병합 정렬 시간:", measure_time(merge_sort, data2))

 

Day 5: 고급 정렬 알고리즘의 실제 응용

• 강의 내용:
  • 고급 정렬 알고리즘의 실제 응용 사례
    • 데이터베이스 정렬
    • 파일 시스템 정렬
    • 대규모 데이터셋 처리
  • 실제 문제를 통해 배우는 정렬 알고리즘
• 실습:
  • 고급 정렬 알고리즘을 활용한 실제 문제 해결

# 실제 문제 예제: 학생 성적 정렬

class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score

def student_sort_key(student):
    return student.score

# 학생 데이터 생성
students = [
    Student("Alice", 85),
    Student("Bob", 95),
    Student("Charlie", 70),
    Student("David", 90),
    Student("Eva", 88)
]

# 성적 기준으로 학생 정렬
sorted_students = sorted(students, key=student_sort_key, reverse=True)
for student in sorted_students:
    print(f"{student.name}: {student.score}")

# 예상 출력:
# Bob: 95
# David: 90
# Eva: 88
# Alice: 85
# Charlie: 70

 

Day 6: 종합 연습

• 강의 내용:
  • 고급 정렬 알고리즘 종합 연습
    • 다양한 정렬 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • Q&A 세션 및 피드백
• 실습:
  • 다양한 데이터셋을 사용한 정렬 알고리즘 연습
  • 알고리즘 성능 분석 및 최적화

# 종합 연습: 다양한 데이터셋 정렬
def generate_random_data(size):
    import random
    return [random.randint(0, 1000) for _ in range(size)]

# 데이터셋 생성
small_data = generate_random_data(10)
medium_data = generate_random_data(100)
large_data = generate_random_data(1000)

# 정렬 알고리즘 성능 비교
print("작은 데이터셋 퀵 정렬 시간:", measure_time(quick_sort, small_data.copy()))
print("작은 데이터셋 병합 정렬 시간:", measure_time(merge_sort, small_data.copy()))

print("중간 데이터셋 퀵 정렬 시간:", measure_time(quick_sort, medium_data.copy()))
print("중간 데이터셋 병합 정렬 시간:", measure_time(merge_sort, medium_data.copy()))

print("큰 데이터셋 퀵 정렬 시간:", measure_time(quick_sort, large_data.copy()))
print("큰 데이터셋 병합 정렬 시간:", measure_time(merge_sort, large_data.copy()))

 

Day 7: 프로젝트 준비 및 시작

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 데이터 정렬 프로젝트 주제 선정
    • 프로젝트 요구사항 정의
  • 프로젝트 계획 수립
    • 프로젝트 구현 계획 수립
    • 주요 기능 및 모듈 정의
• 실습:
  • 프로젝트 주제 및 계획 수립
  • 프로젝트 구현 시작

### 프로젝트 주제 예시
1. 데이터베이스 정렬 시스템
2. 파일 시스템 정렬 도구
3. 상품 가격 비교 도구

### 프로젝트 요구사항 예시
1. 데이터베이스 정렬 시스템:
   - 데이터 입력 및 저장
   - 다양한 정렬 알고리즘을 통한 데이터 정렬
   - 정렬된 데이터 검색 기능

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 정렬 알고리즘 구현 (퀵 정렬, 병합 정렬 등)
3. 데이터 검색 모듈 구현

 

이 강의는 파이썬의 고급 정렬 알고리즘을 이해하고 구현하는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!