1. 문제1 11143번: Beads (acmicpc.net) 11143번: Beads The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively. Then follows P + Q lines with either P i a, saying www.acmicpc.net 2. 풀이 문제를 요약하자면 구간의 합을 구하는 세그먼트 트리 create_segment라는 함수는 만들필요가 없다 P라는 query가 ..
1. 문제 2018번: 수들의 합 5 (acmicpc.net) 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 2. 풀이 이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다 자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다 그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다..
1. 문제 14246번: K보다 큰 구간 (acmicpc.net) 14246번: K보다 큰 구간 n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오. www.acmicpc.net 2. 풀이 첫번째 핵심 두개의 포인터 i,j를 두고 i~j까지의 합이 k보다 작다면, 끝 포인터 j를 1칸 늘린다. 모든 수가 자연수이기 때문에 끝 포인터 j를 1칸 늘리면 구간 합이 증가하게 된다 ------------------------------------------------------------------------------------------------------------ 두번째 핵심 반대로 i~j까지의 합이 k보다 크다면, 그 순간 ..
1. 문제 18436번: 수열과 쿼리 37 (acmicpc.net) 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net 구간에서 짝수의 개수를 출력하거나, 홀수의 개수를 출력하거나, 값을 바꾸는 쿼리를 수행하는 세그먼트 트리를 만드는 문제 2. 풀이 조금 응용해서, 세그먼트 트리를 2차원으로 구성해보자 [[0,0] for _ in range(n+1)] 형태로 tree[tree_index][0]은 구간의 짝수의 개수, tree[tree_index][1]..
1. 문제 14245번: XOR (acmicpc.net) 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 구간에 어떤 수를 XOR하는 쿼리와 어떤 index에 대응하는 원소를 출력하는 쿼리를 수행하는 문제 2. 풀이 구간에 수를 연산하니까 느리게 갱신되는 세그먼트 트리가 필요할 것 같고 index 하나 원소만 출력하는 트리는 이미 배웠으니까 def create_segment(A,tree,tree_index,A_start,A_end): if A_start == A_end: tree[..
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
