Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
Tags
- 수학
- 재귀
- level2
- 딕셔너리
- 다이나믹 프로그래밍
- 파이썬
- python
- DP
- 그리디
- 힙
- 코딩테스트
- 운영체제
- 백준
- 스택
- level1
- 다익스트라
- level3
- 가상메모리 관리
- level0
- MYSQL
- N과M
- 구현
- dfs
- BOJ
- dict
- 프로그래머스
- 가상메모리
- programmers
- 브루트포스
- BFS
Archives
- Today
- Total
동캄의 코딩도장
백준 9251 [LCS] 파이썬 본문
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
알고리즘 시간에 직접 구현해 보지는 않았지만, 간단히 이론적으로 배운적이 있었다. 그때의 기억이 떠오르면서, 비교하는 것 까지는 생각이 났지만, 구체적으로 어떻게 비교를 해야할지 모르겠었다...
#백준 9251 LCS
import sys
input=sys.stdin.readline
f=list(map(str,input().rstrip()))
s=list(map(str,input().rstrip()))
f_len=len(f)
s_len=len(s)
dp=[[0]*(s_len) for _ in range(f_len)]
for j in range(s_len):
if f[0]==s[j]:
dp[0][j]=1
for i in range(f_len):
if f[i]==s[0]:
dp[i][0]=1
for i in range(1,f_len):
for j in range(1,s_len):
M=0
for k in range(i):
M=max(dp[k][j-1],M)
dp[i][j]=max(max(dp[i-1][:j]),M)
if f[i]==s[j]:
dp[i][j]+=1
for i in range(f_len):
M=max(M,max(dp[i]))
print(M)
시간 초과가 발생하였다.
고민을 하다 다른분의 코드를 참고하여 문제를 해결하였다.
#백준 9251 LCS
import sys
input=sys.stdin.readline
f=list(map(str,input().rstrip()))
s=list(map(str,input().rstrip()))
f_len=len(f)
s_len=len(s)
dp=[[0]*(s_len+1) for _ in range(f_len+1)]
for i in range(1,f_len+1):
for j in range(1,s_len+1):
if f[i-1]==s[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
print(dp[-1][-1])
대단한 분들이 많다..
'코테 > BOJ' 카테고리의 다른 글
백준 1260 [DFS와 BFS] 파이썬 (0) | 2022.02.08 |
---|---|
백준 12865 [평범한 배낭] 파이썬 (0) | 2021.12.15 |
백준 6603 [로또] 파이썬 (0) | 2021.12.02 |
백준 10974 [모든 순열] 파이썬 (0) | 2021.12.02 |
백준 15657 [N과M (8)] 파이썬 (0) | 2021.12.02 |