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

최장 공통 문자열의 개념에서 조금 확장시키면 어렵지 않게 구할 수 있다.

점화식을 사용하는 DP의 일종이다.

우선 최장 공통 문자열을 구하는 과정이다.

1. 두 문자열을 한글자씩 비교한다.
2. 두 문자가 다르면 LCS[i][j]에 0을 표시한다.
3. 두 문자가 같으면 LCS[i-1][j-1]에 1을 더한다.
4. 위의 과정을 반복한다.

// i, j는 1부터
if (str1[i-1] == str2[j-1])
    LCS[i][j] = LCS[i-1][j-1] + 1;
else
    LCS[i][j] = 0;

점화식을 코드로 작성하면 위와 같다.

이번에는 최장 공통 부분 수열을 구할 차례이다.

위의 과정에서 두 문자가 다를때의 식만 다르다.

if (str1[i-1] == str2[j-1])
    LCS[i][j] = LCS[i-1][j-1] + 1;
else
    LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j]);

두 문자가 다를때의 식이 저렇게 나오는 이유는 부분 수열은 연속된 값이 아니기 때문이다.

LCS[i][j-1], LCS[i-1][j]가 현재 문자를 비교하는 과정의 이전 과정인 것이다.

길이만 구하는 경우라면 LCS[str1.size()][str2.size()]로 구할 수 있고 실제 문자열이 필요한 것이라면 LCS배열의 가장 끝에서부터 0을 만날때까지 역순으로 추적한 뒤에 문자열을 뒤집으면 된다.

문자열 내의 특정 문자나 문장들 일괄 변경

#include <regex>

regex_replace("대상 문자열", regex("찾는 문자/문장"), "바꿀 문자/문장");
// regex_replace("aaa-bba-ccd-daf", regex("a"), "z");
// zzz-bbz-ccd-dzf

누적합

#include <numeric>

vector<int> v; // 1~10
accumulate(v.begin(), v.end(), "초기값", "임의 함수");
// accumulte(v.begin(), v.end(), 0);
// 55

https://jason9319.tistory.com/93

설명이 매우 잘되어있다

구현은 보통 DFS나 큐로 이뤄짐

- 최대 공약수는 유클리드 호제법, 최소 공배수는 두 수를 곱한 후 최대 공약수로 나누면 된다. 3개인 경우 순차적으로 시행