파이썬 백준 알고리즘: 구간 곱 구하기 11505

안녕하세요! 알고리즘 풀이 포스트를 작성할 개발자로 도움을 드릴게요. 이번에는 "구간 곱 구하기" 문제를 다루어보려고 합니다. 구간 곱 구하기 문제는 주어진 수열에서 특정 구간의 곱을 계산하는 문제입니다.

문제 내용

주어진 수열에서 특정 구간의 곱을 구하는 문제입니다. 초기에 주어지는 수열은 변경될 수 있으며, 변경된 수열에서도 특정 구간의 곱을 구해야 합니다.

문제 이해하기

주어진 문제를 풀기 위해 세그먼트 트리(Segment Tree) 자료구조를 활용합니다. 세그먼트 트리는 주어진 배열을 분할하여 구간에 대한 정보를 빠르게 계산하기 위한 자료구조입니다.

주어진 문제에서는 수열의 변경과 특정 구간의 곱을 계산해야 합니다. 이를 위해 Bottom-Up 방식과 Top-Down 방식을 함께 사용합니다.

1. Bottom-Up 방식:
   • 수열의 변경을 업데이트하는 함수 **update()**를 구현합니다.
   • update() 함수는 특정 위치에 있는 값을 변경하고, 해당 위치의 부모 노드부터 루트 노드까지의 구간 곱을 계산하여 갱신합니다.
2. Top-Down 방식:
   • 특정 구간의 곱을 계산하는 함수 **query()**를 구현합니다.
   • query() 함수는 주어진 구간을 탐색하면서 구간에 속하는 노드의 값을 곱하여 결과를 반환합니다.

주어진 문제에서는 초기 수열을 기반으로 세그먼트 트리를 초기화한 후, 수열의 변경과 특정 구간의 곱을 계산합니다.

풀이 코드

pythonCopy code
import sys
input = sys.stdin.readline
DEFAULT_NUM = 1
DIVIDE_NUM = 1_000_000_007

# Bottom-Up 방식
def update(target, value):
    # target에 value 반영
    node = s + target - 1
    tree[node] = value
    # Root에 도달할 때까지 반복문 돌기 (좌측, 우측의 곱을 노드에 저장)
    node //= 2
    while node > 0:
        tree[node] = (tree[node * 2] * tree[node * 2 + 1]) % DIVIDE_NUM
        node //= 2

# Top-Down 방식
def query(left, right, node, query_left, query_right):
    # 연관 없음 -> 결과에 영향이 없는 값 return
    if query_right < left or right < query_left:
        return DEFAULT_NUM
    # 판단 가능 -> 현재 노드 값 return
    elif query_left <= left and right <= query_right:
        return tree[node]
    # 판단 불가 -> 자식에게 위임, 자식에서 올라온 값의 곱을 return
    mid = (left + right) // 2
    left_result = query(left, mid, node * 2, query_left, query_right)
    right_result = query(mid + 1, right, node * 2 + 1, query_left, query_right)
    return (left_result * right_result) % DIVIDE_NUM

n, m, k = map(int, input().split())  # 개수, 변경, 구간 곱
s = 1
while s < n:
    s *= 2

# init tree
tree = [DEFAULT_NUM] * (2 * s)
for i in range(n):
    tree[s + i] = int(input())
for i in range(s - 1, 0, -1):
    tree[i] = (tree[i * 2] * tree[i * 2 + 1]) % DIVIDE_NUM

for _ in range(m + k):
    a, b, c = map(int, input().split())
    if a == 1:
        update(b, c)
    else:
        print(query(1, s, 1, b, c))

풀이 방법

주어진 문제를 해결하기 위해 세그먼트 트리를 활용하여 풀이합니다.

1. Bottom-Up 방식:
   • update() 함수를 사용하여 수열의 변경을 업데이트합니다.
   • update() 함수는 변경할 위치에 있는 값을 변경한 후, 해당 위치의 부모 노드부터 루트 노드까지의 구간 곱을 계산하여 갱신합니다.
   • 업데이트는 수열의 길이(n)에 따라 수행합니다.
2. Top-Down 방식:
   • query() 함수를 사용하여 특정 구간의 곱을 계산합니다.
   • query() 함수는 주어진 구간을 탐색하면서 구간에 속하는 노드의 값을 곱하여 결과를 반환합니다.

세그먼트 트리를 초기화한 후, 주어진 m개의 변경 작업과 k개의 구간 곱 연산을 수행합니다. 변경 작업은 update() 함수를 호출하여 수열의 값을 변경하고, 구간 곱 연산은 query() 함수를 호출하여 특정 구간의 곱을 계산하여 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O((m + k) log n)입니다. 초기화 단계에서 세그먼트 트리를 구성하는데 O(n)의 시간이 걸리며, 변경 작업과 구간 곱 연산은 각각 O(log n)의 시간이 소요됩니다. 따라서 전체적인 시간 복잡도는 O((m + k) log n)입니다.

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음