Python 알고리즘 문제 풀이(feat. Code Kata)

윤현묵·2021년 9월 21일
0
post-thumbnail

문제

숫자로 이루어진 리스트 nums를 인자로 주면, 그 안에서 어떤 연속적인 요소를 더했을 때 가장 큰 값이 나오나요? 가장 큰 값을 찾아 return해주세요.

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

  • 설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문

풀이 접근 방식

앞에서부터 연속적으로 더한 값을 모두 저장하여 가장 큰 수를 반환
(사실 위의 방법은 이중반복문을 사용하기 때문에 비효율적이나, 다른 방법이 생각이 나지 않았다..ㅠㅠ)

내 풀이 코드

def maxSubArray(nums):
    output = []                                      (1)
    for i in range(len(nums)):                 
      sum = 0                                        (2)
      for j in range(i,len(nums)):
        sum += nums[j]                               (3)
        output.append(sum)                           (4)
    return max(output)                               (5)

풀이 설명

(1) 모든 연속된 숫자의 합을 저장해줄 리스트 생성
(2) 첫번째 인덱스부터 연속된 숫자를 더해주며, 다음 인덱스의 연속된 숫자를 더하기 전 0으로 초기화
(3) 연속된 숫자의 합을 차례로 누적하며 구해줌
(4) (3)에서 구한 값을 output 리스트에 하나씩 추가
(5) 모든 경우의 수에서 가장 큰 값을 반환
→ 위의 방법은 비효율적인 방법이다. 추후 다른 풀이를 구하면 업데이트 해야겠다..

profile
진정성 있는 개발자를 꿈꾼다

0개의 댓글