최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제란?

Q: 최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제란?

두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다 LCS는 동적 프로그래밍의 대표적 문제입니다. 예를 들어 'ABCDE'와 'ACE'의 LCS는 'ACE'(길이 3)입니다. diff 도구(파일 비교), 유전자 서열 분석, 버전 관리 시스템 등에서 활용되며, 시간 복잡도는 O(mn)입니다.

쉬움 freeCodeCamp

보기 및 정답

A 두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제이다

B 하나의 문자열에서 연속적으로 반복 등장하는 가장 긴 부분 문자열을 탐색하여 추출하는 문제이다

C 두 개의 문자열이 완전히 동일한지 문자 단위로 비교하여 판별하는 문제이다

D 문자열의 각 문자를 유니코드 값 기준으로 오름차순 정렬하는 문제이다

해설

LCS는 동적 프로그래밍의 대표적 문제입니다. 예를 들어 'ABCDE'와 'ACE'의 LCS는 'ACE'(길이 3)입니다. diff 도구(파일 비교), 유전자 서열 분석, 버전 관리 시스템 등에서 활용되며, 시간 복잡도는 O(mn)입니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

로그인

추가 정보 입력

회원가입

비밀번호 찾기

최장 공통 부분 수열(LCS, Longest Common Subsequence) 문제란?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

모두를 위한 진짜 쎈 바이브코딩