https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static List[] graph; static boolean[] visited; public static boolean bfs(int start){ boolean check = false; Queue q = new LinkedL..
전체 글
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net import java.util.*; import java.io.*; public class Main { static List[] graph; static List ans_dfs; static List ans_bfs; static boolean[] visited_dfs; static boolean[] visited_bfs; public static void df..
인접행렬 인접리스트 인접행렬 인접리스트 비교
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..