알면 도움되는 코딩 테스트 유형: 3) #Prefix_Sum

• 오늘은 코딩 테스트에서 알고 가면 좋은 유형인 'Prefix Sum(누적 합)'에 대해 이야기해보려고 합니다.

 

누적 합(Prefix Sum)이란?

 

• 누적 합은 배열의 원소들을 순차적으로 더한 값을 저장하는 배열로, 각 원소는 이전 원소까지의 모든 원소의 합을 나타냅니다. 이를 통해 구간합, 구간 평균 등 다양한 연산을 빠르게 수행할 수 있습니다.

 

누적 합 문제 접근 방법

 

• 코딩 테스트에서는 누적 합 개념이 종종 활용됩니다. 예를 들어,

 

1. 주어진 리스트에서 연속된 부분 리스트 중 최대 / 최소 / 평균 값을 찾기
2. 주어진 리스트에서 특정 값보다 크거나 작은 부분 리스트 개수 세기 등

• 위와 같은 문제들은 일반적으로 반복문으로 해결할 경우 시간 복잡도가 O(N^2)이 됩니다. 하지만, 누적 합을 활용하면 시간 복잡도를 O(N)으로 줄일 수 있습니다. 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용합니다.

 

1. 주어진 문제가 구간합 관련 문제인지 확인합니다.
2. 필요한 경우 입력값에 대한 전처리 과정으로 누적 합 배열(prefix sum array)을 생성합니다.
3. 주어진 조건에 맞게 구간합을 계산하여 정답을 도출합니다.

 

2003번: 수들의 합 2

  문제  
 

• N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 주어진 수열에서 연속된 부분 수열의 합이 특정 값 M과 같은 경우의 수를 찾는 문제입니다.
• 우선, 두 개의 포인터 start와 end를 설정합니다. 이후 end 포인터를 오른쪽으로 움직이며 부분 합을 계산하고, 만약 부분 합이 M보다 크다면 start 포인터를 오른쪽으로 움직여 부분합을 줄입니다. 이 과정을 반복하며 부분합이 M과 같은 경우의 수를 세어주면 됩니다.

N, M = map(int,input().split())
nums = list(map(int,input().split()))

start = end = sum_of_nums = count = 0

while True:
    if sum_of_nums >= M:
        sum_of_nums -= nums[start]
        start += 1
    elif end == N: break
    else:
        sum_of_nums += nums[end]
        end += 1
    if sum_of_nums == M:
        count += 1

print(count)

 
 

3020번: 개똥벌레

  문제  
 

• 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.
• 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

• 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.
• 위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

• 하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.
• 동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

 

  해결 방법  
 

• 이 문제는 각 석순과 종유석마다 높이가 주어지고, 개똥벌레가 날아갈 때 파괴해야하는 장애물의 최소값과 그 경우의 수를 구하는 것입니다.
• 우선 각 석순과 종유석마다 높이에 따른 갯수 배열을 만듭니다. 그 후 각 높이에 대해서 위에서부터 아래로 내려오며 파괴해야하는 장애물 갯수(위에서 내려온 석순 갯수 + 아래에서 올라온 종유석 갯수) 배열을 만듭니다.

import sys; input=sys.stdin.readline

N, H = map(int, input().split())
obstacles = [0] * (H+1)
min_obstacles = N
count = 0

for i in range(N):
    obstacle = int(input())
    if i % 2 == 0: # 석순
        obstacles[H-obstacle+1] += 1
    else: # 종유석
        obstacles[1] += 1
        obstacles[obstacle+1] -= 1

for i in range(2, H+1):
    obstacles[i] += obstacles[i-1]

for i in range(1, H+1):
    if min_obstacles > obstacles[i]:
        min_obstacles = obstacles[i]
        count = 1
    elif min_obstacles == obstacles[i]:
        count += 1

print(min_obstacles, count)

 

• 위의 두 문제 모두 누적 합 개념을 활용하여 해결할 수 있습니다. 이러한 접근 방식은 문제의 효율성을 크게 향상시키며 복잡한 계산 과정을 간소화하는 데 도움이 됩니다. 따라서 앞으로 다양한 코딩 테스트 문제를 해결하는 데 이러한 접근 방식을 활용하면 좋겠습니다.