알고리즘

LCS알고리즘 - 최장 공통 부분수열, 최장 공통 문자열(Longest Common Subsequence, Longest Common Substring)

1. 배경 코딩테스트 준비 중 여러 종류의 알고리즘을 만나다보니 머리로만 기억하는 것은 한계가 있다고 느끼고 지금부터라도 하나씩 차근차근 정리하려한다. 2. 개요 Longest Common Subsequence(최장 공통 부분수열) - 부분수열이라는 단어를 되뇌이면 이해하기 쉽다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 ABC가 LCS가 된다. - A와 BC는 연속되어있는 문자열은 아니지만 두 문자열에서 모두 공 통으로 존재하는 문자다. Longest Common Substring(최장 공통 문자열) - String.substring을 생각하면 쉽다. - 연속으로 이어진 공통 문자열이다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 BC가 LCS가 된다. 3. 예시 Longest Co..