Notice
Recent Posts
목록최장공통부분수열 (1)
천천히 빛나는
알고리즘 : LCS (최장 공통 부분수열)
LCS (Longest Common Subsequence)문자열 x, y가 있을 때 x와 y에서 공통으로 나타나는 부분 문자 수열 중 최대 길이를 갖는 문자 수열예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다 재귀적으로 정의c(i, j) : 수열 xi와 yj의 LCS의 길이 기저조건 (종료조건)i =0 또는 j = 0이면 c(i, j) = 0이 된다재귀조건xi = yj이면 c(i, j) = c(i-1, j-1) + 1xi != yj이면 c(i,j) = max(c(i, j-1), c(i-1, j))int lcs (String x, String y){ int m = x.length(); int n = y.length(); if(m == 0 || n == 0){ re..
STUDY/ALGORITHM
2024. 4. 25. 03:08