# LCS (Longest Common Sequence) 알고리즘

<figure><img src="/files/yqfPP1mSZIikb69KPxXW" alt=""><figcaption></figcaption></figure>

[이미지 출처](https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4longest-common-subsequence-%EA%B8%B8%EC%9D%B4-%EA%B5%AC%ED%95%98%EA%B8%B0)

각 칸은 "이제까지 발견한 최대 순열 길이"를 의미한다

같은 문자를 발견하면, 이전까지의 문자열 비교 정보 (대각선 위)에 +1을 한다

문자가 같지 않으면, 비교 문자 2개 (org와 cmp에서의 두 글자) 둘 중 어느쪽을 문자열에 추가할지 선택한다

```cpp
int LCS(string& org, string& cmp)
{
	vvi dp = vvi(cmp.size()+1, vi(org.size()+1, 0));
	for (int i = 1; i <= cmp.size(); i++)
	{
		for (int j = 1; j <= org.size(); j++)
		{
			if (org[j - 1] == cmp[i - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[cmp.size()][org.size()];
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined/lcs-longest-common-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.