처음에 이 문제를 봤을 때는 1번이 굉장히 어려워보였다. 아니 삽입, 삭제 + O(n^3) 연산?? 그러나, 연산은 스플레이 트리로 처리할 수 있다. 그리고 그 스플레이 트리의 노드들에 대해서 다차원 세그먼트 트리를 처리해주면 1번쿼리를 처리할 수 있다. 그러면 어떻게 세그먼트 트리로 1번 쿼리를 처리하는가?? 이는 두 노드들의 집합 A, B에 대해 1번 쿼리에 대한 답을 merge하는 알고리즘을 만들면 된다! A = { A1, A2, A3, A4 ... An } B = { B1, B2, B3, B4 ... Bm } 일때, 1번 쿼리는 A+B 집합에 대해서 (n+m)C3 번째 수들의 곱으로 생각할 수 있다. 그러나, 이는 분명히 A 집합에 대해 nC3번째 수들의 곱, B집합에 대해 nC3번째 수들의 곱을..
이진 탐색은 배열의 값이 정렬되어 있을 때 사용할 수 있다. 보통, 선형 탐색 기법은 arr[0] 부터 arr[N-1] 까지를 탐색하지만, 이진 탐색은 "가운데" 값부터 탐색해서 탐색 범위를 점차 줄여나간다. 1 2 3 4 5 6 7 8 9 10 위에서 3을 검색한다고 예를 들자. 이 배열의 가장 왼쪽의 인덱스는 0이고, 오른쪽의 인덱스는 9이다. 이때, 중간을 (left + right) / 2라고 정의하자. 중간은 4이고, 값은 5이다. 5는 3보다 크기 때문에 우리는 4보다 작은 범위에서 탐색하면 된다. 이렇게 하면 탐색 범위를 반으로 줄일 수 있다. 이렇게 탐색 범위를 반으로 줄여나가는 것을 재귀적으로 하면 그것이 이진 탐색이다. 결국에는 탐색 범위가 한 칸으로 좁혀지게 되고, 그 곳이 바로 우리가..
문 제 설 명 위 문제는 사실 간단하다. O(n)의 반복문으로 A부터 B까지 3으로 나눠지거나 3,6,9 중 하나의 숫자 이상이 들어가 있는지 판별하면 풀 수 있다. int a,b,sum=0; std::cin>>a>>b; for(int i=a;i 30 ~ 39 . . . (참고로 10~19 -> 20~29에서 3의 배수는 한 칸 땅겨지고 3을 포함하는 경우는 3 , 6 , 9 그대로이므로 동일하다.) 고로 (10 ~ 19 + 00 ~ 09 + 30 ~ 39) * 3 + 10 ~ 19 로 나타낼 수 있다. memo[ i ][ 1 ] = ( memo[ i-1 ][ 1 ] + memo[ i-1 ][ 0 ] + memo[ i-1 ][ 3 ] ) * 3 + memo[ i-1 ][ 1 ]; 이렇게 일반화할 수 있다..
