알고리즘과 입/출력

시간복잡도

• 시간 복잡도를 이용하면 작성한 코드가 시간이 얼마나 걸릴지 예상할 수 있다.
  
• 표기법으로 대문자 O를 사용한다.
  
• 입력의 크게에 대해서 시간이 얼마나 걸릴지 나타내는 방법
  

  //1부터 N까지 합을 계산
  int sum = 0;
  for(int i=1; i<=n; i++) {
    sum += i;
  }
  //시간 복잡도 : O(n)
  

• 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도이다.
  
• 1초가 걸리는 입력의 크기

O(1)
O(lgN)
O(N) : 1억
O(NlgN) : 5백만
O(N^2) : 1만
O(N^3) : 500
O(2^N) : 20
O(N!) : 10

• 시간 복잡도의 의미

O(1) : 단순계산(a+b 같은 연산, 배열에 접근하는 연산)
O(lgN) : N개를 절반으로 계속해서 나눔
O(N) : 1중 for문
O(NlgN)
O(N^2) : 2중 for문
O(N^3) : 3중 for문
O(2^N) : 크기가 N인 집합의 부분 집합
O(N!) : 크기가 N인 순열

• Big O Notation에서 상수는 버린다.

O(3N^2) = O(3N^2)
O(1/2N^2) = O(N^2)
O(5) = O(1)

• 두가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다.

O(N^2+N) = O(N^2)
O(N^2+NlgN) = O(N^2)

• 두가지 항이 있는데 변수가 다르면 놔둔다.

O(N^2+M) = O(N^2+M)

입/출력

A+B

//a와 b를 입력받고 a+b를 출력
public class main {
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
        int a,b;
        a = sc.nextInt();
        b = sc.nextInt();
        System.out.println(a+b);
    }
}

• 테스트케이스가 주어질 경우 각각을 독립적인 문제로 생각하고 풀면 된다.

//테스트 케이스c와 a,b를 입력받고 a+b를 출력
public class main {
	public static void main(String args[]){
    	Scanner sc = new Scanner(System.in);
        int a,b,c;
		c = sc.nextInt();
        while(c--) {
        	a = sc.nextInt();
			b = sc.nextInt();
        	System.out.println(a+b);
        }
    }
}