파이썬 코딩테스트 강좌: 구간 곱 구하기
프로그래밍 문제를 풀 때, 종종 주어지는 특정 범위의 값들을 기반으로 계산을 수행하는 경우가 있습니다. 이 글에서는 ‘구간 곱 구하기’라는 문제를 다루어 보겠습니다. 이 문제는 주어진 배열에서 특정 구간에 속하는 값을 곱하는 알고리즘을 구현하는 것입니다. 이 과정에서 효율적인 방법으로 문제를 해결하는 전략을 함께 논의하겠습니다.
문제 설명
입력으로 주어진 정수 배열과 여러 개의 쿼리가 있습니다. 각 쿼리는 두 개의 인덱스 (l, r)로 구성되어 있으며, 배열에서 해당 인덱스를 포함하는 구간의 모든 요소를 곱한 값을 출력해야 합니다. 주의할 점은 구간의 곱 결과가 매우 큰 숫자가 될 수 있어, 이를 최적화하여 계산해야 한다는 것입니다.
예시: 배열: [1, 2, 3, 4, 5] 쿼리: (1, 3) 출력: 2 * 3 * 4 = 24
문제 풀이 전략
1. 기본 접근 방법
가장 직관적인 접근 방법은 주어진 배열에서 각 쿼리에 대해 정해진 인덱스의 요소들을 반복하여 곱하는 것입니다. 하지만, 이 방식은 최악의 경우 O(Q * N) 시간복잡도를 가지게 되므로 비효율적입니다. 여기서 N은 배열의 크기, Q는 쿼리의 수를 나타냅니다. 이 방법은 쿼리 수가 많아지면 크게 느려질 수 있습니다.
2. 누적 곱을 활용한 접근 방법
효율적인 방법 중 하나는 누적 곱(Prefix Product)을 활용하는 것입니다. 누적 곱을 구하는 방법은 배열의 각 요소에 대해 그 이전까지의 곱을 계산하여 저장하는 것입니다.
- 예를 들어, 배열이
A = [1, 2, 3, 4, 5]일 경우:누적 곱 배열 P: P[0] = 1 P[1] = 1 * 1 = 1 P[2] = 1 * 1 * 2 = 2 P[3] = 1 * 1 * 2 * 3 = 6 P[4] = 1 * 1 * 2 * 3 * 4 = 24 P[5] = 1 * 1 * 2 * 3 * 4 * 5 = 120
이렇게 누적 곱 배열을 구성한 후, 구간 곱을 구하려면 다음과 같은 공식을 사용할 수 있습니다:
구간 곱 = P[r+1] / P[l]
여기서 P[i]는 i 번째 요소까지의 곱을 나타냅니다. 이 방법을 사용하면 구간 곱을 O(1) 시간 복잡도로 계산할 수 있게 됩니다.
파이썬 코드 구현
지금부터 위의 접근 방법을 참고하여 파이썬으로 구간 곱 구하기 알고리즘을 구현해 보겠습니다.
def calculate_prefix_product(arr):
n = len(arr)
prefix_product = [1] * (n + 1)
for i in range(n):
prefix_product[i + 1] = prefix_product[i] * arr[i]
return prefix_product
def range_product(arr, queries):
prefix_product = calculate_prefix_product(arr)
results = []
for l, r in queries:
product = prefix_product[r + 1] // prefix_product[l]
results.append(product)
return results
# 예시 배열 및 쿼리
arr = [1, 2, 3, 4, 5]
queries = [(1, 3), (0, 2), (2, 4)]
# 함수 호출
result = range_product(arr, queries)
print(result) # 출력: [24, 6, 60]
최종 점검
이제 코드가 제대로 작동하는지 확인할 차례입니다. 여러 테스트 케이스를 통해 올바른 결과가 나오는지 확인합니다. 이 과정에서 쿼리의 범위가 유효한지, 경계 값에서도 문제가 없는지를 점검하는 것이 중요합니다.
- 테스트 케이스 1: arr = [1,2,3,4,5], queries = [(0, 4)] => 결과: 120
- 테스트 케이스 2: arr = [10,20,30], queries = [(0, 2), (1, 1)] => 결과: [6000, 20]
- 테스트 케이스 3: arr = [0, 1, 2, 3], queries = [(0, 3), (1, 1)] => 결과: [0, 1]
결론
이 강좌에서 다룬 구간 곱 구하기 문제는 누적 곱을 적절히 활용해 효율적인 풀이를 도출하는 방법을 보여줍니다. 이러한 원리는 다른 유사한 문제를 해결하는 데도 응용할 수 있습니다. 다양한 알고리즘 문제를 통해 연습하면 더 나은 코딩 테스트 준비가 될 것입니다. 앞으로의 코딩 테스트에서 이 기술을 잘 활용하시기 바랍니다!
추가 질문
혹시나 문제가 해결되지 않거나 추가적인 질문이 있다면 언제든 저에게 문의해 주세요. Happy Coding!