알고리즘
[백준] 9251 LCS Python
아람2
2024. 9. 30. 14:05
반응형
1. 문제
두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다
예를 들어, ACAYKP 와 CAPCAK 의 LCS 는 ACAK 가 된다
2. 요구사항
시간 제한 0.1초
메모리 제한 256MB
3. 알고리즘 분류
* 다이나믹 프로그래밍
* 문자열
4. 접근 방식
ㄷㅎ님이 기깔나게 설명해 주신 LCS 알고리즘을 이용하여 풀었다 LCS 알고리즘 정리한 내용
문제에서 문자열 A "ACATKP" 과 문자열 B "CAPCAK" 을 비교한 내용을 표로 정리하면 아래와 같다
| 0 | A | C | A | Y | K | P | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| A | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| P | 0 | 1 | 1 | 2 | 2 | 2 | 3 |
| C | 0 | 1 | 2 | 2 | 2 | 2 | 3 |
| A | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
| K | 0 | 1 | 2 | 3 | 3 | 4 | 4 |
0 인 행렬을 추가한 이유는 비교 과정에서 대각선 +1 과 왼쪽/ 위쪽 비교를 위해서 추가했고,
그렇기 때문에 for 문의 범위를 m/ n+1 까지로 설정하여 첫번째 행과 열이 0으로 초기화된 상태에서 비교가 가능하다
X 처리한 부분이 대각선 +1 된 부분이다
5. 전체 코드
첫번째 시도
# LCS Longest Common Subsequence 최장 공통 부분 수열
# 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
def lcs(A, B):
n = len(A) # 첫번째 배열 길이 구하기
m = len(B) # 두번째 배열 길이 구하기
# 2차원 DP 배열 초기화 (m+1 x n+1 크기)
dp = [[0] * (n+1) for _ in range(m+1)]
# DP 배열 채우기
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0: # 마진 설정
dp[i][j] = 0
# dp 는 인덱스 1부터, A B 는 인덱스 0부터 시작하기 때문에
# A[i-1] 와 B[j-1] 를 비교하여 dp[i][j] 값을 결정
elif A[i-1] == B[j-1]: # 두 문자가 같을 경우
dp[i][j] = dp[i-1][j-1] + 1
else: # 두 문자가 다를 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # 최장 공통 부분 수열 길이 반환
if __name__ == '__main__':
A = input()
B = input()
print(lcs(A, B)) # LCS 길이 출력
dp 배열은 인덱스 1부터, 문자열 A 와 B 배열은 인덱스 0부터 시작하기 때문에
A[i-1] 와 B[j-1] 를 비교하여 dp[i][j] 값을 결정한다, 그런데 인덱스 에러가 떴다
두번째 시도
# LCS Longest Common Subsequence 최장 공통 부분 수열
# 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
def lcs(A, B):
n = len(A) # 첫번째 배열 길이 구하기
m = len(B) # 두번째 배열 길이 구하기
# 2차원 DP 배열 초기화 (m+1 x n+1 크기)
dp = [[0] * (n+1) for _ in range(m+1)]
# DP 배열 채우기
for i in range(1, m+1):
for j in range(1, n+1):
# 이미 모든 dp 배열을 0 으로 초기화했으므로
# 인덱스 에러를 방지하기 위해 i, j == 0 고려하지 않음
# if i == 0 or j == 0: # 마진 설정
# dp[i][j] = 0
# dp 는 인덱스 1부터, A B 는 인덱스 0부터 시작하기 때문에
# A[i-1] 와 B[j-1] 를 비교하여 dp[i][j] 값을 결정
if A[i-1] == B[j-1]: # 두 문자가 같을 경우
dp[i][j] = dp[i-1][j-1] + 1
else: # 두 문자가 다를 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # 최장 공통 부분 수열 길이 반환
if __name__ == '__main__':
A = input().strip()
B = input().strip()
print(lcs(A, B)) # LCS 길이 출력
이미 모든 dp 배열을 선언하면서 0으로 초기화했기 때문에 인덱스 에러를 방지하기 위해
i, j == 0 조건을 없애고 A, B 입력 받을 때도 strip() 을 써줬다 그래도 인덱스 에러가 났다ㅡ.ㅡ
세번째 시도
# LCS Longest Common Subsequence 최장 공통 부분 수열
# 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
def lcs(A, B):
m = len(A) # 첫번째 배열 길이 구하기
n = len(B) # 두번째 배열 길이 구하기
# 빈 문자열이 있는 경우 0 리턴
if n == 0 or m == 0:
return 0
# 2차원 DP 배열 초기화 (m+1 x n+1 크기)
dp = [[0] * (n+1) for _ in range(m+1)]
# DP 배열 채우기
for i in range(1, m+1):
for j in range(1, n+1):
# 이미 모든 dp 배열을 0 으로 초기화했으므로
# 인덱스 에러를 방지하기 위해 i, j == 0 고려하지 않음
# if i == 0 or j == 0: # 마진 설정
# dp[i][j] = 0
# dp 는 인덱스 1부터, A B 는 인덱스 0부터 시작하기 때문에
# A[i-1] 와 B[j-1] 를 비교하여 dp[i][j] 값을 결정
if A[i-1] == B[j-1]: # 두 문자가 같을 경우
dp[i][j] = dp[i-1][j-1] + 1
else: # 두 문자가 다를 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # 최장 공통 부분 수열 길이 반환
if __name__ == '__main__':
A = input().strip()
B = input().strip()
print(lcs(A, B)) # LCS 길이 출력
사실 3번 더 인덱스 에러가 났는데,..... 코드를 다시 차근차근 읽어 보니
A 의 길이를 n, B 의 길이를 m 으로 할당하고 있었다 그래서 다시 바꿔주니 잘 동작했다
이 문제에 시간을 너무 많이 써버렸다, 정신 차리자!
# LCS Longest Common Subsequence 최장 공통 부분 수열
# 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
def lcs(A, B):
m = len(A) # 첫번째 배열 길이 구하기
n = len(B) # 두번째 배열 길이 구하기
# 빈 문자열이 있는 경우 0 리턴
if n == 0 or m == 0:
return 0
# 2차원 DP 배열 초기화 (m+1 x n+1 크기)
dp = [[0] * (n+1) for _ in range(m+1)]
# DP 배열 채우기
for i in range(1, m+1):
for j in range(1, n+1):
# 이미 모든 dp 배열을 0 으로 초기화했으므로
# 인덱스 에러를 방지하기 위해 i, j == 0 고려하지 않음
# if i == 0 or j == 0: # 마진 설정
# dp[i][j] = 0
# dp 는 인덱스 1부터, A B 는 인덱스 0부터 시작하기 때문에
# A[i-1] 와 B[j-1] 를 비교하여 dp[i][j] 값을 결정
if A[i-1] == B[j-1]: # 두 문자가 같을 경우
dp[i][j] = dp[i-1][j-1] + 1
else: # 두 문자가 다를 경우
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n] # 최장 공통 부분 수열 길이 반환
if __name__ == '__main__':
A = input().strip()
B = input().strip()
print(lcs(A, B)) # LCS 길이 출력
반응형