TIL #1 알고리즘 기초

minuk1236·7일 전
0

1. 시간 복잡도

Big O Notation 을 사용

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

시간 복잡도 예제

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

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

시간 복잡도 : O(N)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(N2)O(N^2)

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

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

시간 복잡도 특징

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

  • 빅오 표기법에서는 상수를 버린다
    O(3N2)O(3N^2) = O(N2)O(N^2)
  • 두 가지 항이 있을 경우, 변수가 같으면 큰 것만 남기고 나머지 버린다.
    O(N2+N)O(N^2 + N) = O(N2)O(N^2)
  • 두가지 항이 있는데, 변수가 다르면 그대로 둔다.
    O(N2+M)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과 동일하다.

참고

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

0개의 댓글