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. 배열의 일부 원소를 바꾸는 경우 배열의 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. 특정한 구간에 존재하는 모든 수의 합 어떤 수열이 주어질때, 만약 특정 구간 [a,b]에 존재하는 모든 수의 합을 구하라고 한다면 어떻게 구할 수 있을까? 가장 쉬운 방법은, 그냥 반복문으로 [a,b]까지 돌아서 모든 수의 누적합을 구하면 된다 answer = 0 for i in range(a,b+1): answer += A[i] 만약 배열 A의 크기가 N일때, 최악의 경우 위 코드의 시간 복잡도는 O(N)이다. 1번부터 N번까지 다 더하라하면 O(N)이니까 여기까지는 괜찮은데 만약 이러한 질문을 M번이나 한다면? O(N)의 연산을 M번 수행해야하므로, 시간복잡도는 O(NM)이고 N,M이 매우 크다면, 당연히 매우 느리다 2. Prefix sum 만약 S[0] = 0이고, 1번부터 i번까지의 수열 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
