LeetCode 문제풀이 (Interleaving String)

오랜만에 DP 문제를 풀어보았습니다. DP 는 Dynamic Programming 의 줄임말인데요, 풀고자 하는 문제가 다음의 성질을 만족할 때 DP 를 적용할 수 있습니다. 1. 큰 단위 문제를 작은 단위 문제로 나눌 수 있다. 2. 큰 단위 문제의 답은 작은 단위 문제의 답으로 구성된다. 3. 작은 단위 문제의 답을 Memorization 하여 큰 단위 문제 해결에 이용할 수 있다. Greedy 알고리즘과의 차이는 위에서 설명한 2번과 관련되어 있습니다. Greedy 문제의 해답은 작은 단위 문제의 답으로 구성되지 않으며 단지 매 순간 최선의 선택을 해야되는 경우입니다. 알고리즘 문제를 보았을 때 뭔가 최적화를 해야되는 문제인데 Greedy 가 아님을 느낄 수 있을텐데요, 그런 경우 대부분 DP 문제라고 보시면 됩니다. DP 문제를 풀 때에는 큰 단위의 문제를 어떻게 나눌 수 있는지, 작은 단위의 해답을 어떻게 이용할 수 있는지가 키 포인트입니다. 특히 알고리즘 문제에서는 작은 단위 문제의 해답을 배열에 저장하고는 하는데요, 배열에서의 인덱스가 어떤 의미를 갖는지 설정하는 것이 문제의 전부라고 할 수 있습니다. (그 외 edge case 에 대해서도 고민이 필요하겠지만요,,) 해당 문제에서 배열 인덱스의 의미는 "string s2 의 i 번째 인덱스까지 고려했을 때 interleaving 의 가부" 입니다. - Name: Interleaving String - Difficulty: Medium - Algorithm: DP - Time Complexity: O(m * n) - Space Complexity: O(min(m, n)) - github: https://github.com/rere950303/study-algorithm/commit/baa3506703b26560d990482cc8b8554ed6e9f9d9