일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- 안드로이드
- permutation
- 1182
- Kotlin
- 백준
- 뒤로가기
- 11053
- lcm
- 매일11시
- 괄호
- 11기
- 1260
- 순열
- Android
- 최소공배수
- 9095
- itertools
- Python
- 코테
- 11057
- LCS
- 홈화면
- expo
- Combination
- 파이썬
- 6603
- 11054
- 앱
- 코틀린
- 나머지
Archives
- Today
- Total
황소개발자
LCS 최장 공통 부분 수열 : 3개일 때 길이 뿐만 아니라, 부분문자열까지 찾아내기 @@황소처럼 우직하게@@ 본문
반응형
백준 1958 파이썬 python : LCS 3 @@황소처럼 우직하게@@
처음엔 아래 코드와 같이, a b c 의 lcs 는 (a b 의 lcs) 와 (c) 의 lcs 이겠지 생각했으나 틀렸다. def lcs(a, b): dp = [[0 for i in range(len(a) + 1)] for j in range(len(b) + 1)] for i in range(1, len(b)..
hjp845.tistory.com
이전 글에서 길이를 찾아내는 문제를 풀어보았다.
이번에는 부분문자열까지 찾아내는 솔루션을 제시한다.
이런 문제가 사이트에 있을진 모르겠지만, 충분히 나올 수 있는 문제다.
lst = [input() for i in range(3)]
dp = [[[0 for i in range(len(lst[0]) + 1)] for j in range(len(lst[1]) + 1)] for k in range(len(lst[2]) + 1)]
for k in range(1, len(lst[2]) + 1):
for j in range(1, len(lst[1]) + 1):
for i in range(1, len(lst[0]) + 1):
if lst[0][i - 1] == lst[1][j - 1] == lst[2][k - 1]:
dp[k][j][i] = dp[k - 1][j - 1][i - 1] + 1
else:
dp[k][j][i] = max(dp[k - 1][j][i], dp[k][j - 1][i], dp[k][j][i - 1], dp[k - 1][j - 1][i], dp[k][j - 1][i - 1], dp[k - 1][j][i - 1])
ans = ''
now = dp[-1][-1][-1]
k = len(dp) - 1
j = len(dp[0]) - 1
i = len(dp[0][0]) - 1
while now != 0:
if now - 1 == dp[k - 1][j][i] == dp[k][j - 1][i] == dp[k][j][i - 1] == dp[k - 1][j - 1][i] == dp[k][j - 1][i - 1] == dp[k - 1][j][i - 1]:
ans = lst[0][i - 1] + ans
k -= 1
j -= 1
i -= 1
now -= 1
else:
flag = []
value = 0
if dp[k - 1][j][i] > value:
value = dp[k - 1][j][i]
flag = [k - 1, j, i]
if dp[k][j - 1][i] > value:
value = dp[k][j - 1][i]
flag = [k, j - 1, i]
if dp[k][j][i - 1] > value:
value = dp[k][j][i - 1]
flag = [k, j, i - 1]
if dp[k - 1][j - 1][i] > value:
value = dp[k - 1][j - 1][i]
flag = [k - 1, j - 1, i]
if dp[k - 1][j][i - 1] > value:
value = dp[k - 1][j][i - 1]
flag = [k - 1, j, i - 1]
if dp[k][j - 1][i - 1] > value:
value = dp[k][j - 1][i - 1]
flag = [k, j - 1, i - 1]
k, j, i = flag
print(dp[-1][-1][-1])
print(ans)
알고리즘은 간단하다
주변 6개 칸이 현재칸 값보다 다 1씩 낮다면, 현재 문자열을 ans에 추가한다. 그리고 i - 1, j - 1, k - 1 칸으로 이동한다.
그렇지 않다면
주변 6개 칸중에서 큰 값을 찾고 그 칸으로 이동한다.
0이 되면 탐색을 종료한다.
반복문으로 깔끔하게 풀 수도 있었으나, 6개정도니 그냥 if문 6개로 풀었다.
반응형
'백준 문제 풀이' 카테고리의 다른 글
백준 11724 파이썬 python : 연결 요소의 개수 @@황소처럼 우직하게@@ 런타임에러 해결, 시간초과 해결 (0) | 2020.02.21 |
---|---|
백준 1260 파이썬 python : DFS와 BFS @@황소처럼 우직하게@@ 탐색순서 주의안하면 시간초과납니다;; 최적화하기. (0) | 2020.02.20 |
백준 1958 파이썬 python : LCS 3 @@황소처럼 우직하게@@ (0) | 2020.02.20 |
백준 9252 파이썬 python LCS 2 @@황소처럼 우직하게@@ (0) | 2020.02.20 |
백준 2133 파이썬 python 타일 채우기 @@황소처럼 우직하게@@ (0) | 2020.02.20 |