알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13711 두개의 수열이 주어졌을 때, LCS를 구하는 문제입니다.  두개의 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구하는 문제입니다.N의 값이 10^5이기에 반복문을 통해서 전부  확인해본다면 시간 초과가 생깁니다. 문제를 봤을 때, 각 수열은 1부터 N까지 숫자가 1개씩만으로 주어진다는 것을 알 수 있습니다.그렇다면, 하나의 문자열을 기준으로 잡고, 다른 문자열의 숫자가 몇번 째로 나오는지를 저장만 해준다면,이는 가장 긴 증가하는 부분 수열의 문제로 바뀐다는 것을 알 수 있습니다. 예를 들어보겠습니다.문자열 1 : 1 2 4 7 8 9 6 3 5문자열 2 : 2 4 6 8 1 3 5 7 9-> 해당 수열의 LC..

문제 링크입니다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS를 사용한 문제입니다. 해당 문제에서 변형된 문제이니, 문제를 풀고 와주시면 좋을거 같습니다. -> https://junseok.tistory.com/170 LCS 문제에서 추가된 것은 수열까지 출력하는 것입니다. 쉽게 생각할 수 있는 방법은 수열을 저장하면서 푸는 방법인데 이는 시간초과로 실패했습니다. 따라서 역추적을 하는 ..

문제 링크입니다. https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 문자열이 주어졌을때, 공통되는 가장 긴 수열을 찾는 문제입니다. 이 문제의 핵심은 연속된 문자열이 아닌 부분 수열이라는 점입니다. 따라서 X, Y 문자열을 하나하나 비교해나가면서 최댓값을 확인하면 됩니다. 그림으로 한번 확인해보겠습니다. X, Y 문자열이 주어졌을때, 두 문자열 중 하나를 고정시킵니다. X 문자열을 고정했다고 했을때..