[동적계획법] C 프로그래머스 연속 펄스 부분 수열의 합 풀이

문제

• 연속 펄스 부분 수열의 합

풀이 과정

• 문제부터 이해가 안감 뭔소리를 하는지 왜 값이 10인지 이해를 못해서 헤맸음
• 차근차근 이해해보자면,
  • 2, 3, -6, 1, 3, -1, 2, 4 일 때, 주어진 수열의 부분 수열에 1, -1, 1, -1 또는 -1, 1, -1, 1 인 펄스 수열을 더해서 가장 큰 값을 찾아라 는 문제
  • 펄스 수열이란? 1과 -1이 번갈아 나오는 수열이므로
    • 두가지의 경우의 수가 생기는데
    • 1 부터 -1, 1, -1, 1 ... 순서로 더한 수열
    • -1 부터 1, -1, 1, -1 ... 순서로 더한 수열
• 문제만 빠르게 이해한다면 어렵진 않은 문제
  • 주어진 수열에 두 가지 경우인 펄스 수열을 더한 다음 구해진 두 가지 수열을 탐색하며 max 값을 찾아 리턴하면 됨
    • 여기서 헷갈렸던 부분은 탐색 시 cur부분이 음수가 된다면 버리고 새로 시작해야 된다는 점
    • 음수가 누적되면 다음 값을 더해도 현재 값이 줄어드므로 약간 그리디? 처럼 버리고 새로 시작해야 됨

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int len;

long long max(int* arr) {
    long long max = arr[0];
    long long cur = arr[0];
    
    for (int i=1; i<len; i++) {
        if (cur > 0) {
            cur += arr[i];
        } else {
            cur = arr[i];
        }
        
        if (cur > max) {
            max = cur;
        }
    }
    
    return max;
}

long long solution(int sequence[], size_t sequence_len) {
    len = sequence_len;
    
    int *p1 = (int*)malloc(len * sizeof(int));
    int *p2 = (int*)malloc(len * sizeof(int));
    
    for (int i=0; i<len; i++) {
        if (i % 2 == 0) {
            p1[i] = sequence[i] * 1;
            p2[i] = sequence[i] * -1;
        } else {
            p1[i] = sequence[i] * -1;
            p2[i] = sequence[i] * 1;
        }
    }
    
    long long sum1 = max(p1);
    long long sum2 = max(p2);
    
    long long answer = (sum1 > sum2) ? sum1 : sum2;
    
    return answer;
}

• dp의 일종인 카데인 알고리즘이라고 한다.
  • 풀다가 문제를 도저히 이해 못해서 chatgpt와 같이 푼 문제

카데인 알고리즘이란?

• 1차원 배열에서 연속된 부분 수열의 합 중 가장 큰 값을 구하는 알고리즘
• 시간 복잡도 O(n)으로 매우 효율적

카데인 알고리즘은 언제 사용하나?

• 연속된 요소들의 합을 최적화해야 하는 문제
  • 최대 연속 부분 수열 합
  • 주식 매매 문제 (최소와 최대 차이 계산)
  • 신호 처리, 온도 변화 등 연속 데이터를 분석하는 문제

순서

• 매 단계에서 "현재 위치까지의 최대 합"을 계산
• "전체 최대값"을 지속적으로 갱신