⏳ 시간 복잡도 (Time Complexity)
시간복잡도를 알면 문제의 크기(N)에 대해 걸리는 시간을 예상
ex) O(N) 일 때
N이 1억(100,000,000)이면 약 1초
N이 10만(100,000)이면 약 0.001초
ex) O(N^2) 일 때
N이 10만(100,000) -> N^2 은 100억(10,000,000,000) 이므로 약 100초
1초가 걸리는 입력N의 크기
- O(1)
- O(lgN)
- O(N) : 1 억
- O(NlgN) : 500만
- O(N^2) : 1만
- O(N^3) : 500
- O(2^N) : 20
- O(N!) : 10
시간 복잡도 계산
Big O Notation에서 상수는 버린다.
- O(3N^2) = O(N^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)
✍📄 Java 입출력
- Scanner는 데이터 타입에 상관없이 입력을 받지만 느리다.
- System.out 속도가 느리다.
- 입력이 많은 경우에 속도가 느리기 때문에 BufferedReader를 사용한다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));- 출력이 많은 경우에 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한번만 사용.
- 또는 BufferedWriter 를 사용.
테스트케이스 입출력 문제를 풀 때
입력을 한번에 받고 출력을 한번에 하는게 아니라
입력 받고 출력하고를 반복 해야 한다.
입력의 제한이 주어지지 않을 때
입력을 EOF(End of File)까지 받으면 된다.
Java : while(sc.hasNextInt())import java.util.* public class Main{ public static void main(String args []){ Scanner sc = new Scanner(System.in); int a,b; while(sc.hasNextInt()){ a= sc.nextInt(); b= sc.nextInt(); System.out.println(a+b); } } }
⏰ 시간 초과 (Time Limit Exceeded)
c언어의 strlen(s)의 시간복잡도는 s의 길이이다.
for(int i=0; i<strlen(s); i++) {s의 길이를 N이라고 한다면 위의 시간복잡도는 O(N^2)이다.
이러한 반복문에서 strlen을 계속 실행되는 것은 불필요하기 때문에 시간초과가 일어날 수 있다.
int l = strlen(s) 같이 어딘가에 저장을 하고 사용해야 한다.
하지만 Java에서는 String의 .length()의 시간복잡도는 O(1)이기 때문에 상관없다.
StringBuilder를 사용해야 하는 이유
Java에서 String의 += 연산은 O(N+K)이므로 StringBuilder를 이용해 문자열을 만들어야 한다. 아래 코드의 시간 복잡도는 O(N^2)
import java.util.*
public class Main{
public static void main(String args []){
String s = "";
int n = 1000000;
for(int i=0; i<n; i++){
s += "A"; // ❗
}
}
}C++에서는 s += "A";가 s에 A를 붙이는 것을 의미하기 때문에 O(1)이지만
s = s + "A";는 둘을 더해서 새로운 문자열을 만드는 것을 의미하기 때문에 O(N)이다.
하지만 Java에서는 s += "A"; 와 s = s + "A"; 는 둘 다 문자열을 더해 새로운 문자열을 만드는 것을 의미하기 때문에 O(N)이다.
💾 메모리
보통 가장 많은 공간을 사용하는 것음 보통 배열.
- 배열이 사용한 공간 : 배열의 크기 x 자료형의 크기 Byte
메모리 사용량은 별로 신경 쓰지 않아도 된다.
보통 배열의 크기가 크면 시간초과를 받고 불필요한 값이 없다면 알아서 메모리 관리가 된다.
