두 문자열에서 가장 긴 공통 부분 문자열(Longest Common Substring)을 찾아야 할 때, 상향식(Bottom-Up) 방식의 동적 프로그래밍(Dynamic Programming)을 활용하면 효율적으로 문제를 해결할 수 있습니다.
핵심 아이디어는 작은 하위 문제들의 해답을 미리 계산해 저장해 두고, 필요할 때마다 다시 계산하지 않고 바로 참조하는 것입니다. 이렇게 축적된 결과들을 활용하면 최종적으로 더 큰 문제의 해답을 구할 수 있습니다.
아래는 이를 구현한 예시 코드입니다.
예제 코드
def compute_lcw(string_1, string_2):
val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
for i in range(len(string_1) + 1):
val[i][len(string_2)] = 0
for j in range(len(string_2)):
val[len(string_1)][j] = 0
lcw_i = lcw_j = -1
lcw_len = 0
for i in range(len(string_1) - 1, -1, -1):
for j in range(len(string_2)):
if string_1[i] != string_2[j]:
val[i][j] = 0
else:
val[i][j] = 1 + val[i + 1][j + 1]
if lcw_len < val[i][j]:
lcw_len = val[i][j]
lcw_i = i
lcw_j = j
return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
print(string_1[lcw_i:lcw_i + lcw_len])실행 결과
The longest common substring is : bull
코드 설명
- 'compute_lcw'라는 이름의 함수를 정의하고, 두 개의 문자열을 매개변수로 전달받습니다.
- 2차원 리스트(val)를 생성하여 각 위치에서 시작하는 공통 부분 문자열의 길이를 저장합니다. 경계 조건에 해당하는 마지막 행과 열은 0으로 초기화합니다.
- 문자열의 뒤에서부터 앞으로 순회하면서 두 문자열의 각 문자를 비교합니다.
- 두 문자가 일치하지 않으면 해당 위치의 값을 0으로 설정하고, 일치하면 대각선 방향(다음 위치)의 값에 1을 더한 값을 저장합니다.
- 계산된 값이 현재까지의 최대 길이보다 크면 최대 길이와 그 시작 위치(lcw_i, lcw_j)를 갱신합니다.
- 모든 순회가 끝나면 최대 길이와 시작 인덱스 정보를 반환합니다.
- 예제에서는 'bull'과 'bullied'라는 두 문자열을 정의한 뒤 함수를 호출하고, 결과를 변수에 할당합니다.
- 공통 부분 문자열의 길이가 0보다 크면 해당 부분 문자열을 슬라이싱하여 콘솔에 출력합니다.
이 알고리즘은 시간 복잡도 O(m×n), 공간 복잡도 O(m×n)을 가지며(m, n은 각 문자열의 길이), 재귀 호출 없이 반복문만으로 해결하기 때문에 재귀 깊이 제한 걱정 없이 안정적으로 동작한다는 장점이 있습니다.