지나가던 개발자
[Python] 백준 9251번(LCS) 문제 풀이 본문
s1 = input()
s2 = input()
lcs = [[0 for col in range(len(s1)+1)] for row in range(len(s2)+1)]
for i in range(1, len(s2)+1):
for j in range(1, len(s1)+1):
if s1[j-1] == s2[i-1]:
lcs[i][j] = lcs[i-1][j-1]+1
continue
lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])
print(max(sum(lcs, [])))
이 문제를 풀고 솔브닥 골드가 되었다...!
LCS를 구하는 알고리즘을 설명한 글은 밑에다가 첨부해 놓겠다. 내가 글을 하나 쓸까 하는 생각도 했지만 밑의 블로그가 너무 잘 써서 그걸 보는 편이 나을 듯 하다.
근데 Python3로 제출하면 시간 초과가 뜨고 PyPy3로 제출해야 맞았다고 뜬다. Python3보다 PyPy3가 빠른데 둘 다 시간 제한이 2초여서 그런 듯 하다.
이 글을 쓰는 데 도움이 되었던 자료들:
[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io
[Python] 길이가 정해진 리스트 만들기
파이썬에서 리스트를 생성할 때는 그저 아래와 같이 작성하면 쉽게 리스트가 생성이 된다. list = [] 리스트 길이를 지정하고 0으로 초기화 하고 싶다면 다음과 같이 작성하면 된다. list = [0 for i in
jobc.tistory.com
'PS > Python' 카테고리의 다른 글
| [Python] 백준 6679번(싱기한 네자리 숫자) 문제 풀이 (0) | 2022.10.13 |
|---|---|
| [Python] 백준 17413번(단어 뒤집기 2) 문제 풀이 (0) | 2022.10.12 |
| [Python] 백준 11719번(그대로 출력하기 2) 문제 풀이 (0) | 2022.10.10 |
| [Python] 백준 1316번(그룹 단어 체커) 문제 풀이 (0) | 2022.10.10 |
| [Python] 백준 1759번(암호 만들기) 문제 풀이 (0) | 2022.10.09 |
'PS/Python' Related Articles
more
Comments