🔎 백준 9251번:LCS
🧐 문제 해석
- 두 문자열이 주어졌을때 가장 긴 공통 부분 수열을 구해라
- 문자열이 꼭 연속하지 않아도 된다.
🎯 목표:
두 문자열이 주어졌을때 가장 긴 공통 부분 수열의 길이를 구해야 한다.
🔍 핵심 아이디어
이 문제는 대표적인 DP(dynamic programming) 방식으로 LCS(Longest Common Subsequence) 를 찾는 문제이다.
✅ DP 테이블 용도
- dp[i][j] : i번째까지의 문자를 썼을때 가장 긴 공통 부분 수열의 길이
📌 핵심 포인트
🔶 점화식
for i in range(1,len(str1)+1):
for j in range(1,len(str2)+1):
if str1[i-1] == str2[j-1] :
dp[i][j] = dp[i-1][j-1] + 1
else :
dp[i][j] = max(dp[i-1][j],dp[i][j-1])-
현재 조사하고 있는 문자끼리 동일하다면 해당 칸의 dp값은 이전 인덱스의 문자를 비교했을때의 dp값에 1을 더한 값이다
: dp[i][j] = dp[i-1][j-1] + 1 -
현재 조사하고 있는 문자끼리 동일하지 않다면 두 문자중에 하나를 제외한 경우(하나를 사용하지 않는 경우) 중에 더 큰 값을 가져온다.
: dp[i][j] = max(dp[i-1][j],dp[i][j-1])
💯 정답
str1=input()
str2=input()
count = 0
dp = [[0] * (len(str2)+1) for _ in range(len(str1)+1)]
for i in range(1,len(str1)+1):
for j in range(1,len(str2)+1):
if str1[i-1] == str2[j-1] :
dp[i][j] = dp[i-1][j-1] + 1
else :
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[len(str1)][len(str2)])
🔎 백준 11053번:LIS
🧐 문제 해석
- n개의 숫자로 이루어진 수열이 주어진다.
- 증가하는 수열의 길이를 구해야 한다.
🎯 목표:
해당 수열이 증가하는 부분의 길이를 구해야 하며, 정답 수열에 포함되는 숫자들이 연속하지 않을 수도 있다.
🔍 핵심 아이디어
이 문제는 대표적인 DP(dynamic programming) 문제인 LIS (Longest Increasing Subsequence) 를 구하는 것이다.
✅ DP 테이블 용도
dp[i]=arr[i]를 마지막 원소로 가지는 LIS의 최대 길이
📌 핵심 포인트
🔶 점화식
for i in range(n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j]+1)- 현재 위치
i의 값을 마지막 원소로 하는 LIS를 찾는다 - 앞의 모든
j < i에 대해서:arr[j] < arr[i]인 경우,dp[j]+1이 될 수 있다
- 그 중 최대값을
dp[i]로 설정
💯 정답
n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n
for i in range(n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
📚 LIS vs LCS 비교 정리
🟩 LIS (Longest Increasing Subsequence)
| 항목 | 설명 |
|---|---|
| 정의 | 주어진 수열에서 증가하는 부분 수열 중 가장 긴 것의 길이 구하기 |
| 특징 | - 연속될 필요 없음 - 수열의 순서를 유지해야 함 |
| 접근 방식 | dp[i] = i번째 원소를 마지막으로 했을 때의 LIS 길이 |
| 시간 복잡도 | O(N^2), (이진 탐색 활용 시 O(N log N)) |
🟦 LCS (Longest Common Subsequence)
| 항목 | 설명 |
|---|---|
| 정의 | 두 수열에서 공통으로 등장하는 부분 수열 중 가장 긴 것의 길이 구하기 |
| 특징 | - 연속될 필요 없음 - 각 수열의 순서 유지 필요 |
| 접근 방식 | dp[i][j] = 첫 번째 수열의 i번째, 두 번째 수열의 j번째까지 봤을 때의 LCS 길이 |
| 시간 복잡도 | O(N×M) |
🧠 차이 요약
| 항목 | LIS | LCS |
|---|---|---|
| 수열 개수 | 1개 | 2개 |
| 조건 | 증가하는 수열 | 공통된 부분 수열 |
| 사용 예 | 정렬/정수열 분석 | 문자열 비교, 버전 차이 등 |
| 점화식 구조 | 1차원 DP | 2차원 DP |
LCS(Longest Common Subsequence)와 LIS(Longest Increasing Subsequence)는 얼핏 보면 둘 다 부분수열을 다룬다는 점에서 비슷해 보일 수 있지만 둘의 문제의 목적은 전혀 다르다.
✅ LCS는 "공통된 부분 수열"을 찾는 문제이다.
즉, 두 개의 서로 다른 문자열이 주어졌을 때, 이 둘이 공통적으로 가지고 있는 부분 수열 중에서 가장 긴 걸 찾는 게 목표이기 때문에 두 문자열을 동시에 보면서 겹치는 문자를 찾고, 그걸 이어붙이되 순서는 유지해야 한다.
때문에, 주로 2차원 DP 테이블을 사용해서 푼다.
dp[i][j]는 A 문자열의 i번째 문자까지, B 문자열의 j번째 문자까지 봤을 때의 최장 공통 부분 수열의 길이를 뜻하고 있다.
✅ LIS는 "증가하는 부분 수열"을 찾는 문제이다.
하나의 수열이 주어졌을 때, 이 안에서 숫자들이 계속 증가하는 부분 수열 중에서 가장 긴 걸 찾는 게 목표이다.
즉, LIS는 자기 자신 내부에서 증가하는 흐름을 찾는 문제고, 다른 문자열과의 비교는 없기 때문에 문제는 1차원 DP 배열로도 풀 수 있고, 더 효율적으로는 이분 탐색(logN)을 활용한 풀이도 가능하다.
