[백준, 9251번] LCS

아래 코드는 2차원 배열을 활용해 푸는 방법

• 아직도 dp를 활용하여 누적합을 만들어 내는 로직을 구현하는데에 많은 어려움이 있어서
   여러 방법을 찾아보려고 노력중.
• 우선 아래 코드에서 else 구문에 dp[i][j-1] 을 추가하여 max로 값을 찾는 이유에 대한 의문을 제기할 수 있다.
• 결과적으로는 저 코드를 추가함으로서 이전에 나온 값이 이만큼 나온적이 있다라는 의미가 되는데
• ACAYKP
• CAPCAK 
• 예시를 들어보자면 i가 2의 경우 a = 'C'
  • j = 1일 땐 b = 'C' 가 될 때는 같기에 이전까지의 누적 합에 해당하는 dp[i-1][j-1] 에서 +1 해주고
  • j = 2일 땐 b = 'A' 가 될 때는 다르니 현재의 dp 값에는 i-1 층에 해당하는 현재 j 값과, j 가 1이었을 때의 값 중
     큰 값을 비교 후 값을 담아주는데
  • 이렇게 하는 이유는 누적을 하면서 이전까지 최소한 누적된 값만큼 같은 값이 존재했다  라는
     의미로 해석할 수 있게 되어서 
  • j = 4 일 때  b = 'C' 로 되는 경우에는 i 가 1의 경우일 때
     a[i] 와 b[2] 가 같은 이후로 최소한 누적된 값이 1번은 있다로 된 다음 다음 배열에 쭉 1로 채워진 것을 활용해
    • i = 2, j = 4 인 b가 'C'의 경우에 해당 값에서 +1을 해주게 되면 최소한 A와 C는 한번씩 나와서 
       현재 dp의 값에 2가 담겨지게 된다.
    • 마찬가지로 이후의 배열에도 최댓값인 2로 쭉 채워지게 된다.

# 2차원 캐시를 통해 푸는 방법
a,b = input(), input()
ln_a, ln_b = len(a), len(b)
dp = [[0]*(ln_b+1) for _ in range(ln_a+1)]
for i in range(1, ln_a+1):
    for j in range(1, ln_b+1):
        if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]+1
        else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
print(max(dp[-1]))

 

아래 코드는 위에서 사용했던 방식을 1차원 배열만을 활용해 재활용하며 누적해가는 방식의 코드

• 이전 코드에서 활용했던 최소한 누적된 값만큼 같은 값이 존재했다 를 여기에선 cnt로 변경하여
   값을 비교하기 전 현재 dp의 값이 cnt 보다 크다면 cnt 값을 변경 해주고
• 다음의 값이 dp보다 작거나 같고 같은 문자의 경우엔
   이전에 같은 문자의 개수인 cnt에 +1을 해주게 되는 코드
• 여기서 if와 elif 로 if, if 를 사용하지 않은 이유는 
  •  if와 elif를 사용하여 같은 문자가 존재할 경우 계속 앞에 있던 같은 값을 비교하지 않고 
     그 다음 문자를 비교하기 위한 코드로 적용한 것을 의미할 수 있다.

a,b = input(), input()
ln_a, ln_b = len(a), len(b)
dp = [0]*ln_b
for i in range(ln_a):
    cnt = 0
    for j in range(ln_b):
        if dp[j] > cnt: 
            cnt = dp[j]
        elif a[i] == b[j]: 
            dp[j] = cnt + 1
print(max(dp))