어떤 N개의 수가 주어져 있을 때, 이 수들에 대한 구간 곱을 효율적으로 구하고, 중간에 수의 변경이 빈번히 일어나는 상황을 고려해보자. 예를 들어, 수열이 1, 2, 3, 4, 5로 주어지고, 세 번째 수를 6으로 바꾼 후에 두 번째부터 다섯 번째까지의 곱을 구하면 240이 된다. 여기서 다섯 번째 수를 2로 변경하고, 세 번째부터 다섯 번째까지의 곱을 구하면 48이 된다.
이러한 문제를 해결하기 위해서는 수의 변경과 구간 곱 계산을 효율적으로 처리할 수 있는 자료 구조가 필요하다. 이 글에서는 백준 온라인 저지 11505번 “구간 곱 구하기” 문제를 해결하기 위한 알고리즘과 코드 구현에 대해 알아보겠다.
voidbuild(intnode,intstart,intend){if(start==end){// 리프 노드일 경우
if(arr[start]==0){tree[node].zero_count=1;tree[node].product=1;// 곱셈의 항등원
}else{tree[node].zero_count=0;tree[node].product=arr[start]%MOD;}}else{// 내부 노드일 경우
intmid=(start+end)/2;build(node*2,start,mid);// 왼쪽 자식 노드
build(node*2+1,mid+1,end);// 오른쪽 자식 노드
tree[node].zero_count=tree[node*2].zero_count+tree[node*2+1].zero_count;if(tree[node].zero_count>0){tree[node].product=1;// 0이 존재하므로 곱은 0
}else{tree[node].product=(tree[node*2].product*tree[node*2+1].product)%MOD;}}}
voidupdate(intnode,intstart,intend,intidx,int64_tval){if(start==end){// 리프 노드 업데이트
arr[idx]=val;if(val==0){tree[node].zero_count=1;tree[node].product=1;}else{tree[node].zero_count=0;tree[node].product=val%MOD;}}else{intmid=(start+end)/2;if(idx<=mid){update(node*2,start,mid,idx,val);// 왼쪽 자식 노드 갱신
}else{update(node*2+1,mid+1,end,idx,val);// 오른쪽 자식 노드 갱신
}tree[node].zero_count=tree[node*2].zero_count+tree[node*2+1].zero_count;if(tree[node].zero_count>0){tree[node].product=1;}else{tree[node].product=(tree[node*2].product*tree[node*2+1].product)%MOD;}}}
int64_tquery(intnode,intstart,intend,intl,intr){if(r<start||end<l){// 구간이 겹치지 않음
return1;// 곱셈의 항등원 반환
}if(l<=start&&end<=r){// 구간이 완전히 포함됨
if(tree[node].zero_count>0){return0;}else{returntree[node].product%MOD;}}intmid=(start+end)/2;int64_tleft_product=query(node*2,start,mid,l,r);int64_tright_product=query(node*2+1,mid+1,end,l,r);return(left_product*right_product)%MOD;}
intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>N>>M>>K;arr.resize(N+1);tree.resize(4*N);for(inti=1;i<=N;++i){cin>>arr[i];}build(1,1,N);inttotal_ops=M+K;for(inti=0;i<total_ops;++i){inta;int64_tb,c;cin>>a>>b>>c;if(a==1){// 값 변경 연산
update(1,1,N,b,c);}elseif(a==2){// 구간 곱 계산 연산
int64_tresult=query(1,1,N,b,c);cout<<result%MOD<<'\n';}}return0;}
importsysMOD=1000000007input=sys.stdin.readlinedefbuild():# 리프 노드 초기화foriinrange(N):idx=size+ival=arr[i]ifval==0:tree_zero[idx]=1tree_prod[idx]=1else:tree_zero[idx]=0tree_prod[idx]=val%MOD# 내부 노드 초기화foridxinrange(size-1,0,-1):left=idx<<1right=left|1tree_zero[idx]=tree_zero[left]+tree_zero[right]iftree_zero[idx]:tree_prod[idx]=1else:tree_prod[idx]=(tree_prod[left]*tree_prod[right])%MODdefupdate(pos,val):idx=size+posifval==0:tree_zero[idx]=1tree_prod[idx]=1else:tree_zero[idx]=0tree_prod[idx]=val%MODidx>>=1whileidx:left=idx<<1right=left|1tree_zero[idx]=tree_zero[left]+tree_zero[right]iftree_zero[idx]:tree_prod[idx]=1else:tree_prod[idx]=(tree_prod[left]*tree_prod[right])%MODidx>>=1defquery(l,r):l+=sizer+=sizezero_count=0result=1whilel<=r:ifl%2==1:zero_count+=tree_zero[l]ifzero_count==0:result=(result*tree_prod[l])%MODl+=1ifr%2==0:zero_count+=tree_zero[r]ifzero_count==0:result=(result*tree_prod[r])%MODr-=1l>>=1r>>=1return0ifzero_countelseresult%MODN,M,K=map(int,input().split())arr=[int(input())for_inrange(N)]size=1whilesize<N:size<<=1tree_zero=[0]*(size<<1)tree_prod=[1]*(size<<1)build()for_inrange(M+K):cmd=''whilecmd.strip()=='':cmd=input()a,b,c=map(int,cmd.strip().split())ifa==1:# 업데이트 연산update(b-1,c)else:# 쿼리 연산res=query(b-1,c-1)print(res)
코드 설명
입력 최적화: sys.stdin.readline()을 사용하여 입력을 빠르게 받는다.
세그먼트 트리 구현:
배열 크기를 가장 가까운 2의 제곱 수로 설정하여 완전 이진 트리를 만든다.
리프 노드와 내부 노드를 초기화하는 build() 함수를 사용한다.
업데이트 연산은 update() 함수를 통해 O(log N) 시간에 처리한다.
쿼리 연산은 query() 함수를 통해 O(log N) 시간에 처리한다.
메모리 사용 최적화:
threading 모듈을 사용하지 않아 추가적인 메모리 사용을 방지한다.
배열 인덱싱을 효율적으로 처리하여 메모리 낭비를 최소화한다.
입력 처리 주의사항:
입력 줄이 비어 있을 경우를 대비하여 while 문을 사용하여 입력을 받는다.
이는 온라인 저지에서 입력의 끝에 공백이 있을 수 있기 때문이다.
결론
이번 문제는 세그먼트 트리를 이용하여 수의 변경과 구간 곱 계산을 효율적으로 처리하는 방법을 학습할 수 있었다. 특히, 곱셈 연산에서 0이 존재할 경우를 처리하기 위해 추가적인 정보를 저장하는 아이디어가 중요했다. 이를 통해 O(log N)의 시간 복잡도로 모든 연산을 수행할 수 있었다.
이번 문제는 세그먼트 트리를 이용하여 수의 변경과 구간 곱 계산을 효율적으로 처리하는 방법을 학습할 수 있었다. 특히, Python에서 메모리 초과를 방지하기 위해 threading 모듈을 사용하지 않고도 효율적인 코드를 작성하는 것이 중요했다. 이를 통해 O(log N)의 시간 복잡도로 모든 연산을 수행할 수 있었다.
앞으로도 이러한 자료 구조와 알고리즘을 활용하여 다양한 문제를 효율적으로 해결할 수 있도록 노력해야겠다.