1. 시간복잡도, 공간복잡도

시간 제한이 1초인 문제의 경우

→ 1억에 1초가 걸린다고 한다. 100,000,000

• N의 범위가 500: 시간 복잡도가 O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2,000: 시간 복잡도가 O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100,000: 시간 복잡도가 O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10,000,000: 시간 복잡도가 O(N) 알고리즘을 설계하면 문제를 풀 수 있다.
• 0 7개까지는 오케이

** BFS의 시간복잡도는 O(n^2)이다. (모든 정점 n^2, 정점마다 4방 -> O(4n^2)=O(n^2))

** Collections.sort()의 시간복잡도는 O(nlogn)이다.

공간복잡도

• int a[1000]: 4KB
• int a[1000000]: 4MB
• int a[2000][2000]: 16MB

[Algorithm] 복잡도 (with 자바)

2. 입력받기, StringBuilder

public static void main(String[] args) throws Exception{
	System.setIn(new FileInputStream("src/main/java/input.txt"));
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	//한 줄 입력
	StringTokenizer st = new StringTokenizer(br.readline);
	N = Integer.parseInt(st.nexttoken());
	//띄어쓰기 입력
	st = new StringTokenizer(br.readline);
	for(int n=0;n<N;n++){
		arr[n] = st.nextToken();
	}
}