1. 문제 11505번: 구간 곱 구하기 (acmicpc.net) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 특정 구간의 합을 구하라는 것에서 특정 구간의 곱을 구하는 것으로 바뀜 근데 구간의 합을 구하는 것에서 몇가지 살짝? 신경써야함 2. 풀이 기본적으로 트리의 노드에 왼쪽 자식과 오른쪽 자식의 합을 저장하던 것을 왼쪽 자식과 오른쪽 자식의 곱을 저장하는 것으로 바꾸면 된다 tree[tree_index] = tree[2*tree_index]..
1. 배열의 일부 원소를 바꾸는 경우 배열의 index번째 수를 value로 바꾸고자 한다면 세그먼트 트리를 어떻게 구성해야할까 1-1) 당연히 해당 index번째 수를 포함하고 있는 구간의 합을 저장하고 있는 모든 노드의 값을 바꿔주면 된다 원래 index번째 수가 A[index]였다고 하자. 해당 구간의 합은 s+A[index]인데 A[index]가 value로 바뀌었다고 한다면? 해당 구간의 합은 s+value이다. 그러면 해당 구간의 합 s+A[index]는 s+value로 바꿀려면 어떻게 해야할까? 당연히 value-A[index]를 s+A[index]에 더해주면 된다 1-2) 노드가 저장하는 구간이 [start,end]라고 한다면, 당연히 index가 [start,end]에 포함되는 경우와 포..
1. 세그먼트 트리의 표현 배열의 크기 N이 2의 거듭제곱꼴이면 Perfect binary tree이므로 트리의 높이 h는 각 높이의 노드의 수가 x개이면 $$h=log_{2} x$$ full binary tree라면 어떨까? 어떤식으로 구성되어 있느냐에 따라 조금 달라진다..... $h= \left \lceil log_{2} x \right \rceil $이기도 하고.. $H= \left \lceil log_{2} x \right \rceil +1 $ 이기도 하고... 따라서 세그먼트 트리를 표현할 때, 배열을 이용해서 표현할 수 있고 세그먼트 트리 배열의 크기는 항상 그 크기가 일정한 높이 h인 perfect binary tree의 노드 수로 나타낼 수 있다 비어있는 부분은 0으로 채우든지 하면 되니..
1. 개요 연속적으로 나열된 수 n개가 있을때, 특정 구간의 모든 수를 합한 값을 구하는 문제 예를 들어 [10,20,30,40,50]이 있다고 가정해보자. 두번째 수부터 네번째 수까지의 합은 20+30+40=90이다. 이러한 구간 합 계산 문제는 매우 간단하게 인덱싱으로 구할 수 있을 것 같지만, 여러개의 테스트 케이스로 구성된 문제라면 이야기가 달라진다 T개의 테스트 케이스가 주어지고 테스트케이스 각각이 [left,right]에 존재하는 모든 수의 합을 구하라고 한다고 하자 만약 수열의 길이가 N이라고 한다면, 최악의 경우 O(NT)의 시간복잡도를 가진다 매 테스트케이스마다 길이 N의 구간합을 계산하라고 할 수 있기 때문이다. 하지만 만약 N=1000000이고 T=1000000이라고 한다면? O(NT..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
