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까지 사각형을 그려서 사각형을 이용한다.
https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 안테나를 왼쪽부터 오른쪽으로 이동한다고 생각하면 처음에는 계속 거리의 합이 작아 질것이다. 이렇게 작아지는 것이 만약 집이 5개라면 3번째지점을 지나는 순간에 다시 합이 커질 것이다. 왜냐하면 3번째집을 만나기전에는 2개에 집에서 한칸씩 멀어지더라도 3개의 집에서는 한칸씩 가까워 지기에 이득이였기 때문이다. 만약 집이 짝수라면 2번쨰집을 지나고 3번째집을 도착할 때까지는 값이 같기에 2번째집의 위치가 답이다. 중앙값의 ..
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net sort의 comparator에서 조건문을 if(!=)로 하면 더 깔끔해질 수도 있다. 자릿수 합을 구하는 부분을 함수로 바꾸면 더욱 깔끔할 듯하다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br =..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static class Meeting{ Integer start; Integer end; Meeting(Integer start, Integer end){ this.start= start; this.end = end; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..
https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 링크드해쉬맵을 이용하면 클래스를 만들 필요가 없다. import java.io.*; import java.util.*; public class Main { public static class Num{ Integer num; Integer count; Integer idx; public Num(Integer num, Integer count, Integer idx){ this.num=num; this.count=count; this.idx ..
HashSet 기본적인 SET 순서가 뒤죽박죽임 HashSet은 Set 인터페이스의 구현 클래스입니다. 그렇기에 Set의 성질을 그대로 상속받습니다. Set은 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있습니다. 저장 순서가 유지되지 않습니다. 만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용하면 됩니다. Set 인터페이스를 구현한 클래스로는 HashSet과 TreeSet이 있는데 HashSet의 경우 정렬을 해주지 않고 TreeSet의 경우 자동정렬을 해준다는 차이점이 있습니다. Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 점입니다. 삽입 삭제 조회 시 0(1)을 기대할 수 있지만 해시충돌 같은 이슈로 더 늘어 날 ..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Bu..
