• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

누적합 문제4 질문

24.02.23 17:04 작성 조회수 84

1

안녕하세요,이 문제에서 prefix 를 만드실 때 처음부터 5*5 리스트를 만드셨는데 이 아이디어는 어떻게 떠올리신 건지 궁금합니다. 저 방식이 누적합 문제를 풀 때 일반적으로 사용되는 방식인가요?저같은 경우에는 4*4형식으로 만들어서 코드를 작성하였는데 이렇게 하니 답은 맞는데 시간 초과가 뜨네용

 



n, m = map(int, input().split())

box2 = []
for _ in range(n):
    box2.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if i - 1 >= 0:
            box2[i][j] += box2[i - 1][j]
        if j - 1 >= 0:
            box2[i][j] += box2[i][j - 1]
        if i - 1 >= 0 and j - 1 >= 0:
            box2[i][j] -= box2[i - 1][j - 1]

# 쿼리 처리
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    answer = box2[x2 - 1][y2 - 1]
    if x1 - 2 >= 0:
        answer -= box2[x1 - 2][y2 - 1]
    if y1 - 2 >= 0:
        answer -= box2[x2 - 1][y1 - 2]
    if x1 - 2 >= 0 and y1 - 2 >= 0:
        answer += box2[x1 - 2][y1 - 2]
    print(answer)

답변 2

·

답변을 작성해보세요.

1

질문 감사합니다!

 

질문자님이 말씀해주신 것처럼,

처음에 계산을 필요로 하는 공간보다 1칸 더 많이 만드는게 누적합의 일반적인 시작입니다 🙂

 

처음에 공간을 +1이나 + 10이나 + 100이나 크기가 커진다고해서 시간 복잡도나 공간 복잡도가 드라마틱하게 변하지 않아서 처음에는 필요한 공간을 만들어서 계산하는 게 유리합니다 🙂 !!

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.02.24

안녕하세요, 인프런 AI 인턴입니다.
Emilie님, 누적합 문제를 푸실 때 5x5 리스트를 사용하는 아이디어는 특정한 경우에 적용되는 일반적인 방법 중 하나입니다. 이 방식은 0번째 행과 열을 padding처럼 사용하여 인덱스 처리를 단순화하기 위해서 사용합니다. 이렇게 하면 누적합을 계산할 때, 범위를 벗어나는 경우에 대한 예외 처리를 별도로 하지 않아도 돼서 코드가 간결해지고, 논리적으로 이해하기 쉬워집니다.

Emilie님의 코드에서 시간 초과 문제가 발생한 것은 누적합을 계산하는 부분에서 비효율적으로 중복 계산이 일어나기 때문일 수 있습니다. box2[i][j]를 갱신할 때, 이미 계산된 값을 재활용하는 방식으로 코드를 최적화할 필요가 있습니다. 예를 들어, 한 번 계산된 누적합은 다시 계산하지 않도록 하거나, 누적합을 갱신할 때 더 효율적인 로직을 고려해 볼 수 있을 것입니다.

누적합 문제에서 보통 사용되는 방식이 궁금해 하시니, 누적합을 계산하기 위한 일반적인 방법들을 학습하는 것도 좋을 것 같습니다. 다양한 알고리즘 문제를 접하면서 시간 복잡도를 줄이기 위한 더 많은 기법들을 배울 수 있을 거예요.