Loading...

미리보기

전체 45개 스텝 중 14개만 표시

로그인하고 전체 보기

LCS (최장 공통 부분 수열)

보통

LCS (Longest Common Subsequence)

두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾습니다.

📊 복잡도

구분	복잡도
최선	O(n×m)
평균	O(n×m)
최악	O(n×m)
공간	O(n×m)

🏷️ 태그

DP문자열부분 수열

📖 개념 소개

LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 알고리즘입니다. "부분 수열"은 연속하지 않아도 되며, 원래 순서만 유지하면 됩니다.

1/45

Loading...

🎯최장 공통 부분 수열

두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾습니다! • 문자열 1: "EARTH" • 문자열 2: "HEART" "부분 수열"이란? 순서는 유지하되, 연속하지 않아도 됨! 예: "ACE"는 "ABCDE"의 부분 수열 (A_C_E)

🔒

기초 학습

LCS (최장 공통 부분 수열)

정의

LCS(Longest Common Subsequence)는 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 알고리즘입니다. "부분 수열"은 연속하지 않아도 되며, 원래 순서만 유지하면 됩니다.

핵심 특성

✓문자 일치 시: dp[i][j] = dp[i-1][j-1] + 1
✓문자 불일치 시: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
✓2D 테이블 사용: 두 문자열 각각을 행/열로
✓역추적으로 실제 LCS 문자열 복원 가능

시간 복잡도

최선

O(n×m)

평균

O(n×m)

최악

O(n×m)

공간 복잡도

O(n×m)

LCS (최장 공통 부분 수열) | AlgoNote