LCS

[Gold V] 비밀번호 만들기 - 17218 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 다이나믹 프로그래밍, 문자열 문제 설명 최근 들어 개인정보 유출에 대한 뉴스를 많이 본 수형이는 한 사이트의 비밀번호가 유출 되더라도 다른 사이트에서 똑같은 비밀번호로 접속할 수 없도록 사이트마다 비밀번호를 다르게 설정하기로 다짐했다. 많이 고민한 결과 수형이는 눈을 감고 키보드를 막 쳐서 나온 두 문자열에서 공통으로 존재하는 가장 긴 부분 문자열을 비밀번호로 하기로 하였다. 수형이가 눈을 감고 만든 두 문자열이 주어졌을 때 비밀번호를 만드는 프로그램을 만들어보자. 입력 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는..

LCS LCS란 보통 최장 공통 부분수열(Longest Common Subsequence)을 의미하지만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 여기에서 부분수열(Subsequence)과 문자열(Substring)의 차이는 문자열이 연속적인지 아닌지에 따라 달라지는데요, 연속적이라면 문자열(Substring)이고, 비연속적이면 부분수열(Subsequence)입니다. 다음과 같은 예시가 있다고 가정해봅시다. [AUTABBEHNSAAB, BCUAMEFKAJNAAB] 위 예시에서 AAB는 연속적이기 때문에 문자열이라고 할 수 있고, UAENAAB는 비연속적이기 때문에 부분 수열이라고 할 수 있습니다. 위에서 말한 두 가지의 LCS를 구현하는 방법에 대해 알아보겠습니..