이번 커밋에서는 분할 정복 알고리즘과 관련된 문제들을 해결하고 코드를 작성했습니다. 주요 내용은 스트라센 행렬 곱셈, 퀵 정렬, 그리고 백준 11650번 좌표 정렬 문제입니다.

Algorithm-assignments: 분할 정복 알고리즘 실습 완료

요약

이번 커밋은 20260331-분할정복-4강실습완료라는 메시지와 함께 이루어졌습니다. 주요 변경사항은 스트라센 행렬 곱셈 알고리즘 구현, 퀵 정렬 알고리즘 구현, 그리고 좌표 정렬 문제 해결을 위한 퀵 정렬 기반 코드 작성입니다. 총 480라인의 코드가 추가되었으며, 3라인이 수정되었습니다.

배경 및 목적

알고리즘 강의의 네 번째 주차 실습이 완료됨에 따라, 분할 정복(Divide and Conquer) 패러다임을 적용한 다양한 알고리즘 문제 해결 능력을 향상시키는 것이 목적입니다. 구체적으로는 다음과 같은 문제들을 해결하고자 했습니다.

스트라센 행렬 곱셈: 일반적인 행렬 곱셈보다 효율적인 스트라센 알고리즘을 구현하여 큰 행렬에 대한 곱셈 성능을 개선합니다.
퀵 정렬: 분할 정복의 대표적인 정렬 알고리즘인 퀵 정렬을 직접 구현하여 그 원리를 이해하고 실제 적용합니다.
백준 11650번 좌표 정렬: 퀵 정렬을 활용하여 2차원 좌표를 효율적으로 정렬하는 방법을 학습합니다.

구현 내용

이번 커밋에서는 네 개의 파일에서 변경이 있었습니다.

Week04_problem/2.8.strassen_problem.py: 스트라센 행렬 곱셈 알고리즘을 구현했습니다.
- 주요 변경사항: 행렬을 4개의 하위 행렬로 분할하고, 재귀적으로 스트라센 알고리즘을 적용하여 곱셈 연산을 수행하는 strassen 함수를 작성했습니다. 또한, 행렬 덧셈, 뺄셈, 곱셈을 위한 Matrix 클래스를 정의하고, 분할(partition) 및 결합(combine) 함수를 구현했습니다.
- 추가/삭제 라인 수: 259라인 추가, 0라인 삭제.
- 핵심 코드 설명:
```
# ... (Matrix 클래스 정의)

def partition(n, M):
    # ... (행렬 분할 로직)
    return Matrix(m1), Matrix(m2), Matrix(m3), Matrix(m4)

def combine(n, M1, M2, M3, M4):
    # ... (분할된 행렬 결합 로직)
    return Matrix(mat)

def strassen(n, A, B):
    if n <= threshold:
        return A * B
    else:
        A11, A12, A21, A22 = partition(n, A)
        B11, B12, B21, B22 = partition(n, B)
        # ... (M1 ~ M7 계산)
        C11 = M1 + M4 - M5 + M7
        C12 = M3 + M5
        C21 = M2 + M4
        C22 = M1 - M2 + M3 + M6
        return combine(n, C11, C12, C21, C22)
```
  위 코드는 행렬 A와 B를 n x n 크기에서 n/2 x n/2 크기의 하위 행렬로 나누고, 7가지 재귀 호출(M1 ~ M7)을 통해 곱셈을 수행한 후, 이를 결합하여 최종 결과를 반환합니다.
Week04_problem/2.6.quicksort_problem.py: 퀵 정렬 알고리즘을 구현했습니다.
- 주요 변경사항: partition 함수와 quicksort 함수를 구현했습니다. partition 함수는 피벗을 기준으로 배열을 두 부분으로 나누고, quicksort 함수는 이 partition 함수를 재귀적으로 호출하여 배열을 정렬합니다.
- 추가/삭제 라인 수: 157라인 추가, 0라인 삭제.
- 핵심 코드 설명:
```
def partition(low, high, S):
    pivotitem = S[low]
    j = low
    for i in range(low + 1, high + 1):
        if S[i] < pivotitem:
            j += 1
            S[i], S[j] = S[j], S[i]
    S[low], S[j] = S[j], S[low]
    return j

def quicksort(low, high, S):
    if low < high:
        pivotpoint = partition(low, high, S)
        quicksort(low, pivotpoint - 1, S)
        quicksort(pivotpoint + 1, high, S)
```
  partition 함수는 피벗(pivotitem)보다 작은 요소들을 왼쪽으로, 큰 요소들을 오른쪽으로 모으고 피벗의 최종 위치를 반환합니다. quicksort 함수는 이 pivotpoint를 기준으로 재귀적으로 함수를 호출하여 정렬을 완성합니다.
