이번 커밋에서는 이항 계수(Combinations)와 플로이드-워셜 알고리즘을 동적 계획법(Dynamic Programming, DP) 방식으로 구현했습니다. 이전에는 직접적인 공식이나 재귀를 사용했던 방식에서 벗어나, DP 테이블을 활용하여 더 효율적이고 체계적인 문제 해결 방법을 모색했습니다.

2026-1-Algorithm-assignments: 이항 계수 및 플로이드-워셜 알고리즘 DP 구현

요약

2026년 4월 7일에 진행된 이번 작업에서는 Week05_problem 디렉토리 내의 파이썬 파일들을 수정했습니다. 3.2.bin2_problem.py 파일에서는 이항 계수를 DP 방식으로 구현했고, 3.4.floyd2_problem.py 파일에서는 플로이드-워셜 알고리즘을 DP 방식으로 구현했습니다. 또한 LeetCode 문제 해결을 위한 leetcode_1334_problem.py 파일도 DP를 적용하여 업데이트했으며, VS Code 설정을 위한 .vscode/settings.json 파일도 추가되었습니다. 총 398라인의 코드가 추가되었습니다.

배경 및 목적

알고리즘 학습 과정에서 동적 계획법(DP)은 중요한 주제입니다. DP는 큰 문제를 작은 하위 문제로 나누어 해결하고, 중복되는 계산을 피하기 위해 하위 문제의 해답을 저장하는 기법입니다. 이번 작업의 목적은 이항 계수와 플로이드-워셜 알고리즘을 DP 방식으로 구현함으로써 DP의 원리를 깊이 이해하고, 실제 알고리즘 문제 해결에 적용하는 능력을 키우는 것입니다.

구현 내용

3.2.bin2_problem.py - 이항 계수(Combinations) DP 구현

이항 계수 C(n, k)를 계산하기 위해 파스칼의 삼각형 원리를 이용하는 DP 테이블을 사용했습니다.

변경 파일: Week05_problem/3.2.bin2_problem.py
추가 라인: 103
삭제 라인: 0
핵심 코드 설명:
- B라는 2차원 리스트를 (n+1) x (k+1) 크기로 생성하여 B[i][j]는 C(i, j) 값을 저장하도록 합니다.
- 테이블의 첫 행과 첫 열 (또는 대각선 j=i까지)을 1로 초기화합니다. B[i][0] = 1 (n개 중 0개를 선택하는 경우의 수는 1)과 B[i][i] = 1 (n개 중 n개를 선택하는 경우의 수는 1)을 처리합니다.
- 점화식 B[i][j] = B[i-1][j-1] + B[i-1][j]를 사용하여 테이블 내부 값을 채워나갑니다. 이는 C(i, j) = C(i-1, j-1) + C(i-1, j)라는 이항 계수의 성질을 이용한 것입니다.
- 계산은 i가 2부터 n까지, j가 1부터 min(i, k)까지 반복하며 진행됩니다. min(i, k)를 사용하는 이유는 k를 넘어서는 열은 최종 결과 B[n][k] 계산에 필요 없기 때문입니다.

def bin2(n, k):
    B = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        B[i][0] = 1
        if i <= k:
            B[i][i] = 1
    for i in range(2, n + 1):
        for j in range(1, min(i, k) + 1):
            B[i][j] = B[i - 1][j - 1] + B[i - 1][j]
    return B[n][k]

3.4.floyd2_problem.py - 플로이드-워셜 알고리즘 DP 구현

플로이드-워셜 알고리즘은 모든 쌍의 꼭짓점 간의 최단 경로를 찾는 알고리즘입니다. DP 테이블을 사용하여 점진적으로 최단 거리를 갱신합니다.

변경 파일: Week05_problem/3.4.floyd2_problem.py
추가 라인: 171
삭제 라인: 0
핵심 코드 설명:
- D[i][j]는 정점 i에서 정점 j까지의 최단 거리를 저장하는 DP 테이블입니다. 초기값은 입력된 가중치 행렬 W입니다.
- P[i][j]는 i에서 j까지의 최단 경로를 반으로 쪼갤 때 중간 정점 k를 저장하는 테이블로, 경로 재구성 시 사용됩니다.
- 세 개의 중첩된 반복문 (k, i, j)을 사용하여 모든 정점 k를 경유하는 경우를 고려하여 D[i][j] 값을 갱신합니다.
- if D[i][k] + D[k][j] < D[i][j]: 조건은 정점 i에서 k를 거쳐 j로 가는 경로가 기존의 i에서 j로 가는 최단 경로보다 짧은지를 확인합니다. 짧다면 D[i][j]를 갱신하고 P[i][j]에 k를 저장합니다.
- path(i, j) 함수는 P 테이블을 재귀적으로 사용하여 실제 최단 경로를 출력합니다.

