🧗‍♂️초보자용 가이드 'Max Dot Product of Two Subsequences' – LeetCode 1458 (C++, Python, JavaScript)

Source: Dev.to

문제 요약

주어진 것:

• 정수 배열 두 개, nums1와 nums2.

목표:

• 두 배열에서 길이가 같은 비어 있지 않은 부분 수열들 사이의 최대 내적을 찾는다.

직관

이 문제의 핵심은 동적 프로그래밍에 있습니다. 우리는 부분수열을 찾고 있기 때문에, 각 단계에서 현재 숫자들의 곱을 포함시킬지, 나중에 더 좋은 쌍을 찾기 위해 건너뛸지를 결정합니다.

우리는 dp[i][j]가 첫 번째 배열의 인덱스 i까지와 두 번째 배열의 인덱스 j까지의 요소들을 사용하여 얻을 수 있는 최대 점곱을 나타내는 2차원 격자를 구축합니다.

각 인덱스 쌍 (i, j)에 대해 세 가지 선택이 있습니다:

1. 새로운 곱을 시작하거나 이전 곱을 확장 – A[i] * B[j]를 계산합니다. 이전 최적 결과 dp[i‑1][j‑1]가 양수라면, 이를 현재 곱에 더합니다.
2. 첫 번째 배열의 현재 요소를 건너뛰기 – dp[i‑1][j]를 그대로 가져옵니다.
3. 두 번째 배열의 현재 요소를 건너뛰기 – dp[i][j‑1]를 그대로 가져옵니다.

이러한 옵션들을 고려함으로써 격자는 점차 최대 가능한 값들로 채워지고, 최종 답은 오른쪽 아래 셀에 위치하게 됩니다.

코드 블록

C++

class Solution {
public:
    int maxDotProduct(vector& A, vector& B) {
        int n = A.size(), m = B.size();
        vector> dp(n, vector(m));

        for (int i = 0; i  0 && j > 0) {
                    dp[i][j] += max(dp[i - 1][j - 1], 0);
                }

                // Choice 2: Skip current element from A
                if (i > 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                }

                // Choice 3: Skip current element from B
                if (j > 0) {
                    dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

파이썬

class Solution:
    def maxDotProduct(self, A: List[int], B: List[int]) -> int:
        n, m = len(A), len(B)
        dp = [[0] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                current_product = A[i] * B[j]

                if i > 0 and j > 0:
                    dp[i][j] = current_product + max(dp[i - 1][j - 1], 0)
                else:
                    dp[i][j] = current_product

                if i > 0:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j])
                if j > 0:
                    dp[i][j] = max(dp[i][j], dp[i][j - 1])

        return dp[n - 1][m - 1]

자바스크립트

/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
var maxDotProduct = function (A, B) {
    const n = A.length;
    const m = B.length;
    const dp = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i  0 && j > 0) {
                dp[i][j] = currentProduct + Math.max(dp[i - 1][j - 1], 0);
            } else {
                dp[i][j] = currentProduct;
            }

            if (i > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
            if (j > 0) {
                dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n - 1][m - 1];
};

핵심 요점

• Subsequence vs. Subarray: 부분수열의 원소는 연속될 필요가 없으며, 그래서 dp[i‑1][j]와 dp[i][j‑1]를 사용해 요소를 “건너뛸” 수 있습니다.
• Dynamic Programming Power: 중간 결과를 테이블에 저장함으로써 지수 시간 문제를 관리 가능한 이차 시간 문제로 변환합니다.
• Handling Negative Numbers: 식 max(dp[i‑1][j‑1], 0)은 이전 부분수열이 현재 곱을 향상시키는지, 아니면 새로 시작해야 하는지를 결정합니다.

최종 생각

이 문제는 동적 프로그래밍이 큰 탐색 공간을 효율적으로 탐색할 수 있음을 보여줍니다. 유사한 기법은 추천 시스템(사용자 관심사를 제품 태그와 매칭)과 생물정보학(DNA 서열 비교)에서 사용됩니다. 이 패턴을 마스터하면 대규모 데이터 매칭을 포함하는 기술 면접에서 강력한 이점을 얻을 수 있습니다.