AI 요약관련 정보

• LeetCode 1143번 'Longest Common Subsequence (LCS)' 문제를 자바스크립트로 동적 계획법(Dynamic Programming, DP)을 활용하여 해결하는 방법을 설명한다. 💡
• 동적 계획법은 작은 부분 문제들을 먼저 해결하고, 그 결과들을 활용하여 점진적으로 더 큰 문제의 해답을 찾아나가는 상향식(bottom-up) 접근 방식을 사용한다. 📈
• LCS 문제 해결을 위해 dp[r][c]가 text1의 처음 r개 문자와 text2의 처음 c개 문자 사이의 최장 공통 부분 수열 길이를 저장하는 2차원 DP 테이블을 사용한다. 🗺️
• DP 테이블 초기화 시, 부분 문자열의 길이가 0일 때(빈 문자열) LCS 길이는 항상 0이므로, 첫 번째 행과 열은 모두 0으로 채워진다. 📏
• 점화식 1: 현재 비교하는 두 부분 문자열의 마지막 문자가 동일할 경우, dp[r][c] = 1 + dp[r-1][c-1] 공식을 적용하여 일치하는 문자를 포함하고 이전 대각선 값을 더한다. ✅
• 점화식 2: 현재 비교하는 두 부분 문자열의 마지막 문자가 다를 경우, dp[r][c] = max(dp[r-1][c], dp[r][c-1]) 공식을 사용하여 text1 또는 text2의 마지막 문자를 제외한 LCS 중 더 큰 값을 선택한다. ❌
• 모든 DP 테이블 계산이 완료되면, dp[text1.length][text2.length]에 전체 문자열 간의 최종 LCS 길이가 저장된다. 🏆
• 2차원 DP 풀이의 시간 복잡도는 두 문자열 길이를 m, n이라 할 때 O(mn)이며, 공간 복잡도 또한 O(mn)이다. ⏱️
• 공간 복잡도 최적화를 위해, 현재 행의 값을 계산할 때 이전 행의 정보와 현재 행의 왼쪽 값만 필요하다는 점을 활용하여 prev와 curr 두 개의 1차원 배열만 사용한다. 🚀
• 1차원 DP 구현 시, 두 문자열 중 더 짧은 문자열을 기준으로 배열을 생성하고, 각 행 계산 후 curr 배열을 prev 배열로 업데이트하여 공간 복잡도를 O(min(m, n))으로 줄인다. 🔄