1. 시간 복잡도

Big O Notation 을 사용

• 입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법
• 최악의 경우에 시간이 얼마나 걸릴지 알 수 있음
• 작성한 코드가 시간이 대략 얼마나 걸릴지 예상 가능

시간 복잡도 예제

1부터 N까지 합을 계산하는 코드

int sum = 0;
for(int i=1; 1<=N; i++){
	sum += 1;
}

시간 복잡도 : $O(N)$

int sum = 0;
for (int i=1; i<=N; i++){
	for(int j=1; j<=N; j++){
    	if(i==j){
        	sum += j;
        }
    }
}

시간 복잡도 : $O(N^2)$

int sum = 0;
sum = N*(N+1)/2;

시간 복잡도 : $O(1)$

시간 복잡도 특징

$O(1)$, $O(lgN)$, $O(N)$, $O(NlgN)$, $O(N^2)$, $O(N^3)$, $O(2^N)$, $O(N!)$

• 빅오 표기법에서는 상수를 버린다
  $O(3N^2)$ = $O(N^2)$
• 두 가지 항이 있을 경우, 변수가 같으면 큰 것만 남기고 나머지 버린다.
  $O(N^2 + N)$ = $O(N^2)$
• 두가지 항이 있는데, 변수가 다르면 그대로 둔다.
  $O(N^2 + M)$

2. 입력, 출력 속도 개선

입력

Scanner sc = new Scanner(System.in);

입력이 많은 경우 속도가 느리다.

BufferedReader br = new BufferedReader(new InputStreamreader(System.in));

BufferedReader를 사용하면 속도가 향상된다.

출력

• StringBuilder 사용
• BufferedWriter 사용

문제 1

백준 문제 A+B-3

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	while(n-- > 0) {
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		System.out.println(a+b);
	}
}

입력을 다 받은후 모아서 출력을 하려면 배열을 써야한다.
하지만 배열의 크기를 미리 정할 수 없기 때문에 입력을 받은 뒤 바로 출력을 하는 형태로 구현해야 함

문제 2

백준 문제 A+B-4

• 해당 문제는 처음에 입력이 몇개인지 주어지지 않는 경우이다.
• 즉, 입력을 EOF(End-Of-File)까지 받으면 되는 것이다.
• Scanner 의 hasNext()를 사용하면 된다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);	
		while(sc.hasNextInt()) {
			int a = Integer.parseInt(sc.next());
			int b = Integer.parseInt(sc.next());
			System.out.println(a+b);
		}
}

정수형 입력을 받기 때문에 hasNextInt()를 사용하였고, 나머지는 문제1과 동일하다.

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.