문제 개요
두 개의 희소 벡터(sparse vector)가 리스트 형태로 주어졌을 때, 두 벡터의 내적(dot product)을 계산하여 반환하는 프로그램을 작성해 보겠습니다. 여기서 벡터는 객체로 표현되며, 각 벡터의 요소들은 객체의 멤버 변수 nums에 저장됩니다.
예를 들어 입력이 다음과 같다고 가정해 봅시다.
- vector1 = [1, 0, 0, 0, 1]
- vector2 = [0, 0, 0, 1, 1]
이때 출력은 1입니다. 내적은 각 위치의 요소끼리 곱한 뒤 모두 더한 값으로, 다음과 같이 계산됩니다.
1 × 0 + 0 × 0 + 0 × 0 + 0 × 1 + 1 × 1 = 1
해결 접근 방법
희소 벡터는 대부분의 요소가 0인 벡터입니다. 따라서 한쪽이라도 0인 경우는 곱셈 결과에 영향을 주지 않으므로, 해당 연산을 건너뛰면 불필요한 계산을 줄일 수 있습니다. 알고리즘은 다음과 같습니다.
- 결과를 저장할 변수
res를 0으로 초기화합니다. - vector2의
nums에서 각 인덱스 i와 값 v를 순회합니다. - v가 0이면 다음 반복으로 건너뜁니다(continue).
- vector1의
nums[i]가 0이어도 다음 반복으로 건너뜁니다. - 두 값이 모두 0이 아니라면
res에 v × vector1.nums[i]를 누적합니다. - 순회가 끝나면
res를 반환합니다.
Python 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
class Solution:
def __init__(self, nums):
self.nums = nums
def solve(self, vec):
res = 0
for i, v in enumerate(vec.nums):
if v == 0:
continue
elif self.nums[i] == 0:
continue
else:
res += v * self.nums[i]
return res
ob1, ob2 = Solution([1, 0, 0, 0, 1]), Solution([0, 0, 0, 1, 1])
print(ob1.solve(ob2))
입력
[1, 0, 0, 0, 1], [0, 0, 0, 1, 1]
출력
1
복잡도 분석 및 정리
이 알고리즘은 두 벡터를 한 번씩 순회하므로 시간 복잡도는 O(n), 추가 공간 없이 결과 변수만 사용하므로 공간 복잡도는 O(1)입니다.
핵심은 0인 요소를 조기에 건너뛰어 곱셈 연산 횟수를 최소화하는 것입니다. 특히 데이터가 매우 클 때 희소 벡터의 특성을 활용하면 성능을 크게 향상시킬 수 있으며, 이러한 기법은 검색 엔진의 TF-IDF 유사도 계산, 추천 시스템 등 고차원 희소 데이터를 다루는 실무 분야에서도 널리 활용됩니다.