[프로그래머스 코딩테스트 연습] 연속 펄스 부분 수열의 합 (Python3) Lv3

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

문제 설명 및 알고리즘 분석

이 문제는 수열 sequence에 대해 연속 부분 수열에 1과 -1이 교차하는 펄스 수열을 곱한 뒤, 그 합 중에서 가장 큰 값을 구하는 문제이다.

펄스 수열은 [1, -1, 1, -1, ...] 또는 [-1, 1, -1, 1, ...]과 같이 1과 -1이 번갈아 가며 등장하는 수열을 의미한다.

예를 들어, 주어진 수열 sequence가 [2, 3, -6, 1, 3, -1, 2, 4]일 때, 펄스 수열과 각 원소를 곱하면 연속 펄스 부분 수열을 얻을 수 있다. 이 중에서 가장 큰 합을 구하는 것이 목표이다.

 

코드 설명

def solution(sequence):
    lenS = len(sequence)

    # 두 가지 펄스 수열을 곱한 결과를 각각 S1, S2에 저장
    S1 = [sequence[i]*(-1)**(i) for i in range(lenS)]  # 1, -1, 1, -1... 패턴
    S2 = [sequence[i]*(-1)**(i+1) for i in range(lenS)]  # -1, 1, -1, 1... 패턴

    # DP 테이블을 만들어 연속적인 최대값을 저장
    DP1 = [0 for _ in range(lenS)]  # S1의 최대 연속합 저장
    DP2 = [0 for _ in range(lenS)]  # S2의 최대 연속합 저장

    # DP1과 DP2의 초기값 설정
    DP1[0] = S1[0]
    DP2[0] = S2[0]

    # DP를 이용한 최대 연속 부분 수열 합 구하기
    for i in range(1, lenS):
        DP1[i] = max(DP1[i-1]+S1[i], S1[i])
        DP2[i] = max(DP2[i-1]+S2[i], S2[i])

    # 두 DP 테이블에서의 최대값 중 가장 큰 값 반환
    return max(max(DP1), max(DP2))

알고리즘 원리

1. 펄스 수열 곱하기:
   • 주어진 sequence에 두 종류의 펄스 수열을 각각 곱해서 두 가지 결과 S1과 S2를 구한다.
     • S1은 [1, -1, 1, -1, ...]와 곱해진 수열
     • S2는 [-1, 1, -1, 1, ...]와 곱해진 수열
   • 이렇게 두 종류로 나누는 이유는 어떤 패턴이 더 큰 합을 만들어낼지 모르기 때문이다.
2. DP 테이블 사용:
   • 동적 계획법(DP)을 활용하여 연속 부분 수열 중 최대 합을 구한다.
   • DP1[i]는 수열 S1에서 i번째까지의 연속된 부분 수열 중 최대 합을 저장하고, DP2[i]는 수열 S2에 대해 같은 작업을 수행한다.
   • DP1[i] = max(DP1[i-1] + S1[i], S1[i])는 이전까지의 최대 부분합에 현재 값을 더한 것과, 현재 값 자체를 비교하여 더 큰 값을 취한다. 이는 "이전까지의 합에 현재 원소를 더할지, 새로 시작할지"를 결정하는 과정이다.
3. 최종 결과:
   • DP1과 DP2에서 최대값을 각각 구하고, 그 중에서 더 큰 값을 최종적으로 반환한다.

적용된 알고리즘 및 개념

• 동적 계획법(Dynamic Programming, DP):
  • 연속된 부분 수열의 최대합을 구하는 데 사용되는 대표적인 방법이다. 여기서 DP를 사용하여 각 원소에서의 최대 연속 합을 계산하며, 이는 이전 상태의 최대값에 현재 원소를 추가할지 여부를 결정하는 방식으로 이루어진다.
• 펄스 수열의 변형:
  • 문제에서 주어진 펄스 수열은 두 가지로 나뉘어 사용된다. 이는 1과 -1이 교차하는 패턴으로, 두 가지 모두 고려하여 최종 결과를 비교한다.

성능 분석

• 시간 복잡도: O(n)
  • 수열 sequence의 길이를 n이라고 할 때, DP 테이블을 채우기 위한 반복문이 n번 돌기 때문에 시간 복잡도는 O(n)
• 공간 복잡도: O(n)
  • DP 테이블과 두 가지 펄스 수열에 대한 배열을 각각 저장하기 때문에 공간 복잡도도 O(n)

예시

수열 sequence = [2, 3, -6, 1, 3, -1, 2, 4]에 대해:

• S1은 [2, -3, -6, 1, 3, -1, 2, 4]
• S2는 [-2, 3, 6, -1, -3, 1, -2, 4]

이 두 수열에서 연속된 부분 수열을 구한 뒤 각각의 최대값을 구하면, 최대값은 10