[Algorithm] 최장 공통 문자열(Longest Common Subsequence)

2024. 5. 1. 20:51· Computer Science/Algorithm&DataStructure
목차
  1. 최장 공통 문자열(Longest Common  Subsequence)
728x90

최장 공통 문자열(Longest Common  Subsequence)

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제
다이나믹 프로그래밍을 통해 해결한다.

 

 

 

 

ex) 백준 9252 LCS 2

 

https://www.acmicpc.net/problem/9252

ACAYKP
CAPCAK

를 입력받았을때 dp 배열

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 2, 2, 2]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 2, 3, 4]
[0, 1, 2, 3, 3, 3, 4]

import sys
from collections import deque
st1=[" "]
st2=[" "]
st1.extend(list(sys.stdin.readline().rstrip()))
st2.extend(list(sys.stdin.readline().rstrip()))


dp=[[0 for i in range(len(st2))] for i in range(len(st1))]
for i in range(1,len(st1)):
    for j in range(1,len(st2)):
        if(st1[i]==st2[j]):
            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])

dq=deque()

y=len(st1)-1
x=len(st2)-1

while dp[y][x]!=0:
    if(dp[y][x]==dp[y][x-1]):
        x-=1
        continue
    elif(dp[y][x]==dp[y-1][x]):
        y-=1
        continue 
    else:
        dq.appendleft(st2[x])
        x-=1
        y-=1
print("".join(dq))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

728x90
저작자표시 (새창열림)

'Computer Science > Algorithm&DataStructure' 카테고리의 다른 글

프로그래밍 경시대회 준비 예제코드 (자바,파이썬)  (0) 2024.10.12
[Algorithm] 유니온 파인드(Union-Find)  (0) 2024.05.01
[Algorithm] 이진탐색(Binary Search)  (0) 2024.05.01
  1. 최장 공통 문자열(Longest Common  Subsequence)
'Computer Science/Algorithm&DataStructure' 카테고리의 다른 글
  • 프로그래밍 경시대회 준비 예제코드 (자바,파이썬)
  • [Algorithm] 유니온 파인드(Union-Find)
  • [Algorithm] 이진탐색(Binary Search)
  • [Algorithm] 트리(tree)
아사_
아사_
프로그래밍 공부한거 정리해두는 메모장 블로그
아사_
개발공부 블로그
아사_
전체
오늘
어제
  • 분류 전체보기
    • FrontEnd
      • html
      • css
      • JavaScript
      • Node.js
      • React
      • React Native
    • BackEnd
      • SpringBoot
      • FastAPI
      • PHP
      • Flask
      • supabase
    • Language
      • Python
      • JAVA
      • Kotlin
      • C++
    • Development Tools
      • AWS
      • GIT,GITHUB
      • Docker
      • 메시지 브로커
      • 기타 도구,플랫폼
    • Computer Science
      • 개발지식
      • Server&Network
      • Algorithm&DataStructure
      • Security
      • DataBase
      • OS
    • AI
    • 기타
      • 잡다
      • Android
      • 도서
    • 클론코딩
      • 생활코딩 Express.js
      • 점프 투 장고
      • 생활코딩 Node.js
    • 프로젝트
      • DevQuest

인기 글

최근 글

250x250
hELLO · Designed By 정상우.v4.2.2
아사_
[Algorithm] 최장 공통 문자열(Longest Common Subsequence)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.