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,..
1. 문제 5676번: 음주 코딩 (acmicpc.net) 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 특정 구간의 수열의 곱이 양수인지 음수인지 0인지 판단하거나 특정 인덱스의 원소를 바꾸는 쿼리를 수행하는 문제 2. 곱셈의 시간복잡도 매우 큰 수를 곱할수록 프로그램의 시간복잡도가 높아진다. 이게 몇번만 연산하면 별로 차이 없어보이지만 10만번이나 반복연산해야한다면, 눈에띄게 느려진다 매우 큰 4개의 수를 곱하는 과정을 10만번 반복했는데 평균적으로 0.03초 걸린다면... 단순히 1,2,3,4 4개..
1. 문제 2357번: 최솟값과 최댓값 (acmicpc.net) 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 이번엔 임의의 구간의 최솟값과 최댓값을 구하는 문제 2. 풀이 구간합이나 구간곱과 큰 차이 없긴한데 query 함수 구할때 조금 신경써야할듯 create_segment함수에는 왼쪽 자식과 오른쪽 자식의 최솟값과 최댓값을 저장해야함 최솟값 구하는 트리와 최댓값 구하는 트리 함수를 따로 만들수도 있지만... 그냥 인자 method를 받아서 method가 0이면 최솟..
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]에 포함되는 경우와 포..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
