Po_tta_tt0
콩심콩 팥심팥 🌱
Po_tta_tt0
전체 방문자
오늘
어제
  • 분류 전체보기 (266)
    • 🐛 회고 (14)
    • 💭 생각 (2)
    • 🤸‍♀️ 내 프로젝트 (16)
      • FISH-NEWS (8)
      • MBTI 과몰입 테스트 (2)
      • twitter clonecoding with TS (4)
      • pilzagenda (2)
    • 👨‍👩‍👧‍👦 팀 프로젝트 (2)
      • 피우다 프로젝트 (0)
      • SEMO(세상의 모든 모임) (1)
      • 마음을 전하는 텃밭 (1)
      • Stackticon (0)
    • 👨‍💻 CS지식 (11)
    • ✍ 공부 (94)
      • JavaScript (21)
      • TypeScript (39)
      • Html (0)
      • CSS (2)
      • React (18)
      • NextJS (7)
      • Vue (1)
      • Python (1)
      • Django (0)
      • 개발환경 & 그 외 (2)
    • 🏄‍♀️ 코딩테스트 (99)
      • 🐍 Python (99)
    • 🐙 Git & GitHub (3)
    • 📑 오류기록 (8)
    • 📚 우리를 위한 기록 (9)
    • 수업 (3)
    • 강의 등 (2)
    • 👩‍🎓 SSAFY (0)
    • 👋 우테코 (0)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • 파이썬 감시 피하기
  • bfs
  • 백준 숨바꼭질
  • BFS + DP
  • DP
  • 시뮬레이션
  • 백준
  • 문자열
  • 자바스크립트
  • 플로이드 워셜
  • 백준 파이썬
  • 파이썬
  • react-router-dom
  • 파이썬 다익스트라
  • js
  • Next.js
  • 이분탐색
  • dfs
  • 구현
  • React

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Po_tta_tt0

콩심콩 팥심팥 🌱

🏄‍♀️ 코딩테스트/🐍 Python

[ 백준 9252 해설 ] ( python ) LCS 2

2022. 9. 6. 15:46
반응형

 

📚 LCS 2

 

 

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

예제 입력 1 복사

ACAYKP
CAPCAK

예제 출력 1 복사

4
ACAK
 

 

 

✍ 접근

  • 가장 긴 공통 부분 수열
  • dp를 활용하여 점화식을 세워 풀 수 있다
  • 점화식에 값이 아닌 지나온 순서도 저장해준다

 

 

 

 

 

정답코드 

# ✨ 입력
import sys
input = sys.stdin.readline
A = ' ' + input().rstrip()
B = ' ' + input().rstrip()

len_A = len(A)
len_B = len(B)

board = [['']*len_B for _ in range(len_A)]

# ✨ 점화
for i in range(1,len_A):
    for j in range(1,len_B):
        if A[i] == B[j]:
            board[i][j] = board[i-1][j-1] + A[i]
        else:
            if len(board[i-1][j]) < len(board[i][j-1]):
                board[i][j] = board[i][j-1]
            else:
                board[i][j] = board[i-1][j]
                
res = board[-1][-1]

if len(res) != 0:
    print(len(res))
    print(res)
else:
    print(0)

해설

입력

  • 문제에서 나온 값을 입력받는다
  • 입력받을 때 점화식으로 i-1, j-1을 사용할 것이기 때문에 앞에 ' ' 를 넣어주었다.

점화

  • 세로에 A(ACAYKP) 가로에 B(CAPCAK)가 있는 board(dp)를 만들고
  • for문으로 A/C/A/Y/K/P를 하나하나 돌면서 각각 B 전체와 비교한다.
    • 만약 A/C/A/Y/K/P와 B의 한 부분이 맞으면 그 부분은 dp[i-1][j-1]에서 맞는 값(A[i])을 더해준다.
    • else
      dp[i][j]는 B의 바로 전 값에서 올 때의 길이 / A의 바로 전 값에서 올 때의 길이를 비교하여 길이가 더 긴 값을 가져와서 업데이트해준다

 

 

 

 

 

⭐ 배움

  • dp + 문자열 + 경로저장
반응형
저작자표시 (새창열림)

'🏄‍♀️ 코딩테스트 > 🐍 Python' 카테고리의 다른 글

[ 백준 20437 해설 ] ( python ) 문자열 게임 2  (0) 2022.09.07
[ 백준 2533 해설 ] ( python ) 트리와 쿼리  (0) 2022.09.06
[ 백준 9251 해설 ] ( python ) LCS  (0) 2022.09.06
[ 백준 7575 해설 ] ( python ) 바이러스  (0) 2022.09.05
[ 백준 11779 해설 ] ( python ) 최소비용 구하기 2  (0) 2022.09.05
    '🏄‍♀️ 코딩테스트/🐍 Python' 카테고리의 다른 글
    • [ 백준 20437 해설 ] ( python ) 문자열 게임 2
    • [ 백준 2533 해설 ] ( python ) 트리와 쿼리
    • [ 백준 9251 해설 ] ( python ) LCS
    • [ 백준 7575 해설 ] ( python ) 바이러스
    Po_tta_tt0
    Po_tta_tt0
    감자의 코딩하는 블로그 콩심은데 콩나고 팥심은데 팥난다

    티스토리툴바