<보기>는 두 문자열 X와 Y가 주어졌을 때 최장 공통 부분… | [9급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

<보기>는 두 문자열 $X$와 $Y$가 주어졌을 때 최장 공통 부분 수열(LCS, longest common subsequence)의 길이를 구하는 알고리즘의 점화식이다. $c[i,j]$는 문자열 $X_i$와 $Y_j$의 LCS 길이라고 정의할 때, (가), (나)에 들어갈 내용으로 가장 옳은 것은? (단, LCS는 두 문자열에 공통으로 존재하는 가장 긴 부분 수열을 뜻한다. 이때, 문자의 연속성은 보장하지 않으며 순서는 유지하여야 한다.)
$c[i,j]=\left\{\begin{array}{ll}0 & \text{if } i=0 \text{ or } j=0\\ \text{(가)} & \text{if } i,j>0 \text{ and } x[i]=y[j]\\ \text{(나)} & \text{if } i,j>0 \text{ and } x[i]\neq y[j]\end{array}\right\}$

(가) $c[i-1,j]+1$ (나) $\max\{c[i-1,j],c[i,j-1]\}$

(가) $c[i,j-1]+1$ (나) $\max\{c[i-1,j],c[i,j-1]\}+1$

(가) $c[i-1,j-1]+1$ (나) $\max\{c[i-1,j],c[i,j-1]\}$

(가) $c[i-1,j-1]+1$ (나) $\max\{c[i-1,j],c[i,j-1]\}+1$