이번 커밋에서는 알고리즘 스터디 그룹 프로젝트 '2026-1-Algorithm-assignments'의 02주차 문제 풀이 코드를 추가했습니다. 이 과정에서 바이너리 서치, 첫 번째 나쁜 버전 찾기, 피보나치 수열 계산, 행렬 곱셈 알고리즘 구현 및 테스트 코드를 작성했습니다.

2026-1-Algorithm-assignments: 알고리즘 문제 풀이 코드 추가

요약

GitHub 커밋 메시지는 "commit 1234567890abcdef1234567890abcdef12345678"입니다. 이 커밋은 2026년 3월 17일에 이루어졌으며, 'Week02_problem-1' 디렉토리 내의 네 가지 알고리즘 문제에 대한 파이썬 코드와 테스트 케이스를 추가했습니다. 총 322줄의 코드가 추가되었습니다.

배경 및 목적

본 프로젝트는 CSE304-2026-1-Algorithms 강의에서 요구하는 알고리즘 문제 해결 능력을 향상시키기 위해 진행되었습니다. 이번 작업은 02주차에 해당하는 바이너리 서치, 첫 번째 나쁜 버전 찾기, 피보나치 수열, 행렬 곱셈 알고리즘을 파이썬으로 구현하고, 각 알고리즘의 정확성을 검증하기 위한 테스트 코드를 작성하는 것을 목적으로 합니다.

구현 내용

이번 커밋에서는 네 개의 파이썬 파일에 걸쳐 알고리즘 구현 및 테스트 코드가 추가되었습니다.

변경된 파일 목록

Week02_problem-1/1.4.matrixmult_problem.py
Week02_problem-1/1.5.binsearch_problem.py
Week02_problem-1/1.7.fib2_problem.py
Week02_problem-1/leetcode_278_problem.py

총 322줄의 코드가 추가되었으며, 기존 코드는 수정되지 않았습니다.

주요 변경사항 상세 설명

1. `Week02_problem-1/1.5.binsearch_problem.py`

바이너리 서치 알고리즘을 구현하는 binsearch 함수와 다양한 테스트 케이스를 실행하는 test_case 함수를 추가했습니다. binsearch 함수는 정렬된 리스트 S에서 값 x의 위치를 찾아 반환하며, 찾지 못하면 -1을 반환합니다. test_case 함수는 주어진 입력과 예상 결과를 비교하여 테스트 성공 여부를 출력합니다.

def binsearch(n, S, x):
    low = 0
    high = n - 1

    while low <= high:
        mid = (low + high) // 2

        if S[mid] == x:
            return mid
        if S[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return -1

2. `Week02_problem-1/leetcode_278_problem.py`

LeetCode 278번 문제 'First Bad Version'을 해결하는 firstBadVersion 함수를 Solution 클래스 내부에 구현했습니다. 이 함수는 이진 탐색을 사용하여 첫 번째 나쁜 버전을 효율적으로 찾습니다. isBadVersion 함수는 외부에서 제공되는 API로 가정되며, test_case 함수는 다양한 n 값과 예상되는 첫 번째 나쁜 버전에 대해 시간 초과와 결과 정확성을 검증합니다.

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n

        while left < right:
            mid = left + (right - left) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        return left

3. `Week02_problem-1/1.7.fib2_problem.py`

피보나치 수열의 n번째 항을 계산하는 fib2 함수를 반복문을 사용하여 구현했습니다. 일반적인 재귀 방식보다 효율적인 방법입니다. test_case 함수는 주어진 n에 대한 계산 결과와 예상 결과를 비교하고 실행 시간을 측정하여 출력합니다.

def fib2(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

4. `Week02_problem-1/1.4.matrixmult_problem.py`

두 n x n 행렬 A와 B의 곱셈 결과를 계산하는 matrixmult 함수를 구현했습니다. 기본적인 삼중 루프를 사용하여 표준 행렬 곱셈 방식을 따릅니다. test_case 함수는 주어진 행렬 A, B와 예상되는 결과 행렬을 비교합니다.

def matrixmult(n, A, B):
    # n x n result matrix initialized with zeros
    C = [[0] * n for _ in range(n)]

    # Standard matrix multiplication: C[i][j] = sum(A[i][k] * B[k][j])
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]

    return C

기술적 의사결정

이번 작업에서는 특별한 라이브러리 선택이나 기술적 의사결정은 없었습니다. 각 문제는 파이썬의 기본 기능을 활용하여 구현되었습니다. 예를 들어, 피보나치 수열 계산 시 재귀 대신 반복문을 사용한 것은 스택 오버플로우를 방지하고 성능을 향상시키기 위한 일반적인 선택입니다.

배운 점 및 개선점

배운 점:
- 각 알고리즘의 시간 복잡도를 고려하여 효율적인 구현 방식을 선택하는 연습을 할 수 있었습니다. 예를 들어, 피보나치 수열에서 반복문 기반의 O(n) 구현이 재귀 기반의 O(2^n) 구현보다 훨씬 효율적임을 다시 한번 확인했습니다.
- 알고리즘의 정확성을 검증하기 위한 체계적인 테스트 케이스 작성의 중요성을 알게 되었습니다. 엣지 케이스(빈 리스트, 단일 요소 리스트 등)를 포함한 다양한 테스트 케이스를 통해 알고리즘의 견고성을 높일 수 있습니다.
- LeetCode 문제 풀이를 통해 실제 코딩 테스트 환경에서 자주 접하는 문제 유형과 해결 방식을 익힐 수 있었습니다.
개선점:
- 현재 구현된 행렬 곱셈 알고리즘은 O(n^3)의 시간 복잡도를 가집니다. 행렬 크기가 커질 경우 성능 문제가 발생할 수 있으므로, 향후 Strassen 알고리즘 등 더 효율적인 행렬 곱셈 알고리즘을 탐구하고 구현하는 것을 고려해볼 수 있습니다.
- 각 테스트 케이스에 대한 실행 시간 측정은 현재 time 모듈을 사용하고 있으나, 더 정밀한 측정이 필요하다면 timeit 모듈 등을 활용할 수 있습니다.
다음 단계 계획:
- 03주차 알고리즘 문제 풀이를 진행합니다.
- 현재 구현된 알고리즘들의 성능 개선 방안을 적극적으로 모색하고, 필요하다면 최적화된 코드로 리팩토링합니다.

참고 자료

LeetCode 278. First Bad Version
CSE304-2026-1-Algorithms 강의 자료 (강의 및 과제 정보)