스위프트 코딩테스트 강좌, 구간 곱 구하기

프로그래밍 면접이나 코딩 테스트에서 자주 마주치는 문제 중 하나가 ‘구간 곱 구하기’입니다. 이 문제는 주어진 배열의 특정 구간에 대한 곱을 효율적으로 계산하는 과정을 통해, 데이터 구조와 알고리즘에 대한 깊은 이해를 요구합니다. 이번 장에서는 이 문제를 이해하고, 효율적인 해결방법에 대해 알아보도록 하겠습니다.

문제 정의

주어진 정수 배열 nums와 여러 쿼리 queries가 있을 때, 각 쿼리가 정의하는 구간의 곱을 반환하는 문제를 푸는 것입니다. 구간의 곱은 해당 구간 내의 모든 숫자를 곱한 결과를 의미합니다.

문제 예시

말: 
입력: nums = [1, 2, 3, 4, 5]
쿼리: queries = [[0, 1], [1, 3], [2, 4]]
출력: [2, 24, 60]
설명:
- 첫 번째 쿼리 [0, 1]은 nums[0] * nums[1] = 1 * 2 = 2를 반환합니다.
- 두 번째 쿼리 [1, 3]은 nums[1] * nums[2] * nums[3] = 2 * 3 * 4 = 24를 반환합니다.
- 세 번째 쿼리 [2, 4]는 nums[2] * nums[3] * nums[4] = 3 * 4 * 5 = 60을 반환합니다.

문제 해결 방안

구간 곱을 계산하는 문제는 기본적으로 이중 반복문을 사용하면 됩니다. 하지만 쿼리의 수가 많고 배열이 클 경우, 이중 반복문은 비효율적이므로 다른 방법을 고려해야 합니다. 특히, 쿼리의 수가 N이고 각 쿼리마다 구간의 곱을 계산하는 데 O(M)의 시간이 필요하므로, 최악의 경우 O(N * M)이 됩니다. 따라서, O(N + Q) 시간에 해결할 수 있는 방법을 찾아야 합니다.

선형 시간 복잡도로 구간 곱 계산하기

우리는 누적 곱(pre-computation)이라는 기법을 활용하여 주어진 문제를 해결할 수 있습니다. 이 방식은 각 쿼리의 시작과 끝 인덱스를 활용하여 빠르게 구간의 곱을 계산할 수 있도록 도와줍니다.

누적 곱 계산

우선, 누적 곱 배열을 작성합니다. 누적 곱 배열은 prefixProduct라는 이름으로 정의하고, prefixProduct[i]는 nums[0] * nums[1] * ... * nums[i]를 의미합니다. 이렇게 하면, 구간 [i, j]의 곱은 prefixProduct[j] / prefixProduct[i-1]로 간단히 구할 수 있습니다.

스위프트 코드 구현


import Foundation

func rangeProduct(_ nums: [Int], _ queries: [[Int]]) -> [Int] {
    var prefixProduct = [Int](repeating: 1, count: nums.count + 1)
    
    // 누적 곱 배열 생성
    for i in 0..

코드 분석

위 코드는 다음과 같은 절차로 동작합니다:

누적 곱 배열 생성: 배열 nums를 순회하며 각 위치의 누적 곱을 계산합니다. 이 과정의 시간복잡도는 O(N)입니다.
쿼리 처리: 주어진 쿼리를 하나씩 확인하며 구간 곱을 계산합니다. 각 쿼리를 처리하는 시간복잡도는 O(1)입니다.
따라서 전체적인 시간복잡도는 O(N + Q)입니다.

결론

본 강좌를 통해 구간 곱 구하기 문제를 효율적으로 해결하는 방법을 배웠습니다. 기초적인 이중 반복문 방식에서 탈피하여 누적 곱을 사용하는 방법을 통해 문제를 해결한 것은 많은 알고리즘 문제에서 유용하게 적용될 수 있는 기법입니다. 이러한 형태의 문제는 현실의 데이터 처리를 위한 다양한 어플리케이션에서도 사용되기 때문에, 이 문제를 잘 이해하고 활용하는 것이 중요합니다.

향후 더 많은 코딩 문제에 도전하며, 실력을 쌓아가시길 기원합니다!