LeetCode 코딩테스트 Maximum Subarray – Array (5)

by

LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 글에서는 Array문제인 Maximum Subarray 문제를 python으로 풀어보았다.

Leetcode 문제설명

이 문제는 정수 배열이 주어졌을 때, 해당 배열에서 부분배열(subarray)의 합 중에서 가장 큰 값을 찾고, 그 최대 합을 반환하는 것이다. 부분배열은 배열 내에서 연속된 원소들로 이루어진 것을 의미한다.

해당 문제는 https://leetcode.com/problems/maximum-subarray/ 에서 확인 할 수 있습니다.

예를 들어, 주어진 배열이 [-2, 1, -3, 4, -1, 2, 1, -5, 4]일 때, 이 배열의 부분배열 중 합이 가장 큰 경우는 [4, -1, 2, 1]이며, 해당 부분배열의 합은 6이다. 따라서 이 문제에서 함수는 6을 반환해야 한다.

솔루션

다음 코드는 두 번의 반복문을 사용하여 가능한 모든 부분배열 합을 계산하고, 그 중에서 최대 값을 찾는다. 이는 이중 반복문을 사용한 비효율적인 방법으로, 시간 복잡도는 O(n^2)이다. 이러한 방법을 전체탐색(Brute Force)라고 한다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 입력 배열이 비어있으면 0을 반환
        if not nums:
            return 0

        # 배열의 길이 저장
        n = len(nums)
        
        # 최대 합을 음의 무한대로 초기화
        max_sum = float('-inf')

        # 배열의 각 인덱스에 대해 반복
        for i in range(n):
            # 현재 부분배열의 합을 저장하는 변수 초기화
            current_sum = 0
            
            # 현재 인덱스 i에서 시작하여 배열의 끝까지 반복
            for j in range(i, n):
                # 현재 부분배열 합에 현재 인덱스 j의 값을 더함
                current_sum += nums[j]
                
                # 최대 합을 현재 부분배열 합과 기존 최대 합 중 더 큰 값으로 갱신
                max_sum = max(max_sum, current_sum)

        # 최종적으로 계산된 최대 부분배열 합 반환
        return max_sum
leetcode

이 방법은 모든 가능한 부분배열의 합을 계산하므로 효율성 면에서 좋지 않다. 비교적 큰 배열에 대해 더 많은 시간이 소요될 수 있다. Kadane’s의 알고리즘과 비교했을 때 O(n^2) 대 O(n)의 차이가 두드러지게 나타난다.

Kadane’s 알고리즘은 최대 부분배열 합 문제를 해결하는 효율적인 알고리즘으로, 선형 시간(O(n))에 동작한다. 이 알고리즘의 핵심 아이디어는 배열을 순회하면서 현재 위치에서의 최대 부분배열 합과 전체 최대 부분배열 합을 계속 갱신하는 것이다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
    
        # 입력 배열이 비어있으면 0을 반환
        if not nums:
            return 0

        # 최대 부분배열 합과 현재 부분배열 합을 첫 번째 원소로 초기화
        max_sum = current_sum = nums[0]

        # 배열의 두 번째 원소부터 시작하여 끝까지 반복
        for num in nums[1:]:
            # 현재 부분배열 합 갱신: 현재 원소(num)와 이전까지의 부분배열 합(current_sum + num) 중에서 큰 값을 선택
            current_sum = max(num, current_sum + num)
            
            # 전체 최대 부분배열 합 갱신: 현재 부분배열 합과 기존 전체 최대 부분배열 합 중에서 큰 값을 선택
            max_sum = max(max_sum, current_sum)

        # 최종적으로 계산된 최대 부분배열 합 반환
        return max_sum

다음 문제는 Maximum Product Subarray 입니다.

LeetCode 코딩테스트 Maximum Product Subarray – Array (6)

Leave a Comment