[알고리즘] Week 7: 분할 정복 알고리즘 - 개념과 예제

Day 1: 분할 정복의 개념

• 강의 내용:
  • 분할 정복의 정의와 중요성
    • 분할 정복이란 무엇인가?
    • 분할 정복 알고리즘의 기본 원리 (분할, 정복, 합병)
    • 분할 정복의 장점 및 활용 사례
  • 분할 정복의 장단점
    • 문제를 더 작은 부분 문제로 나누어 해결
    • 재귀적 접근과 비교했을 때의 장점
• 실습:
  • 간단한 분할 정복 알고리즘 예제 설명

# 분할 정복의 간단한 예제: 배열의 최대값 찾기
def find_max(arr, low, high):
    if low == high:
        return arr[low]
    mid = (low + high) // 2
    max1 = find_max(arr, low, mid)
    max2 = find_max(arr, mid + 1, high)
    return max(max1, max2)

# 예제 실행
data = [1, 3, 7, 9, 2, 6, 4, 5, 8]
print("배열의 최대값:", find_max(data, 0, len(data) - 1))  # 9

 

Day 2: 병합 정렬 (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 3: 퀵 정렬 (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 4: 최대 부분 배열 문제 (Maximum Subarray Problem)

• 강의 내용:
  • 최대 부분 배열 문제의 개념
    • 최대 부분 배열 문제 정의 및 분할 정복 접근법
    • 카데인 알고리즘과의 비교
  • 분할 정복을 이용한 최대 부분 배열 문제 해결
• 실습:
  • 분할 정복을 이용한 최대 부분 배열 문제 해결 알고리즘 구현

# 분할 정복을 이용한 최대 부분 배열 문제 해결 알고리즘 구현
def max_crossing_sum(arr, low, mid, high):
    left_sum = float('-inf')
    total = 0
    for i in range(mid, low-1, -1):
        total += arr[i]
        if total > left_sum:
            left_sum = total

    right_sum = float('-inf')
    total = 0
    for i in range(mid + 1, high + 1):
        total += arr[i]
        if total > right_sum:
            right_sum = total

    return left_sum + right_sum

def max_subarray_sum(arr, low, high):
    if low == high:
        return arr[low]

    mid = (low + high) // 2
    left_sum = max_subarray_sum(arr, low, mid)
    right_sum = max_subarray_sum(arr, mid + 1, high)
    cross_sum = max_crossing_sum(arr, low, mid, high)

    return max(left_sum, right_sum, cross_sum)

# 최대 부분 배열 문제 예제
data = [2, 3, 4, 5, 7]
print("최대 부분 배열의 합:", max_subarray_sum(data, 0, len(data) - 1))  # 21

 

Day 5: 최근접 점 문제 (Closest Pair of Points)

• 강의 내용:
  • 최근접 점 문제의 개념
    • 최근접 점 문제 정의 및 분할 정복 접근법
  • 분할 정복을 이용한 최근접 점 문제 해결
    • 두 점 사이의 거리 계산
    • 분할 정복을 통한 효율적인 접근
• 실습:
  • 분할 정복을 이용한 최근접 점 문제 해결 알고리즘 구현

# 두 점 사이의 거리 계산 함수
import math

def distance(point1, point2):
    return math.sqrt((point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2)

# 최근접 점 문제 해결 함수 구현
def closest_pair(points):
    def closest_pair_recursive(points_sorted_by_x, points_sorted_by_y):
        if len(points_sorted_by_x) <= 3:
            return brute_force_closest_pair(points_sorted_by_x)

        mid = len(points_sorted_by_x) // 2
        left_half_x = points_sorted_by_x[:mid]
        right_half_x = points_sorted_by_x[mid:]

        midpoint = points_sorted_by_x[mid][0]
        left_half_y = list(filter(lambda x: x[0] <= midpoint, points_sorted_by_y))
        right_half_y = list(filter(lambda x: x[0] > midpoint, points_sorted_by_y))

        (left_min_pair, left_min_dist) = closest_pair_recursive(left_half_x, left_half_y)
        (right_min_pair, right_min_dist) = closest_pair_recursive(right_half_x, right_half_y)

        if left_min_dist < right_min_dist:
            min_pair, min_dist = left_min_pair, left_min_dist
        else:
            min_pair, min_dist = right_min_pair, right_min_dist

        strip = [p for p in points_sorted_by_y if abs(p[0] - midpoint) < min_dist]
        (strip_min_pair, strip_min_dist) = closest_pair_in_strip(strip, min_dist)

        if strip_min_dist < min_dist:
            return strip_min_pair, strip_min_dist
        else:
            return min_pair, min_dist

    def brute_force_closest_pair(points):
        min_dist = float('inf')
        min_pair = None
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                dist = distance(points[i], points[j])
                if dist < min_dist:
                    min_dist = dist
                    min_pair = (points[i], points[j])
        return min_pair, min_dist

    def closest_pair_in_strip(strip, min_dist):
        min_pair = None
        for i in range(len(strip)):
            for j in range(i + 1, min(i + 7, len(strip))):
                dist = distance(strip[i], strip[j])
                if dist < min_dist:
                    min_dist = dist
                    min_pair = (strip[i], strip[j])
        return min_pair, min_dist

    points_sorted_by_x = sorted(points)
    points_sorted_by_y = sorted(points, key=lambda x: x[1])
    return closest_pair_recursive(points_sorted_by_x, points_sorted_by_y)

# 최근접 점 문제 예제
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print("최근접 점 쌍:", closest_pair(points))

 

Day 6: 분할 정복 알고리즘의 성능 분석

• 강의 내용:
  • 분할 정복 알고리즘의 성능 분석
    • 분할 정복 알고리즘의 시간 복잡도 분석 방법
    • 분할 정복 알고리즘의 공간 복잡도 분석
  • 분할 정복과 다른 알고리즘의 비교
    • 분할 정복 알고리즘과 다른 접근 방식의 비교
    • 각각의 장단점
• 실습:
  • 다양한 분할 정복 알고리즘의 성능 비교 예제

# 성능 비교 예제: 병합 정렬 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

data = [38, 27, 43, 3, 9, 82, 10]
print("병합 정렬 시간:", measure_time(merge_sort, data.copy()))
print("퀵 정렬 시간:", measure_time(quick_sort, data.copy()))

 

Day 7: 종합 연습 및 프로젝트 준비

• 강의 내용:
  • 분할 정복 알고리즘 종합 연습
    • 다양한 분할 정복 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 분할 정복 알고리즘 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 배열을 분할 정복 알고리즘을 사용하여 정렬
2. 주어진 2차원 평면상의 점들 중 최근접 점 쌍 찾기
3. 주어진 문자열의 모든 부분 문자열을 분할 정복을 사용하여 생성

### 프로젝트 주제 예시
1. 대규모 데이터셋 분할 정복 처리 시스템
2. 분할 정복을 활용한 이미지 처리 도구
3. 분할 정복을 사용한 게임 알고리즘

### 프로젝트 요구사항 예시
1. 대규모 데이터셋 분할 정복 처리 시스템:
   - 대규모 데이터셋 입력 및 저장
   - 분할 정복 알고리즘을 통한 데이터 처리
   - 처리된 데이터 출력 및 성능 분석

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 분할 정복 알고리즘 구현 (예: 병합 정렬, 퀵 정렬 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 분할 정복 알고리즘, 특히 병합 정렬, 퀵 정렬, 최대 부분 배열 문제, 최근접 점 문제의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!