이번 커밋은 동적 계획법(Dynamic Programming, DP)의 두 가지 대표적인 문제인 계단 오르기(Climbing Stairs)와 행렬 최소 곱셈(Matrix Chain Multiplication)을 파이썬으로 구현하고 테스트하는 내용을 담고 있습니다. 2026년 4월 14일에 진행되었습니다.

2026-1-Algorithm-assignments: 동적 계획법 연습 및 알고리즘 구현

요약

이번 작업은 Week06_problem 및 Week06_problem_1 디렉토리에 있는 두 개의 파이썬 파일을 수정하고 추가하는 내용을 포함합니다. leetcode_70_problem.py 파일은 계단 오르기 문제의 DP 해법을 구현하고 테스트 코드를 추가했으며, 3.6.minmatrixmult_problem.py 파일은 행렬 최소 곱셈 문제의 DP 해법을 구현하고 테스트 코드를 추가했습니다. 또한, macOS에서 생성되는 임시 파일들을 정리하는 작업도 포함되었습니다.

배경 및 목적

알고리즘 학습 과정에서 동적 계획법은 중요한 개념입니다. 이번 작업은 DP의 원리를 이해하고 실제 문제에 적용하는 능력을 향상시키기 위해 기획되었습니다. 특히, 계단 오르기 문제는 단순한 DP 점화식을, 행렬 최소 곱셈 문제는 좀 더 복잡한 2차원 DP 테이블과 분할 정복을 활용하는 DP를 연습하는 것을 목표로 합니다.

구현 내용

이번 커밋은 총 484라인의 코드를 추가했으며, 0라인의 코드를 삭제했습니다. 주요 변경 사항은 다음과 같습니다.

변경된 파일 목록

Week06_problem/3.6.minmatrixmult_problem.py
Week06_problem/leetcode_70_problem.py
Week06_problem_1/3.6.minmatrixmult_problem.py
Week06_problem_1/__MACOSX/._3.6.minmatrixmult_problem.py (삭제됨)
Week06_problem_1/__MACOSX/._leetcode_70_problem.py (삭제됨)
Week06_problem_1/leetcode_70_problem.py

주요 변경사항 상세 설명

1. `Week06_problem/leetcode_70_problem.py` 및 `Week06_problem_1/leetcode_70_problem.py`

두 파일 모두 LeetCode 70번 문제인 '계단 오르기(Climbing Stairs)'를 DP로 해결하는 코드를 포함합니다.

DP 점화식: dp[i] = dp[i-1] + dp[i-2]
- i번째 계단에 도달하는 방법은 (i-1)번째 계단에서 한 칸 올라오거나, (i-2)번째 계단에서 두 칸 올라오는 경우의 수를 더한 것과 같습니다.
기저 사례:
- n=1: 1가지 방법 (1)
- n=2: 2가지 방법 (1+1, 2)
테스트 코드: 다양한 n 값에 대한 테스트 케이스를 추가하여 올바른 결과와 시간 초과 여부를 확인합니다. 특히, 큰 n 값에 대한 시간 복잡도 검증을 위해 타임아웃 설정을 포함했습니다. multiprocessing 모듈을 사용하여 테스트 코드를 별도의 프로세스에서 실행함으로써 타임아웃 기능을 구현했습니다.

핵심 코드 설명 ( Week06_problem_1/leetcode_70_problem.py 기준):

class Solution(object):
    def climbStairs(self, n):
        # Use dynamic programming with O(n) time.
        # Let dp[i] be the number of ways to reach step i.

        # Base case
        if n <= 1:
            return 1

        # DP 배열: dp[i] = i번째 계단에 오르는 방법의 수
        dp = [0] * (n + 1)
        dp[0] = 1 # 계단이 0개인 경우, 1가지 방법 (도착하지 않음)
        dp[1] = 1 # 1칸: 1가지 (0->1)

        # Recurrence relation: dp[i] = dp[i-1] + dp[i-2]
        # i번째 계단에는 (i-1)번째에서 1칸, 또는 (i-2)번째에서 2칸으로 올 수 있음
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

