LCS2 [Swift][DP] 백준 5582번 (공통 부분 문자열) 요구능력 : DP 코드설명 : LCS를 풀고오면 문제가 상당히 쉽게느껴집니다. LCS 풀고오기 LCS문제와 다른점을 예시로 설명해보면 A B C 와 A D C가 있다. LCS라면 길이가 가장 긴건 A와 C라서 2가된다. 이 문제대로라면, 길이는 1이다. A 또는 C의 길이이다. 이 문제는 부분수열이기 때문에 같은 문자가 연속적으로 함께있어야지만, 조건이 성립한다. LCS는 기존에 연속적이지 않아도 중간중간 같은 문자가 나타나면 길이를 더해갔지만, 공통부분문자열의 경우에는 연속해서 같은 문자가 나오지 않으면 거기서 길이를 끊어야한다. 점화식을 설명하면, for문을 돌면서 x[i - 1]의 문자와 y[j - 1]의 문자를 비교하면서 만약 같다면, 부분수열이 하나 같다는 말이므로 dp[i][j]에 dp[i -.. 2022. 3. 14. [Swift][DP] 백준 9251번 (LCS) 요구능력 : DP 코드설명 : https://www.youtube.com/watch?v=EAXDUxVYquY 이곳에 설명을 아주 잘해주시는 교수님이 계십니다. 후기 : 여태 야매로 풀던 DP를 제대로 푸는방법을 배운것같은 강의였다. let x = readLine()!.map{String($0)} let y = readLine()!.map{String($0)} var dp = Array(repeating: Array(repeating: 0, count: y.count + 1), count: x.count + 1) for i in 1...x.count{ for j in 1...y.count{ if x[i - 1] == y[j - 1]{ dp[i][j] = dp[i - 1][j - 1] + 1 }else{ d.. 2022. 3. 10. 이전 1 다음