목록5582 DP (1)

Gemstone's Devlog

[백준] 5582번: 공통 부분 문자열 (다이나믹 프로그래밍)

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 이 문제는 DP로 접근해야하는 문제이다. 이중 for문을 돌다가 같은 문자를 만나게 되면 그전까지의 공통 부분 문자열 길이 +1을 dp에 저장한다. 파이썬 코드 ans = 0 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 ..
Data Structure & Algorithms 2022. 3. 31. 00:29
이전 Prev 1 Next 다음