2. `Week06_problem/3.6.minmatrixmult_problem.py` 및 `Week06_problem_1/3.6.minmatrixmult_problem.py`

두 파일 모두 '행렬 최소 곱셈(Matrix Chain Multiplication)' 문제를 DP로 해결하는 코드를 포함합니다.

문제 정의: 여러 개의 행렬을 곱할 때, 곱하는 순서에 따라 스칼라 곱셈 횟수가 달라집니다. 이 문제를 해결하기 위해 곱셈 순서를 최적화하여 총 스칼라 곱셈 횟수를 최소화하는 방법을 찾습니다.
DP 접근:
- M[i][j]는 행렬 Ai부터 Aj까지의 곱셈에서 필요한 최소 스칼라 곱셈 횟수를 저장합니다.
- P[i][j]는 M[i][j]를 얻기 위한 최적의 분할점 k 값을 저장합니다.
점화식: M[i][j] = min(M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j]) for i <= k < j
- d는 행렬의 차원을 나타내는 리스트로, Ai의 크기는 d[i-1] x d[i]입니다.
최적 괄호화: order(i, j, P) 함수는 P 테이블을 사용하여 최적의 곱셈 순서를 괄호로 표현합니다.

핵심 코드 설명 ( Week06_problem_1/3.6.minmatrixmult_problem.py 기준):

# 이 함수로 i부터 j까지의 행렬 곱셈에서 최소 곱셈 횟수와 그 때의 k값을 구한다.
def minimum(i, j, M, d): # M는 최소 곱셈 횟수를 저장하는 테이블, d는 행렬의 차원을 나타내는 리스트이다.
    minvalue, mink = INF, 0 # minvalue는 현재 i, j에서 최소 곱셈 횟수를 저장하는 변수이고, mink는 그 때의 k값을 저장하는 변수이다.
    for k in range(i, j): # 분할점 k을 옮겨보면서 최소 곱셈 횟수를 계산한다. k는 (Ai) i부터 Aj-1) j-1까지 가능하다.
        value = M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j]
        if value < minvalue: # k, 즉 분할점을 Ai(Ai+1...Aj)인 i부터 (AiAi+1...Aj-1)Aj인 j-1까지 바꿔가면서 최소 곱셈 횟수를 계산한다.
            minvalue = value # 현재 분할점 k에서 최소 곱셈 횟수가 현재 i,j 조합에서 지금까지 기록된 최소횟수보다 더 작은 경우, minvalue와 mink를 업데이트한다.
            mink = k

    return minvalue, mink

# 이 함수는 n개의 행렬과 각 행렬의 차원을 나타내는 리스트 d를 입력으로 받아서, 최소 곱셈 횟수와 그 때의 M과 P 테이블을 반환한다.
def minmult(n, d):
    # 1 based indexing을 사용하기 위해서 M과 P 테이블의 크기를 (n+1) x (n+1)로 설정한다.
    # M[i][j]는 i부터 j까지의 행렬 곱셈에서 최소 곱셈 횟수를 저장하고,
    # P[i][j]는 그 때의 k값을 저장한다.
    M = [[INF] * (n + 1) for _ in range(n + 1)]
    P = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1): # 대각성분은 자기자신과의 곱이므로 0으로 초기화.
        M[i][i] = 0
    for diagonal in range(1, n): # diagonal은 diagonal은 한 행렬 입장에서 곱해질 행렬(들) 개수이다. 총 n개의 행렬이 있으므로 1~n-1까지만 가능.
        for i in range(1, (n - diagonal) + 1): # 행렬이 n개 있다고 치면 번호는 1번부터 n번까지이다.
            j = i + diagonal # 코드에서 항상 j = i + diagonal
            M[i][j], P[i][j] = minimum(i, j, M, d) # minimum은 i부터 j까지의 행렬 곱셈에서 최소 곱셈 횟수와 그 때의 k값을 구하는 함수이다. 이를 호출해 M과 P 테이블을 업데이트한다.

    return M[1][n], M, P

3. macOS 임시 파일 정리

