https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net SET 자료형을 이용할수도 있지만 이번엔 이분탐색 메소드를 이용해보았다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new Inpu..
Problem Solving
조사범위를 좁혀가면서 조사하는 알고리즘 직접구현 java 메소드 이용 존재한다면 해당 인덱스값 반환 없으면 음수 반환
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
비트 연산자는 말 그대로 비트 단위로 연산이 이루어지는 연산자이다. '암호화' 작업처럼 임의의 숫자를 만든다거나, 메모리 용량이 부족할 때, 계산이 복잡해서 속도가 느려질 때 비트 연산자를 이용해서 빠른 속도로 계산을 할 수 있다. 데이터는 컴퓨터 내부에서 0과 1로 이루어져 있기 때문에, 0 또는 1로 표현할 수 있는 최소단위인 비트로 계산할 때 속도가 빠른 것이라고 이해할 수 있다. 비트 (bit) : 0 또는 1로 표현할 수 있는 최소 단위, 8비트가 모이면 1 바이트(Byte)가 된다. 비트 논리 연산자 & | ^ ~ & (AND) 연산자 두 개의 비트값이 모두 1인 경우에만 연산 결과 값이 1이 된다. int num1 = 5; int num2 = 10; int result = num1 & num..
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까지 사각형을 그려서 사각형을 이용한다.
