[백준] 9251 LCS Python

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 길이 출력