__MACOSX 디렉토리 내의 .DS_Store와 같은 macOS에서 자동으로 생성되는 임시 파일들이 커밋에 포함되어 있었습니다. 이 파일들은 프로젝트의 실제 코드와 관련이 없으므로, 이 커밋에서 해당 파일들이 삭제되었습니다.

기술적 의사결정

계단 오르기 문제에서의 시간 제한 처리

선택 기술: multiprocessing 모듈을 사용한 서브프로세스 실행 및 signal 모듈을 사용한 타임아웃 설정.
선택 이유: LeetCode와 같은 온라인 저지 플랫폼에서는 시간 초과가 흔하게 발생하므로, 알고리즘의 효율성을 검증하기 위해 시간 제한을 두는 것이 중요합니다. multiprocessing은 메인 프로세스에 영향을 주지 않고 별도의 환경에서 코드를 실행할 수 있게 하며, signal.SIGALRM은 특정 시간 이후 예외를 발생시켜 시간 초과를 감지하는 데 유용합니다.
대안:
- 단순히 코드 실행 시간을 측정하고 출력하는 방식: 실제 시간 초과를 감지하고 테스트를 실패 처리하는 데는 부족합니다.
- threading 모듈 사용: 스레드 간의 동기화 문제가 발생할 수 있고, CPU 바운드 작업에서 GIL(Global Interpreter Lock)의 영향을 받을 수 있어 multiprocessing이 더 적합합니다.
장단점:
- multiprocessing + signal: 시간 초과를 효과적으로 감지하고 테스트할 수 있습니다. 하지만 서브프로세스 생성 및 통신 오버헤드가 발생할 수 있습니다.

DP 테이블 초기화

선택 기술: float('inf')를 사용하여 DP 테이블의 초기값을 무한대로 설정.
선택 이유: DP 문제에서 최소값을 찾을 때, 초기값을 매우 큰 값으로 설정하여 어떤 유효한 계산 값보다도 항상 크도록 만듭니다. 이는 min() 함수 등을 사용할 때 올바르게 작동하도록 보장합니다.
대안: 큰 정수 값 사용 (예: 10**9).
장단점: float('inf')는 파이썬에서 제공하는 명확한 무한대 표현으로, 어떤 정수 값보다도 크므로 계산상 오류를 줄일 수 있습니다. 큰 정수 값은 오버플로우 가능성이 있거나, 문제의 특정 제약 조건에 따라 적절한 값을 선택하기 어려울 수 있습니다.

배운 점 및 개선점

배운 점

동적 계획법의 두 가지 중요한 예제인 계단 오르기 문제와 행렬 최소 곱셈 문제를 직접 구현하면서 DP의 점화식 설정과 테이블 채우기 과정을 익혔습니다.
행렬 최소 곱셈 문제에서 2차원 DP 테이블과 분할 정복 개념을 함께 활용하는 방법을 배웠습니다.
테스트 코드 작성 시, 시간 복잡도 검증을 위한 타임아웃 기능을 구현하는 방법을 익혔습니다. multiprocessing 모듈을 활용하여 안전하게 테스트를 진행할 수 있음을 알게 되었습니다.
macOS에서 생성되는 불필요한 임시 파일들을 커밋에서 제외하는 방법을 배웠습니다.

개선점

각 DP 문제에 대한 추가적인 분석 (예: 메모이제이션과의 비교)을 블로그 포스트에 포함하면 더 좋을 것 같습니다.
행렬 최소 곱셈 문제에서 최적 괄호화 순서를 재구성하는 order 함수의 동작 방식을 더 상세하게 설명하면 이해에 도움이 될 것입니다.
테스트 코드에서 multiprocessing 사용 시 발생할 수 있는 예외 처리 로직을 더 견고하게 만들 필요가 있습니다.

다음 단계 계획

이번에 구현한 DP 알고리즘들을 이용하여 다른 유사한 DP 문제들을 풀어보고, 다양한 DP 패턴을 학습할 계획입니다.
시간 복잡도 및 공간 복잡도 분석을 각 코드에 명시하여, 알고리즘의 효율성을 더 명확히 파악하도록 하겠습니다.
이후 커밋에서는 그래프 알고리즘이나 트리 알고리즘 관련 내용을 다룰 예정입니다.