해킹왕 양선규

a = [[]] # dp테이블과 인덱스를 동기화하기 위해 빈 리스트를 추가한다. b = [[]] for i in list(input()): a.append(i) for i in list(input()): b.append(i) # 0행과 0열 값을 모두 0으로 맞춰준다. # 첫번째 비교부터 공식을 적용하려면 이전 값이 존재해야 하기 때문에 맞춰주는 것. dp = [[0 for _ in range(len(a))] for _ in range(len(b))] for x in range(1, len(b)): for y in range(1, len(a)): if b[x] == a[y] : # 문자열이 일치할 경우 dp[x][y] = dp[x-1][y-1] + 1 # 좌측위 방향 값에서 +1 더한 값 else: # ..

DP(Dynamic Programming, 동적 계획법) - 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해, 다시 큰 문제를 해결할 때 사용한다. - DP는 특정 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰인다. - “큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고, 재활용” - DP라는 이름은 그냥 멋있어 보여서 지은 이름이다. DP를 쓰는 이유 - 일반적인 재귀방식도 DP와 유사하지만, 일반적인 재귀를 단순히 사용 시 “동일한 작은 문제가 반복”되어, 비효율적인 계산이 될 수 있다. ex) 피보나치 수열. 한번 한 계산을 또 하고 또 하고 반복한다. --->>> DP 방식으로 작은 문제의 결과를 저장해두고 “재사용”하면 매우 효율적으로 해결할 수 있다. --->>..