Brute-force의 지수적 복잡도를 O(m·n)으로 최적화한 DP 패턴 적용 사례

Context

문자열 간 최소 편집 거리(Edit Distance) 산출을 위해 Brute-force Recursion 구조 채택. 입력 문자열 길이가 20자 수준의 소규모 데이터에서도 중복 계산으로 인한 CPU 리소스 과점 및 성능 저하 발생.

Technical Solution

• Optimal Substructure와 Overlapping Subproblems 특성을 식별하여 Dynamic Programming 패턴 적용
• '현재 상태를 만드는 마지막 결정(Last Decision)'에 집중하여 Replace, Insert, Delete의 세 가지 상태 전이 정의
• 하위 문제의 해를 저장하는 2차원 DP Table(dp[i][j])을 설계하여 중복 계산 제거
• Base Case로 빈 문자열 간의 변환 비용을 설정하여 재귀의 기저 조건 확보
• 반복문을 통한 Bottom-up 방식으로 테이블을 채워 Stack Overflow 위험 제거 및 실행 속도 최적화

Impact

• 시간 복잡도 및 공간 복잡도를 지수 시간에서 O(m·n) 수준의 다항 시간으로 개선