9252. [Python]LCS 2

1. 문제

 

https://www.acmicpc.net/problem/9252

 

 

2. 접근 방법

 

• 시간 제한: 2초 (Python)
• 메모리 제한: 256MB
• LCS
• DP

 

3. 파이썬 코드

 

# 재귀 제한 해제
import sys
sys.setrecursionlimit(10000)

# 재귀함수를 통해서 문자 찾기
def backtracking(start, value):
    global max_value
    global ans
    global word_two
    # 최대 길이 도달했을때 종료
    if value == 0:
        print(max_value)
        print(ans[::-1])
        exit()
    # 현재 칸에서 위로 간 값과 왼쪽으로 간 값을 비교해서 작은 값찾는 재귀
    else:
        if matrix[start[0]-1][start[1]] == value:
            backtracking([start[0]-1,start[1]],value)
        elif matrix[start[0]][start[1]-1] == value:
            backtracking([start[0],start[1]-1],value)
        # 만약 왼쪽과 위 둘다 작은 경우 왼쪽위로 인덱스 변경 후 문자 저장
        elif matrix[start[0]-1][start[1]] < value and matrix[start[0]][start[1]-1] < value:
            ans += word_two[start[1]-1]
            backtracking([start[0]-1,start[1]-1],value-1)


word_one = input()
word_two = input()

one_length = len(word_one)
two_length = len(word_two)

matrix = [[0]* (two_length+1) for _ in range(one_length+1)]
max_value = 0
ans = ""
# LCS 구하는 알고리즘
for i in range(one_length+1):
    for j in range(two_length+1):
        if i == 0 or j == 0:
            continue
        else:
            if word_two[j-1] == word_one[i-1]:
                matrix[i][j] = matrix[i-1][j-1] + 1
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    if matrix[i][j] > max_value:
        max_value = matrix[i][j]
if max_value == 0:
    print(0)
else:
    backtracking([one_length,two_length],max_value)

 

4. 문제를 풀고난 후 생각

 

• LCS(최장 공통 부분 수열)을 구할 수 있다면 맨 마지막 인덱스에서 백트래킹을 통해서 문자열까지 찾을 수 있다.
• 효율적인 방법이라고는 할 수 없지만 현재 내가 구현할 수 있는 방법에 있어서는 최선이였다.
• 현재 인덱스에서 위 값과 왼쪽 값을 비교하여 같은 경우를 우선으로 하여 탐색을 진행했으며 들어가며 위와 왼쪽 모두 값이 작은 경우 인덱스를 각각 -1, -1 해준 후 백트래킹을 계속 진행시켰다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• LCS(최장 공통 부분 수열)
• DP