김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 15560 구간 합 최대? 1 파이썬(Python)

문제 링크

생각보다 쉬운 골드 문제.
처음엔 세그먼트 트리(Segment Tree)가 생각났지만, 입력 크기와 난이도를 따져 보았을 때, 세그먼트 트리가 필요없어 보여서 패스했다.
입력의 크기가 \(N, Q \le 10^{3}\)이기 때문에, 대략 \(O(N^{2}\log N^{2})\)으로 해결해도 풀릴 정도로 시간이 널널하다.
쿼리가 최대 \(N\)개임을 고려하면 쿼리 한번에 대략 \(O(N\log N^{2})\)정도의 시간이 있는 셈이다.
우선, 값을 바꾸는 두 번째 쿼리는 그냥 그대로 구현하면 된다(\(O(1)\)).
부분합을 구하는 첫 번째 쿼리가 문제인데, 우선 주어진 식이 조금 복잡하므로 그냥 단순한 부분합의 최대값을 구하는 문제라고 생각해보자(Maximum Subarray Problem).
이 경우 배열(리스트)을 순회하면서 부분합을 구하는 문제는 어렵지 않다.
현재 값에 원소들을 순서대로 더해가면서 최댓값을 갱신하다가, 중간에 값이 음수로 떨어지면 현재 값을 0으로 초기화하고 계속하면 된다.
나도 문제 풀고 나서 나중에 알았는데 이런 방식을 카데인 알고리즘(Kadane’s Algorithm)이라고 한다더라.
여담으로 카데인 알고리즘을 동적계획법(Dynamic Programming, DP)으로 많이 소개하던데, 관점에 따라서는 바로 직전 부분문제가 단 한 번 사용되고, 그 부분문제의 정답과 현재 답 중 큰 걸 고르는 걸 순회하며 반복한다는 관점에서 그리디 알고리즘(Greedy Algorithm)으로 생각해도 되지 않나 싶다.
아무튼, 카데인 알고리즘은 단순히 배열을 1회 순회할 뿐이기 때문에 \(O(N)\)에 해당한다.
다만, 이 문제는 단순히 부분합을 구하는 게 아니라 \(U \times (K_i + ... + K_j) + V \times (j - i)\)를 구한다는 차이점이 있다.
단순히 식만 한번 전개해 봐도 \(U \times (K_i + ... + K_{j+1}) + V \times (j + 1 - i) = U \times (K_i + ... + K_j) + V \times (j - i) + U \times K_{j+1} + V\)임을 쉽게 알 수 있기 때문에, 하나의 \(j+1\)번째 원소에 대해 부분합이 \(K_{j+1}\)를 더한다면, 이 문제는 \(U \times K_{j+1} + V\)를 더한다는 점만 유의하면 된다.
따라서 \(N\)개 쿼리 중 첫 번째 쿼리는 \(O(N)\), 두 번째 쿼리는 \(O(1)\)로 해결 가능하기 때문에 충분히 풀고도 남는다.

#!python

from sys import stdin

input = stdin.readline

n, q, u, v = map(int, input().split())
nums = list(map(int, input().split()))

for _ in range(q):
    c, a, b = map(int, input().split())

    # 두 번째 쿼리(1번)면 값을 바꾼다
    if c:
        nums[a - 1] = b

    # 첫 번째 쿼리(0번)면 배열을 순회해 최대 부분합을 구한다
    else:
        cur, ans = -v, -float("inf")
        for i in range(a, b + 1):
            cur += u * nums[i - 1] + v
            ans = max(ans, cur)
            if cur > -v:
                continue
            cur = -v
        print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