https://docs.oracle.com/javase/8/docs/api/
Problem Solving/구간합
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 이진탐색이 아닌 SET 자료형으로도 풀 수 있다. 합을 set에 저장해두고 contains로 확인하는 방법이다. 로직은 똑같다. contains는 O(1)이다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IO..
https://www.acmicpc.net/problem/17232 17232번: 생명 게임 첫줄에는 바둑판의 세로길이, 가로길이를 나타내는 두 정수 N과 M, 준표가 바둑판을 관찰하고자 하는 시간 T가 주어진다. 두번째 줄에는 주위의 기준이 되는 정수 K, 각 칸의 다음 상황을 결정하 www.acmicpc.net 2차원 누적합을 이용한 시뮬레이션 구현 문제이다. 구현시 실수하지 않도록 주의하자. min(머시기,m)으로 해야하는데 min(머시기,n)으로 한걸 못찾아서 시간을 버렸다. 범위를 벗어나는지 체크를 if 조건문이 아닌 min, max를 이용하는 것도 좋은 방법이다. import java.util.*; import java.io.*; public class Main { static String[]..
https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 2부터 5 까지 2만큼 파고 1부터 3까지 9만큼 파라는 명령이면 prefix[2] =2 , prefix[5+1]=-2 prefix[1] =9 , prefix[3+1]=-9 (올라가기 시작하는 곳에 더할값을 더하고 더하는 값이 끝나는 다음 곳 부터는 다시 그 값을 뺴서 리셋 해주면 된다.) 로 기록하고 prefix 배열을 돌면서 prefix[i] = prefix[i-1]+prefix..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2차원 구간합은 원점으로부터의 사각형의 합을 이용한다. import java.util.*; import java.io.*; public class Main { static int[][] map; static int[][] plusmap; static int n; public static void pre(){ for(int i =1; i
https://www.acmicpc.net/problem/16713 16713번: Generic Queries 첫째 줄에는 $N, Q$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^6$, $1 \le Q \le 3 \cdot 10^6$) 둘째 줄에는 $a_1, a_2, \cdots a_N$이 공백을 사이에 두고 주어진다. ($0 \le a_i \le 10^9$) 그 후, $Q$개의 줄에 걸 www.acmicpc.net XOR 연산은 다시 XOR연산을 해주면 이전 값으로 돌아갈 수 있다. 1011 0101 ----- 1110 0101 ----- 1011 그 이유는 같은 것을 XOR하면 0이 나오고 a^b^a = a^a^b = 0^b=b이기 때문이다. import java.util.*; i..
1차원 누적합 배열[i] 부터 배열[j]의 값의 합을 여러번 구하는 문제가 나온다면 누적합배열을 생각할 수 있다. 누적합 배열을 만든다음 누적합배열[j]-누적합배열[i]를 뺴면 보다 복잡도가 낮게 구할 수 있다. 누적합 연산 뿐 아니다 구간 XOR 연산 과 곱셈에 또한 적용가능하다. 2차원 누적합 2차원은 원점으로 부터 i,j까지 사각형을 그려서 사각형을 이용한다.