def floyd2(n, W):
    P = [[-1] * n for _ in range(n)]
    D = [row[:] for row in W]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
                    P[i][j] = k
    return D, P

leetcode_1334_problem.py - LeetCode 문제 DP 적용

주어진 LeetCode 문제 findTheCity 역시 모든 도시 쌍 간의 최단 거리를 구해야 하므로 플로이드-워셜 알고리즘을 적용했습니다.

변경 파일: Week05_problem/leetcode_1334_problem.py
추가 라인: 121
삭제 라인: 0
핵심 코드 설명:
- dist 테이블을 n x n 크기로 생성하고, 초기에는 간선 정보를 바탕으로 거리를 설정합니다. 자기 자신으로의 거리는 0으로 초기화합니다.
- 플로이드-워셜 알고리즘을 동일하게 적용하여 모든 도시 쌍의 최단 거리를 계산합니다.
- 계산된 dist 테이블을 바탕으로 각 도시 i에서 distanceThreshold 이하로 도달 가능한 다른 도시(j)의 개수를 셉니다.
- 가장 적은 수의 도달 가능한 도시를 가진 도시 번호를 찾고, 만약 동률이면 도시 번호가 더 큰 도시를 선택하여 반환합니다.

def findTheCity(n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    city = -1
    min_count = float('inf')
    for i in range(n):
        count = 0
        for j in range(n):
            if i != j and dist[i][j] <= distanceThreshold:
                count += 1
        if count < min_count or (count == min_count and i > city):
            min_count = count
            city = i
    return city

Week05_problem/.vscode/settings.json - VS Code 설정 추가

VS Code에서 파이썬 환경 설정을 위한 settings.json 파일을 추가했습니다.

변경 파일: Week05_problem/.vscode/settings.json
추가 라인: 3
삭제 라인: 0

기술적 의사결정

이항 계수 계산 시, 직접적인 팩토리얼 함수를 사용하는 대신 DP 테이블을 선택했습니다. 팩토리얼 함수는 n이 커짐에 따라 매우 큰 값을 반환하게 되어 오버플로우의 위험이 있습니다. 또한, 같은 C(n, k) 값을 여러 번 계산하는 중복 계산이 발생할 수 있습니다. DP 테이블을 사용하면 C(i, j) 값을 한 번만 계산하여 저장하고, 이를 활용하여 C(n, k)를 효율적으로 계산할 수 있습니다. 이는 큰 n 값에서도 안정적이고 빠른 계산을 보장합니다.

플로이드-워셜 알고리즘의 경우, 각 정점 쌍 간의 모든 최단 경로를 구해야 하므로 DP 방식이 자연스럽습니다. 만약 특정 시작점과 끝점 사이의 최단 경로만 필요하다면 다익스트라 알고리즘과 같은 다른 알고리즘을 고려할 수 있지만, 이 문제에서는 모든 쌍의 최단 거리가 필요하므로 플로이드-워셜이 적합합니다.

배운 점 및 개선점

배운 점

이항 계수 계산에 DP 테이블을 적용하여 팩토리얼 오버플로우 문제를 해결하고 중복 계산을 방지하는 방법을 배웠습니다.
플로이드-워셜 알고리즘의 DP 구조와 k를 경유 정점으로 허용하며 D[i][j]를 갱신하는 원리를 확실히 이해했습니다.
LeetCode와 같은 실제 문제에 DP 알고리즘을 적용하는 연습을 통해 문제 해결 능력을 향상시켰습니다.
경로 재구성(P 테이블 사용)의 필요성과 방법을 익혔습니다.

개선점

플로이드-워셜 알고리즘에서 P 테이블을 사용하여 경로를 재구성하는 로직을 좀 더 명확하게 이해하고, 다양한 케이스에 적용해 볼 필요가 있습니다.
bin2 함수의 경우, k가 n보다 클 때의 예외 처리나 min(i, k) 부분을 더 간결하게 표현할 수 있는 방법이 있는지 추가 탐색이 필요합니다.
더 큰 데이터셋에 대한 성능 테스트를 통해 알고리즘의 효율성을 검증할 필요가 있습니다.

다음 단계 계획

이번에 구현한 알고리즘들을 복습하고, 관련 LeetCode 문제들을 더 풀어보며 숙달도를 높일 계획입니다.
DP와 관련된 다른 유형의 문제들(예: knapsack, LIS 등)을 학습하고 구현할 예정입니다.
알고리즘 복잡도 분석을 더 깊이 있게 공부하여, 각 알고리즘의 시간 및 공간 복잡도를 이해하고 최적화 방안을 모색할 것입니다.

참고 자료

CSE304-2026-1-Algorithms GitHub Repository
LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (문제 설명 및 예시)
알고리즘 관련 강의 자료 및 온라인 튜토리얼