1. 문제 16975번: 수열과 쿼리 21 (acmicpc.net) 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 주어진 구간에 특정 값을 더해주고, 배열 A의 x번째 수를 출력하는 문제 2. 풀이 lazy propagation을 쓰지 않고 팬윅 트리를 이용하는 방법도 있다는데.. 아직 팬윅 트리는 공부하지 않았으니까 넘어가고 정직하게 lazy propagation으로 풀어보자 먼저 목표는 A 배열의 값을 바꾸고, 구간의 합이나 곱이나 이런게 아니라 결국에 A[x]를 출력하는 것이다. 그러..
1. 문제 크기가 N인 정수의 배열 A가 주어지며 구간의 합을 구하는 문제를 M번 수행하는 문제에서 중간에 index번째 수를 value로 바꾸는 문제는 세그먼트 트리를 이용하여 해결했다. 이번엔 단순히 i번째 수를 value로 바꾸는 것이 아니라, i번째 수부터 j번째 수에 v를 더하는 경우를 생각해보자. 세그먼트 트리에서 index번째 수를 value로 바꾸는 연산은 O(logN)인데, i번째수부터 j번째 수를 모두 v로 바꾼다면 최대 O(NlogN)이다. 하지만 그냥 i번째 수부터 j번째 수를 순회해서 바꾸면 O(N)이다. 세그먼트 트리를 사용했더니 오히려 더 느리게 된다 2. 구간을 변경하는 update함수 [left,right]의 모든 수에 value를 더하는 작업을 수행해야한다면? [left,..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
