99클럽 코테 스터디 17일차 TIL - 중복, 연속적으로 계산할 땐 누적합

문제 - 우박수열 정적분 문제링크

프로그래머스

문제 설명

우박수열 만드는법

 

양의 정수 k가 주어지고, k에서 시작하는 우박수열을 만듭니다. 이후, 우박수열을 y값으로 하고 x값은 0부터 각 수열 생성시마다 x = 1, x = 2 이런식으로 1씩 증가하도록 해서 (x, y)가 정해지며, 그래프를 그릴 수 있습니다.

마지막으로 넓이를 구해야 하는 x의 범위들이 주어지는데, 이때 해당 x 범위와 x축, y축, 그래프가 형성하는 영역의 넓이를 구하면 됩니다.

제한 사항

k: 1만 이하

ranges 길이: 1만 이하

 

풀이 과정

이 문제에는 여러 서브태스크들이 존재합니다.

 

1. 우박수열을 만드는 과정

2. range의 범위를 알맞게 조정하는 과정

3. 해당 범위의 정적분 값을 구하는 과정

 

1, 2번은 쉽습니다. 하지만 3번에서 범위 넓이를 한칸씩 계산한다면 시간초과가 날 것입니다.

k의 크기에 따라 얼마나 우박수열이 길어질지 정확히 알지는 못하지만, 예시를 보았을 때 우박수열의 길이는 k라고 볼 수 있습니다.

 

그럼 범위의 넓이를 구할 때, 높이가 1인 사다리꼴 조각들의 넓이를 전부 구해야 하므로 O(k)이고, 총 시간복잡도는 O(len(ranges) * k)가 되고 최대 1억번의 연산이 필요합니다.

1억번의 연산은 대부분의 문제에서 시간초과가 나는 정도입니다.

 

최적화를 해야하는데, ranges 순회는 무조건 해야합니다. 따라서 넓이 구하는 과정을 최적화하자면, 우리는 이미 계산했던 넓이를 중복해서 계산하고 있습니다. 예를 들어, [0,5]범위와 [3,6] 범위에서 중복계산되는 부분은 [3,5] 부분 입니다.

이 비효율성을 해결하는 알고리즘은 누적합 알고리즘입니다.

 

누적합은 구간 내 원소의 합을 반복적으로 구해야 할 때 사용하면 좋은 알고리즘입니다. 일단 O(N)으로 누적합을 구해 놓으면, 이후 구간합은 O(1)로 구할 수 있기 때문입니다.

 

sum[i] = sum[i - 1] + items[i]

이런식으로 이전 누적합과 현재 아이템을 더해서 현재 누적합에 할당하는 방식으로 구현할 수 있습니다.

 

이 문제에서 items는 [[0,1], [1,2], [2,3], ..., [n-1, n]]과 같은 길이가 1인 영역의 넓이입니다.

이 items에 대해 누적합을 구한 후, 이후에 만약 [3,6] 구간의 넓이가 필요할 때, 6까지의 누적합에서 3까지의 누적합을 빼면 남은 영역인 [3, 6]의 넓이를 구할 수 있게 됩니다.

"""
    k: 1만
    range길이: 1만

    누적합 문제
    1. 우박수열 구하고
    2. 한번 순회해서 누적합 구하고
    3. range 범위 계산한 후 누적합 구한거 이용해서 넓이 구하기
"""
def getRainStones(arr, k):
    while k != 1:
        if k % 2 == 0:
            k //= 2
        else:
            k *= 3
            k += 1
        arr.append(k)

def getArea(arr, i):
    return (arr[i] + arr[i + 1]) / 2

def parseRange(arr, st, en):
    if en <= 0:
        en = len(arr) - 1 + en
    return (st, en)

def solution(k, ranges):
    answer = []

    rainStones = [k]
    # 1. 우박수열 구하기
    getRainStones(rainStones, k)
    
    # 2. 넓이 누적합 구하기
    areas = [0] # areas[1] : [0~1] 구간 넓이
    for i in range(len(rainStones) - 1):
        areas.append(areas[i] + getArea(rainStones, i))

    # 3. range 처리
    for rng in ranges:
        st, en = parseRange(rainStones, rng[0], rng[1]) # [st~en] 구간

        if st > en:
            answer.append(-1)     
        else:
            answer.append(areas[en] - areas[st])

    return answer

 

 

총평

어제 백준에서 누적합 문제 풀이를 시도했는데 예시 테스트만 통과할 뿐 결국 정답을 맞추지 못했습니다. 그 후 오늘 이 문제를 보니 수월하게 알고리즘 분류를 파악하고 풀 수 있었습니다.

혹시 심심하시다면 아래 문제를 풀고 댓글로 힌트 남겨주시면 감사하겠습니다.

24538번: 작업 일지

 

틀린코드

N, K = map(int, input().split())
starts = [0 for _ in range(K + 1)]
ends = [0 for _ in range(K + 1)] # (며칠연속, 카운트)
cnts = [0 for _ in range(K + 1)]

for _ in range(N):
    st, en = map(int, input().split())
    starts[st] += 1
    ends[en] += en - st + 1
    cnts[en] += 1

for i in range(K - 1, 0, -1):
    # i + 1의 starts 확인 -> cnts에서 제외해야 할 수 제거
    ends[i] += ends[i + 1] - cnts[i + 1]
    cnts[i] += cnts[i + 1] - starts[i + 1]

for i in range(1, len(ends)):
    print(ends[i], end= ' ')