[백준]9251 - LCS

고려사항

1. Dynamic Programming 관련

• 처음에 dp 배열 dp=[[0]*(m+1) for i in range(n+1)]로 선언했는데, Dynamic Programming에서는 이전 상태 참조가 많아서 boundary condition 때문에 보통 한 줄씩 더 크게 만든다고 함.
• 첫 번째 코드 제출했는데 틀렸다고 함. 혹시 인덱스 참조가 잘못된건가 싶어서 봤더니 애초에 return값도 dp[-1][-1]로 주고 잘 나오니까 첫 번째 문자를 참조하는 상황인 i=0, j=0상황에서 i-1, j-1인덱스를 참조해도 괜찮은 것이 아닌가? 싶었음
• 그래서 나름 테스트케이스를 생각해서 넣어봤는데, a와 b로 빈 문자열을 넘기는 경우에 차이가 생김.
  • 첫 번째 코드의 경우 dp는 크기가 [0][0]인 빈 배열로 초기화됨. dp[-1][-1]참조 시 빈 배열을 참조하려 하여 IndexError 발생
  • 두 번째 코드의 경우 가로세로 한 줄씩 큰 배열이 생성되어 한 칸의 여유공간이 생김. dp=[[0]]이 되고 두 반복문이 range(1,1)이 되어 실행되지 않으며 진작에 초기화했던 값인 0을 return함
• 앞으로 dp 풀 때 배열 크기를 넉넉하게 잡아야겠다.
  
  

2. C++ 관련

• return값에 python처럼 그대로 dp[-1][-1] 넣고 백준에 제출하니까 런타임 에러(OutOfBounds) 발생함. 음수 인덱스 참조 기능이 없다고 한다. 그래서 dp[n][m]을 return하도록 수정함.

📍 왜 C++에서는 음수 인덱스 접근이 안되는가

• C++의 배열은 메모리 상에서 연속된 블록에 할당됨. 배열의 첫 번째 요소가 시작 주소가 되고 인덱스로 특정 요소까지 거리를 계산하여 접근하는 방식이므로 시작 주소 기준 양수 값만 가능함.
• 반면 Python에서는 음수 인덱스 접근이 가능한데, 이는 list에서 a[-1]을 a[a.length-1]로 처리하기 때문임. 목록의 마지막 항목 access에 많은 시간을 들이지 않아도 됨.

원래의 python 코드

1차 시도

def lcs(a,b):
  n=len(a)
  m=len(b)

  dp=[[0]*(m) for i in range(n)]

  for i in range(n):
    for j in range(m):
      if a[i]==b[j]:
        dp[i][j]=dp[i-1][j-1]+1

      else:
        dp[i][j]=max(dp[i][j-1], dp[i-1][j])

  return dp[-1][-1]

a=input()
b=input()
print(lcs(a,b))

최종

#G5_9251_LCS

def lcs(a,b):
  n=len(a)
  m=len(b)

  dp=[[0]*(m+1) for i in range(n+1)]

  for i in range(1,n+1):
    for j in range(1,m+1):
      if a[i-1]==b[j-1]:
        dp[i][j]=dp[i-1][j-1]+1

      else:
        dp[i][j]=max(dp[i][j-1], dp[i-1][j])

  return dp[-1][-1]

a=input()
b=input()
print(lcs(a,b))

---

C++ 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>  //max() 함수

using namespace std;

int lcs(const string& a, const string& b) {
    int n=a.length();
    int m=b.length();

    vector<vector<int>> dp(n+1, vector<int>(m+1,0));

    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            if (a[i-1]==b[j-1]) {
                dp[i][j]=dp[i-1][j-1]+1;
            } else {
                dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
            }
        }
    }

    return dp[n][m];
}

int main() {
    string a,b;
    cin >> a >>b;
    
    cout << lcs(a,b) << endl;

    return 0;
}