탁월함은 어떻게 나오는가?

오늘은 LCS 알고리즘을 공부해보겠다.LCS 문제는 두 문자열의 부분 수열을 비교하는 문제로, DP를 활용하여 해결하는 문제이다.  DP를 사용하는 이유LCS 문제에서 DP가 적절한 이유는 중복되는 부분 문제와 최적 부분 구조를 가지기 때문이다.1. 중복되는 문제- 두 문자열을 비교하다 보면, 같은 부분 문자열을 여러 번 계산하게 된다. 예를 들어, DP배열을 사용하지 않는다면 dp[i][j]를 계산할 때 dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1] 같은 부분을 반복적으로 계산해야 한다.- DP는 이러한 중복 계산을 한 번만 계산하고 저장하여, 다시 계산하지 않도록 하는게 큰 아이디어이다. 이로 인해서 계산량을 크게 줄일 수 있다.2. 최적 부분 구조- 부분 문제들의 ..