Week04_problem/baekjoon_11650_problem.py: 백준 11650번 문제 '좌표 정렬하기'를 해결하기 위해 퀵 정렬 기반의 함수를 작성했습니다.
- 주요 변경사항: 2차원 좌표 리스트를 입력받아 x좌표 기준으로 먼저 정렬하고, x좌표가 같을 경우 y좌표 기준으로 정렬하는 quick_sort 함수를 구현했습니다.
- 추가/삭제 라인 수: 60라인 추가, 0라인 삭제.
- 핵심 코드 설명:
```
def quick_sort(points):
    if len(points) <= 1:
        return points
    pivot = points[0]
    left = []
    right = []
    for point in points[1:]:
        if point[0] < pivot[0] or (point[0] == pivot[0] and point[1] < pivot[1]):
            left.append(point)
        else:
            right.append(point)
    return quick_sort(left) + [pivot] + quick_sort(right)
```
  이 함수는 일반적인 퀵 정렬과 유사하게 동작하지만, 비교 조건에 x좌표뿐만 아니라 y좌표도 포함하여 두 차원에서의 정렬을 올바르게 수행합니다.
Week03_problem/leetcode_215_problem.py: LeetCode 215번 문제 'K번째로 큰 원소 찾기'에서 사용되는 mergeSort 함수와 merge 함수 내의 주석을 수정했습니다.
- 주요 변경사항: mergeSort 함수의 기저 케이스 설명을 명확히 하고, merge 과정에서의 정렬 시작 시점에 대한 설명을 보충했습니다.
- 추가/삭제 라인 수: 4라인 추가, 3라인 삭제.

기술적 의사결정

이번 커밋에서는 명시적인 새로운 기술이나 라이브러리 선택은 없었습니다. 기존에 학습한 알고리즘을 직접 구현하는 데 집중했습니다.

배운 점 및 개선점

배운 점:
- 스트라센 알고리즘의 분할, 재귀 호출, 결합 과정을 통해 분할 정복의 강력함을 다시 한번 확인할 수 있었습니다.
- 퀵 정렬의 partition 로직을 직접 구현하면서, 피벗 선택과 요소 이동 방식이 정렬 성능에 미치는 영향을 이해했습니다.
- 좌표 정렬 문제에서, 복합적인 비교 조건(x좌표 우선, y좌표 차선)을 퀵 정렬의 비교 로직에 적용하는 방법을 배웠습니다.
- 주석을 통해 코드의 의도를 명확히 전달하는 것의 중요성을 다시 한번 느꼈습니다.
개선점:
- 스트라센 알고리즘의 경우, threshold 값을 조절하며 성능을 비교하는 테스트 코드가 포함되어 있어 알고리즘의 효율성을 다양한 관점에서 검증할 수 있습니다.
- 퀵 정렬 구현 시, 실제 환경에서는 피벗 선택 전략(예: 중앙값 선택)을 개선하여 최악의 경우(O(n^2))를 방지하는 것이 중요합니다.
- 좌표 정렬에서 사용된 퀵 정렬은 기본 구현이며, 대규모 데이터셋에서는 더 효율적인 파이썬 내장 sort 함수나 다른 정렬 알고리즘을 고려할 수 있습니다.
다음 단계 계획:
- 이번에 구현한 알고리즘들을 활용하여 추가적인 알고리즘 문제를 풀어보겠습니다.
- 다른 분할 정복 알고리즘(예: 병합 정렬, 이진 탐색)을 학습하고 구현할 예정입니다.

참고 자료

알고리즘 강의 자료 (CSE304-2026-1-Algorithms)
백준 온라인 저지 (https://www.acmicpc.net/problem/11650)
LeetCode (https://leetcode.com/problems/kth-largest-element-in-an-an-array/)