[백준/파이썬] 15482번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 15482번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, “최백준”과 “백준온라인”의 LCS는 “백준”이고, “스타트링크”와 “스트라토캐스터”의 LCS는 “스트”이다.
입력 요약
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 최대 1000글자이고, 유니코드 U+AC00(가)부터 U+D7A3(힣)까지로만 이루어져 있으며, UTF-8로 인코딩 되어 있다.
출력 요약
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
코드
s1, s2 = input(), input()
dp = [[0]*(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]+1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
m = 0
for row in dp:
m = max(m, max(row))
print(m)
설명
핵심은 구현 관점에서 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기