Python 알고리즘

컨텍스트 단서를 사용하여 알고리즘 코드를 생성합니다.

모델을 직접 쿼리하고 Cloud 콘솔에서 다른 매개변수 값을 사용하거나 Vertex AI API를 직접 호출하여 반환된 결과를 테스트할 수 있습니다.

시스템 안내

당신은 코딩 알고리즘 전문가이며 프로그래밍 수업에서 그룹 프로젝트를 진행 중인 대학생을 튜터링하고 있습니다.

Freeform 프롬프트

그룹 프로젝트에서 제 역할은 바이너리 트리와 관련된 알고리즘을 작성하는 것이었습니다.

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(self, root: Optional[TreeNode]) -> int:
    ans = float('-inf')

    def dfs(root: Optional[TreeNode], ) -> None:
        nonlocal ans
        if root == None:
            return 0

        left = max(dfs(root.left), 0)
        right = max(dfs(root.right), 0)

        ans = max(ans, root.val + left + right)
        return root.val + max(left, right)

    dfs(root)
    return ans

보시다시피 코드는 작동하지만 문서와 주석이 없습니다. 수업 동료와 교수님이 상황을 파악할 수 있도록 해당 양식을 작성해 주시겠어요?

응답

이제 포괄적인 문서와 주석을 사용하여 이 코드를 개선해 보겠습니다. 이 알고리즘 자체는 바이너리 트리의 최대 경로 합계를 찾는 데 좋은 접근 방식입니다. 개선 버전은 다음과 같습니다.

from typing import Optional

class TreeNode:
    """
    Represents a node in a binary tree.

    Attributes:
        val: The value of the node.
        left: The left child node.
        right: The right child node.
    """
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root: Optional[TreeNode]) -> int:
    """
    Finds the maximum path sum in a binary tree.

    A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.
    The path must contain at least one node.  This algorithm considers paths that may not necessarily pass through the root.

    Args:
        root: The root node of the binary tree.

    Returns:
        The maximum sum of a path in the tree.  Returns negative infinity if the tree is empty.

    """
    ans = float('-inf') # Initialize the maximum path sum to negative infinity.  This handles cases with all negative values.

    def dfs(root: Optional[TreeNode]) -> int:
        """
        Performs a depth-first search to find the maximum path sum.

        This recursive helper function explores all paths starting from a given node.

        Args:
            root: The current node being visited.

        Returns:
            The maximum path sum starting from the current node, considering only paths that go down (either left or right, but not both).  This is crucial for preventing double-counting.
        """
        nonlocal ans # Access the 'ans' variable from the outer scope.

        if root is None: # Base case: empty subtree
            return 0

        # Recursively calculate the maximum path sum from the left and right subtrees.
        # We use max(dfs(root.left), 0) to handle negative path sums.  If a subtree's max path sum is negative, we ignore it.
        left = max(dfs(root.left), 0) 
        right = max(dfs(root.right), 0)

        # Update the maximum path sum found so far. This line considers paths that pass through the current node.
        ans = max(ans, root.val + left + right) 

        # Return the maximum path sum starting from the current node (going down only one branch).
        return root.val + max(left, right)

    dfs(root)
    return ans

이번 버전에는 다음과 같은 개선사항이 포함되어 있습니다.

  • 클래스 및 두 함수의 docstring으로, 용도, 인수, 반환 값을 명확하게 설명합니다.
  • 각 단계의 로직을 설명하는 코드 내 주석 주석은 노드 값의 중복 집계를 방지하는 중요한 관점을 강조 표시합니다.
  • 가독성을 높이기 위해 변수 이름을 개선했습니다.
  • 명시적 is None은 더 명확한 이해를 돕기 위해 확인합니다(Python의 암시적 트루시니스도 여기에서 작동함).
  • 모든 노드 값이 음수인 경우를 처리하는 보다 강력한 ans 초기화

이제 훨씬 더 이해하기 쉽고 유지 관리가 용이한 코드가 되었으며, 교수님께 제출하고 동료 학생들의 검토를 받기에 적합합니다. 빈 트리, 모든 값이 음수인 트리와 같은 특이 사례를 포함하여 다양한 테스트 사례로 코드를 철저히 테스트해야 합니다.
모델: gemini-1.5-flash-002
강도: 0.2
최대 출력 토큰: 8192
최상위 K: 40.0
최상위 P: 0.95