[백준] 2042 구간 합 구하기

문제

---

풀이 과정

1) 문제 이해 및 접근

초기에 구간합 문제로 누적합을 이용하여 접근을 시도했습니다.

누적합을 구하고 계속되는 추가 값 수정 및 구간합을 구하는 과정에서 많은 연산이 진행될거라 예상해서 예상 연산 횟수를 고려해봤습니다.

 

그러나 중간에 어떠한 수가 변경하게 되면 특정 수 이후의 모든 누적합이 변경해야 하거나, 다른 변수에 저장할 경우 특정 구간의 모든 수를 확인해야하는 단점이 예상되었고, 문제 조건에 따라 수의 개수 (최대 1,000,000) X 구간합 구하는 횟수 (최대 10,000) 으로 최악의 경우 10,000,000,000(10억의 연산)번으로 시간 초과 발생을 예상했습니다.

 

이후 다른 알고리즘을 알아보던 중 '세그먼트 트리' 알고리즘을 알게 되어 학습 후 적용시켰습니다.

2) 알고리즘

• 세그먼트 트리 (Segement Tree)
  특정한 구간에 대한 값을 저장한 트리

3) 풀이 코드

사용 언어 - Python

import sys
from math import ceil, log2
sys.stdin = open('input.txt')


# 초기 세그먼트 트리 생성
def initial(node, left, right):                                 # 트리의 현재 노드 / 현재 노드의 숫자 범위 시작 / 현재 노드의 숫자 범위의 끝
    if left >= right:                                           # 리프 노드에 도착하면
        segment_tree[node] = num[left]                          # 리프 노드에 숫자 저장
        node_link[left] = node                                  # 리프 노드의 인덱스 저장
        return segment_tree[node]                               # 리프 노드의 값 반환
    
    left_sum = initial(node*2, left, (left+right)//2)           # 왼쪽 구역의 합 (재귀로 트리의 밑으로 내려감)
    right_sum = initial(node*2+1, (left+right)//2+1,right)      # 오른쪽 구역의 합
    segment_tree[node] = left_sum + right_sum                   # 현재 노드의 값 = 왼쪽 구역의 누적합 + 오른쪽 구역의 누적합

    return segment_tree[node]                                   # 현재 노드의 부모를 위해 현재 노드의 값 반환


# 특정 구간의 합 반환
def section_sum(node, left, right):                                 # 트리 현재 노드 / 노드의 범위 시작 / 노드의 범위 끝
    if left > target_right or right < target_left:                  # 현재 노드가 찾으려는 범위의 누적합이 아니면 0 반환
        return 0
    elif target_left <= left and right <= target_right:             # 현재 노드가 찾으려는 범위에 완전히 속하면 현재 노드의 값 반환
        return segment_tree[node]
    
    left_sum = section_sum(node*2, left, (left+right)//2)           # 왼쪽 자식 노드 탐색
    right_sum = section_sum(node*2+1, (left+right)//2 + 1, right)   # 오른쪽 자식 노드 탐색
    return left_sum + right_sum                                     # 구해진 합 반환


# 특정 노드의 값 변경에 따른 세그먼트 트리 갱신
def update(node):                                                           # 현재 노드의 변호
    segment_tree[node] = segment_tree[node*2] + segment_tree[node*2+1]      # 현재 노드의 값은 왼쪽 자식과 오른쪽 자식의 합

    if node != 1:                                                           # 최상위 루트가 아니면, 계속해서 부모 노드를 방문하여 값 변경
        update(node//2)


N, M, K = map(int, sys.stdin.readline().split())            # 수의 개수 / 변경 횟수 / 구간합 구하는 횟수
num = [0] + [int(sys.stdin.readline()) for _ in range(N)]   # 입력받은 숫자 리스트 (편의를 위한 0번 인덱스 추가)
segment_tree = [0] * 2**ceil(log2(N)) * 2                   # 트리의 크기 지정 (log2 를 이용해 (트리의 레벨-1)을 구한다)
node_link = [-1] * (N+1)                                    # 각 숫자가 트리에서 몇번 인덱스에 값이 배정 되었는지 저장하는 변수

initial(1, 0, N-1)                                          # 트리에 값 저장

for _ in range(M+K):                                        
    a, b, c = map(int, sys.stdin.readline().split())        # 연산의 종류 / 시작 인덱스 / 끝 인덱스(변경할 값)

    if a == 1:                                              # 숫자 변경
        leaf_node = node_link[b]                            # 변경할 숫자의 트리 인덱스 구함
        segment_tree[leaf_node] = c                         # 해당 숫자 값 변경
        update(leaf_node//2)                                # 부모 노드들의 값 변경

    elif a == 2:                                            # 구간합 구하기
        target_left = b                                     # 구하려는 범위의 시작
        target_right = c                                    # 구하려는 범위의 끝
        print(section_sum(1, 0, N-1))                       # 구간합 구하기

---

결과 및 학습한 내용

1) 어려웠던 내용

세그먼트 트리에 대해 알고 있지 않아 시간을 단축해서 연산 및 구간의 합을 구하기 어려웠습니다.

(1) 참고 사이트

• 블로그
  세그먼트 트리의 개념 및 구현 방식 학습
• 블로그
  세그먼트 트리의 개념 및 구현 방식 학습

2) 새롭게 학습한 내용

일차원적인 배열에서 특정 부분의 구간에 대한 합을 구하고, 연속해서 값에 변동이 발생하고 그에 따른 특정 구간의 합을 구하는 경우에 사용하는 세그먼트 트리의 개념에 대해 새롭게 학습했습니다.

트리의 크기를 구하기 위해 트리의 레벨을 알아야 했는데, 리프 노드의 개수가 주어질때 트리의 레벨을 구하는 방법을 학습했습니다.

트리의 레벨 = ceil(log2(리프 노드 개수)) + 1

---

문제 링크

- https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다