Problem Solving

인접행렬 인접리스트 인접행렬 인접리스트 비교

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 리스트 이터레이터 문제이다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter b..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] ans = new int[n]; List list = new LinkedList(); for(int i=1;i

이터레이터는 헷갈린다. 이전의 것이 반환되는데 이것을 둘사이를 이어주는 링크에 위치한다고 생각하면 이해가 쉬울 수도 있다. iterator(4)도 존재할 수 있고 그 이후도 존재할 수 있다. 값은 null일 것이다.

배열 리스트 vector는 Collection이전의 클래스. 속도가 비교적 느림. 또한 코테는 싱글스레드이기에 코테에서는 맞지않다. ArrayList 와 LinkedList ArrayList add는 O(N)이지만 평균적으로는 O(1)이다 Capacity가 전부 찼을경우에만 O(N)인데 1.5배씩 크게 만들기 때문에 크기가 커질수록 grow가 적어진다. 더군다나 크기가 작을 때 grow는 O(상수)급이기에 크게 신경 ㄴㄴ 결론: 최악 O(N)이지만 O(1)로 여겨도 크게 문제 없다. 코테에서는 신경쓰기 import java.util.Arrays; public class MyArrayList { private static final int DEFAULT_CAPACITY = 10; private int si..

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine..

https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 누적합 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.read..

https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 누적합 또는 투포인터로 풀이 가능 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] input1 = br.readL..