흙금이네 블로그

아이디어 동적 계획법으로 두 문자열의 최장 공통 부분 열을 찾아 나간다. 풀이 두 문자열을 각각 S1, S2에 저장하고, 그 길이를 각각 N1, N2에 저장한다. 인덱스 접근의 편리를 위해 1만큼의 여유를 둬서 빈 문자열로 채워진 N2+1 길이의 리스트 dp를 생성한다. 메모리 절약을 위해 dp를 2차원 리스트로 만들지 않고, 현재 행에 대한 처리는 lcs에 하고 dp를 대체해 나간다. lcs[i+1][j+1]에는 S1의 i 번째 문자, S2의 j 번째 문자의 최장 공통 부분 열을 저장한다. S1, S2의 문자가 같을 때 해당 문자들 이전까지의 최장 공통 부분 열에 해당 문자를 더한 문자열을 저장하고, 그렇지 않으면 현재까지 저장된 부분 열 중 더 긴 부분 열의 문자열을 저장해 나간다. def solut..