시간 복잡도와 언어별 유의사항

알고리즘을 풀때 가장 중요한것은 효율성

효율성

효율성을 따질때는 먼저 문제의 크기를 살펴봐야한다.
문제의 크기 예는 상품의 개수, 접속자 수가 있고
문제의 크기를 N이라고 할때 문제의 크기 N에 따라 걸리는 시간이 다르다.

!!문제를 해결할때 문제의 크기를 먼저보고 방법을 생각해야한다.

시간 복잡도

Big O Notation
최악의 경우 시간이 얼마가 걸릴지 예측할수있다.

<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

메모리

메모리 제한은 보통 넉넉하기 때문에 걱정 ㄴㄴ
보통 가장 많은 공간을 차지하는 것은 보통 배열이다.

JAVA 입출력

Scanner 는 느림
BufferedReader는 불편한 대신 빠름
StringBuilder을 이용해서 모아서 출력한다면 빠름

※백준 A+B -4번 문제

입력이 몇개인지 주어지지 않은 경우에는
입력을 EOF까지 받으면 된다
java : while(sc.hasNextInt())
더 받을 정수가 있는지?

언어별 유의사항

시간 초과

java string의 += 연산은 O(N+K)이기 때문에
StringBuilder를 이용해야한다.