백준 9251 : LCS - javascript(문자열, dp)

문제 출처 

https://www.acmicpc.net/problem/9251

 

정답 풀이 

- 두 문자열의 공통 부분 수열 중 가장 긴 부분 수열을 찾는 것. 

- 부분 수열은 원래 문자열에서 문자를 순서를 유지한 채 일부를 선택하여 만든 문자열이다. 

 

DP 접근 방법 

- 두 문자열의 각 문자 쌍을 비교하면서 최장 공통 부분 수열을 점진적 계산 

- 2차원 배열 사용 

- 각 셀 DP[i][j]는 첫번째 문자열의 첫 i개 문자와 두번째 문자열의 첫 j개 문자를 비교했을 때의 LCS 길이를 나타낸다. 

 

테이블 초기화 

- DP[i][0]와 DP[0][j]는 0을 초기화한다. 왜냐하면 공백과 어떤 문자열을 비교하면 공통 부분 수열의 길이는 항상 0이다. 

 

점화식 

- str[i-1] 과 str[j-1]이 같으면 dp[i][j] = dp[i-1][j-1] + 1 이다. 

- 다르면, dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) 이다. 

 

 

 

이를 더 자세히 톺아보자. 

## 왜 그래프의 각 0번째 줄은 0이 되어야 하는가? 

이유) 공백과 문자를 비교하는 칸이기 때문이다. 

 

 

 

str1의 i가 0일 때  str2의 j++일 때 상황을 봐보자.

- str1가 0일 때는 A이고, str2가 0일 때는 C이다.  LCS => 0 

- str1가 0일 때는 A이고, str2가 1일 때는 A이다.  LCS => 1이다. 

  => 이때의 숫자는 그래프에서 어떻게 구할 수 있을까? 

      - str1[i-1] 과 str2[j-1]이였을 때, 즉, graph[i-1][j-1] 일 때 상황에서 +1 을 한 것이라고 말할 수 있다. 

      - 즉, 이전 상태에서 얻을 수 있는 LCS(최장 공통 부분 수열)에 이 새로운 일치하는 문자 하나를 추가하는 것이다. 

   

 

str1의 i가 0일 때  str2의 j++일 때 상황을 계속 봐보자.

- 'A'와 'P'를 비교했을 때 각 문자가 다르다. 

- 그럼 이전의 LCS를 그대로 갖고 와야 하는데, 이전의 LCS는 후보가 두개다 

  - 'A' 와'CA'를 비교했을 때 => 1 : str2[j-1]를 포함하지 않는 경우임

  - ''와 'CAP'를 비교했을 때  => 0 : str1[i-1]를 포함하지 않는 경우 

  => 이 두개의 값에서 큰 값을 graph에 넣어준다. 

  - 즉, 이전 단계에서 최장 공통 부분 수열을 구성할 수 있는 두 가지 경우 중 (각각의 문자를 포함하냐/안하냐) 더 긴 것을 선택한다. 

 

 

정답 코드 

const [str1, str2] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')

function solution(str1, str2){
    let graph = Array.from({length: str1.length+1}).map(() => new Array(str2.length + 1).fill(0))
    
    for(let i=1; i<str1.length+1; i++){
        for(let j=1; j<str2.length+1; j++){
            if(str1[i-1] === str2[j-1]){
                graph[i][j] = graph[i-1][j-1] + 1
            }else{
                graph[i][j] = Math.max(graph[i-1][j], graph[i][j-1])
            }
        }
    }
    return graph[str1.length][str2.length]
}

console.log(solution(str1, str2))