[백준] 17218번: 비밀번호 만들기 (파이썬)

✅문제: 17218번

📌개념정리

(1) 동적 프로그래밍(Dynamic Programming)

• 정의: 복잡한 문제를 간단한 하위 문제로 나누어 해결하고, 이를 통해 중복 계산을 최소화하는 방법
• 서브문제의 결과를 저장하고 재사용함으로써 계산 시간을 효율적으로 단축함.

(2) 최장 공통 부분 수열(Longest Common Subsequence, LCS)

• 정의: 두 시퀀스에서 순서를 유지하면서 둘 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제
• LCS는 문자열 비교, 데이터 동기화, 생물학적 서열 분석 등 다양한 분야에서 활용됨.

📌문제풀이

두 문자열 사이의 최장 공통 부분 수열을 구하는 문제임. 각 문자열을 순차적으로 비교하면서 공통 문자를 발견할 때마다 결과 문자열에 추가함.

1. 두 문자열의 길이에 대한 2차원 리스트(dp)를 초기화하여, 각 셀에 최장 공통 부분 수열을 저장
2. 외부 반복문(i)을 통해 첫 번째 문자열을 순회하고, 내부 반복문(j)을 통해 두 번째 문자열을 순회
3. 두 문자열의 현재 문자(s1[i-1], s2[j-1])가 일치하는 경우, dp[i][j]를 dp[i-1][j-1]에 현재 문자를 추가하여 업데이트
4. 문자가 다른 경우, 이전까지의 최장 부분 수열 중 더 긴 것을 선택하여 dp[i][j]에 저장

def solution(s1, s2):
    # 2차원 배열 초기화
    dp = [['' for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]
    
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            # 현재 위치의 문자가 일치하는 경우
            if s1[i-1] == s2[j-1]:
                # 이전 위치의 최장 공통 부분 수열에 현재 문자를 추가
                dp[i][j] = dp[i-1][j-1] + s1[i-1]
            # 문자가 일치하지 않는 경우
            else:
                # 이전까지의 두 경우에서 더 긴 부분 수열을 선택
                dp[i][j] = max(dp[i-1][j], dp[i][j-1], key=len)
                
    return dp[-1][-1]

s1 = input()
s2 = input()

print(solution(s1, s2))

예제 입력 1의 두 문자열 "AUTABBEHNSA"와 "BCUAMEFKAJNA"를 사용해 dp 테이블을 생성하고, 최장 공통 부분 수열(LCS)을 추적하는 과정은 다음과 같음.

# 예제 입력 1
AUTABBEHNSA
BCUAMEFKAJNA

dp 배열은 두 문자열의 각 문자 조합에 대해 최장 공통 부분 수열을 저장하는 2차원 리스트임. 배열의 크기는 첫 번째 문자열의 길이 +1과 두 번째 문자열의 길이 +1이며, dp[i][j]는 첫 번째 문자열의 첫 i개 문자와 두 번째 문자열의 첫 j개 문자 사이의 최장 공통 부분 수열을 나타냄.

1) dp 테이블 초기화
dp[i][0]과 dp[0][j]는 모든 i와 j에 대해 빈 문자열('')로 초기화됨. 한 문자열의 길이가 0인 경우, 공통 부분 수열도 없음.

2) dp 테이블 채우기
각 문자열의 모든 문자를 비교하며, 같은 문자가 발견될 경우 이전 값(dp[i-1][j-1])에 해당 문자를 추가함. 문자가 다르면 dp[i-1][j]와 dp[i][j-1] 중 더 긴 값을 선택함.

3) dp 테이블

B

C

U

A

M

E

F

K

A

J

N

A

A

A

A

A

A

A

A

A

A

A

U

U

A

A

A

A

A

A

A

A

A

T

U

A

A

A

A

A

A

A

A

A

A

U

A

A

A

A

A

A

A

A

A

B

B

B

U

A

A

A

A

A

A

A

A

A

B

B

B

U

A

A

A

A

A

A

A

A

A

E

B

B

U

A

A

E

E

E

E

E

E

E

H

B

B

U

A

A

E

E

E

E

E

E

E

N

B

B

U

A

A

E

E

E

E

E

E

E

S

B

B

U

A

A

E

E

E

E

E

E

E

A

B

B

U

A

A

E

E

E

E

E

E

A

4) 최장 공통 부분 수열
dp 테이블의 마지막 셀(dp[11][12])에서부터 시작하여 최장 공통 부분 수열을 찾으면, "UAENA"이 두 문자열의 최장 공통 부분 수열임.

# 예제 출력 1
UAENA

📌후기

• 동적 프로그래밍을 활용하는 문제가 가장 어려운 것 같음. 관련 문제를 많이 풀어야 할 것 같음.
• 알고리즘 로직을 어떻게 짤 것인지, 생각을 많이 하게 됨.

📌참고자료

1) boyeonJ, "동적계획법(Dynamic Programming)", 2023.06.05, https://velog.io/@boyeon_jeong/동적계획법Dynamic-Programming
2) emplam27, "[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence", 2021.01.02 , https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence