[DP: LCS 최장 공통 부분수열 Longest Common Subsequence]

4가지 LCS (Longest Common Subsequence) 알고리즘 버전

 

✅ 1. DFS (Brute Force) — 시간복잡도: O(2^(n + m))

# 완전탐색 방식: 모든 경우를 재귀로 탐색
# 시간 복잡도: O(2^(n+m)), 공간 복잡도: O(n+m) (재귀 스택)
def dfs(s1, s2):
    return dfsHelper(s1, s2, 0, 0)

def dfsHelper(s1, s2, i1, i2):
    # 기저 조건: 두 문자열 중 하나라도 끝에 도달하면 LCS는 0
    if i1 == len(s1) or i2 == len(s2):
        return 0
    
    # 현재 문자가 같으면 두 포인터를 모두 이동시키고 +1
    if s1[i1] == s2[i2]:
        return 1 + dfsHelper(s1, s2, i1 + 1, i2 + 1)
    else:
        # 다르면 두 가지 경우 중 최대 선택
        # 1. i1만 증가시키는 경우
        # 2. i2만 증가시키는 경우
        return max(dfsHelper(s1, s2, i1 + 1, i2),
                   dfsHelper(s1, s2, i1, i2 + 1))

---

✅ 2. DFS + 메모이제이션 (Top-Down DP) — 시간복잡도: O(n * m)

# 재귀에 캐시를 더한 방식: 중복 계산을 방지하여 성능 향상
# 시간 복잡도: O(n*m), 공간 복잡도: O(n*m) (캐시 + 재귀 스택)
def memoization(s1, s2):
    N, M = len(s1), len(s2)
    
    # 캐시 초기화: -1은 아직 계산되지 않았음을 의미
    cache = [[-1] * M for _ in range(N)]
    
    return memoHelper(s1, s2, 0, 0, cache)

def memoHelper(s1, s2, i1, i2, cache):
    # 기저 조건
    if i1 == len(s1) or i2 == len(s2):
        return 0
    
    # 캐시에 값이 이미 계산되어 있으면 바로 리턴
    if cache[i1][i2] != -1:
        return cache[i1][i2]

    # 문자가 같으면 좌상단 대각선 방향으로 이동 +1
    if s1[i1] == s2[i2]:
        cache[i1][i2] = 1 + memoHelper(s1, s2, i1 + 1, i2 + 1, cache)
    else:
        # 다르면 두 방향 중 최대값 선택
        cache[i1][i2] = max(memoHelper(s1, s2, i1 + 1, i2, cache),
                            memoHelper(s1, s2, i1, i2 + 1, cache))
    
    return cache[i1][i2]

---

✅ 3. Bottom-Up DP (2D 테이블) — 시간복잡도: O(n * m)

# 이차원 DP 테이블 방식 (반복문 기반)
# dp[i+1][j+1] = s1[0~i]와 s2[0~j]까지의 LCS 길이
def dp(s1, s2):
    N, M = len(s1), len(s2)
    
    # N+1 x M+1 크기의 DP 테이블 (0으로 초기화)
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(N):
        for j in range(M):
            if s1[i] == s2[j]:
                # 문자가 같으면 좌상단 대각선에서 +1
                dp[i + 1][j + 1] = 1 + dp[i][j]
            else:
                # 다르면 왼쪽 또는 위쪽 중 큰 값 선택
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    
    # 최종 결과는 오른쪽 아래칸
    return dp[N][M]

---

✅ 4. 메모리 최적화 DP — 시간복잡도: O(n * m), 공간복잡도: O(m)

# 공간 최적화: 두 행만 번갈아 사용하여 메모리 절약
# 항상 이전 행(dp)과 현재 행(curRow)만 필요함
def optimizedDp(s1, s2):
    N, M = len(s1), len(s2)

    # 이전 행을 저장할 리스트
    dp = [0] * (M + 1)

    for i in range(N):
        # 현재 행 초기화
        curRow = [0] * (M + 1)
        for j in range(M):
            if s1[i] == s2[j]:
                # 문자가 같으면 대각선(dp[j])에서 +1
                curRow[j + 1] = 1 + dp[j]
            else:
                # 다르면 왼쪽 또는 위쪽 중 큰 값 선택
                curRow[j + 1] = max(dp[j + 1], curRow[j])
        
        # 현재 행을 이전 행으로 갱신
        dp = curRow

    # 마지막 값이 정답
    return dp[M]

---

🧠 참고: 4가지 방법 요약

방법	시간복잡도	공간복잡도	특징
DFS (재귀 완전탐색)	O(2^(n+m))	O(n+m)	느리고 비효율적
메모이제이션 (Top-Down)	O(n*m)	O(n*m)	중복 호출 제거
Bottom-Up DP	O(n*m)	O(n*m)	직관적 반복문
메모리 최적화 DP	O(n*m)	O(m)	실무에서 가장 효율적

---

Longest Common Subsequence 자체(문자열) 를 구하는 방법을 설명하고 코드를 드릴게요.

---

✅ LCS 문자열을 복원하는 방법

핵심 아이디어

• dp[i][j]는 s1[0..i-1]와 s2[0..j-1]까지의 LCS 길이를 의미해요.
• 문자열 자체를 구하려면, dp 배열을 끝에서부터 역추적(backtrack) 해서 어떤 문자가 LCS에 포함되었는지 알아내야 해요.

---

✅ 코드 + 주석

def lcsString(s1: str, s2: str) -> str:
    N, M = len(s1), len(s2)
    
    # 1. DP 테이블 초기화 (LCS 길이 저장용)
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    # 2. DP 테이블 채우기 (Bottom-up)
    for i in range(N):
        for j in range(M):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
	
    """
    # 3. 문자열 복원 (역추적)
    """
    i, j = N, M
    lcs = []

    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            # 현재 문자가 같으면 LCS에 포함됨
            lcs.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            # 위쪽 값이 더 크면 위로 이동
            i -= 1
        else:
            # 왼쪽 값이 더 크거나 같으면 왼쪽으로 이동
            j -= 1
	
    """
    # 4. 뒤집어서 리턴 (역순으로 추적했기 때문)
    """
    return ''.join(reversed(lcs))

---

✅ 예시

print(lcsString("abcde", "ace"))  # 출력: "ace"
print(lcsString("AGGTAB", "GXTXAYB"))  # 출력: "GTAB"

---

💡 포인트 정리

• DP로 길이 계산 → dp[i][j]
• 역추적으로 문자 추출 → 조건: s1[i-1] == s2[j-1]일 때 LCS 문자
• 거꾸로 탐색했으므로 결과를 뒤집기

✅ 상황 설명

elif dp[i - 1][j] > dp[i][j - 1]:
    i -= 1  # 위쪽으로 이동
else:
    j -= 1  # 왼쪽으로 이동

이 코드는 아래 상황에서 실행돼요:

• s1[i-1] != s2[j-1]: 즉, 두 문자가 서로 다를 때
• dp[i][j]는 이전 단계에서 dp[i-1][j] 또는 dp[i][j-1] 중 큰 값을 가져왔을 거예요.

---

✅ 의미 설명

방향	의미
dp[i-1][j] > dp[i][j-1] → 위로 이동 (i -= 1)	s1[i-1] 문자를 버리고 LCS를 만든 것이 더 길었음을 의미
반대 → 왼쪽으로 이동 (j -= 1)	s2[j-1] 문자를 버리고 만든 경우가 더 유리했음을 의미

즉, 어떤 문자를 포함시키지 않을지를 판단하는 로직입니다.