개발 블로그 개발 블로그

문자열은 웹개발에서 가장 중요한 요소 중 하나이고 코딩테스트에서 단골로 출제되는 알고리즘이 Dynamic Programming(동적계획법)이기 때문에 가끔씩 DP를 사용하는 문자열 문제가 출제될 때가 있습니다. 어떤 문제든지 패턴을 파악하고 있으면 조금 더 쉽게 풀 수 있습니다. 오늘은 DP를 사용하면 문자열 문제 몇 개를 살펴보도록 하겠습니다. 가장 많이 출제되는 유형의 문제는 두 문자열에서 공통되는 문자의 개수를 찾아내거나 공통되는 문자열의 길이를 구하는 종류의 문제입니다. 예를 들어 "XMJYAUZ”, “MZJAWXU” 두 문자열에서 공통된 글자의 수를 찾아내려고 할 때, 위와 같은 테이블을 만들 수 있을 것입니다. 표에서 인덱스는 각각 하나의 문자를 나타내고 만약 해당하는 인덱스의 문자열이 같은 ..