시간 복잡도(Time Complexity)
- 입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법
- 표기법: 대문자 O(Big O Notation)
- 최악의 경우에 시간이 얼마나 걸리는지 나타냄.
- 시간 복잡도는 소스를 보고 계산 할 수도 있고, 소스를 작성하기 전 에 먼저 계산해볼 수 있음.
- 문제를 풀기 전 먼저 생각한 방법의 시간 복잡도를 계산해보고, 이게 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋음
1부터 N까지 더하는 최적의 코드
int sum = 0;
sum = N*(N+1)/2;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 |
시간 복잡도 계산
- 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+M)
사용한 메모리
- 메모리 제한은 보통 넉넉하기에, 걱정할 필요 없음.
- 불필요한 공간이 없다면, 대부분 메모리 제한은 알아서 지켜진다.
- 보통 가장 많은 공간을 사용하는 것은 배열 이다.
- 배열의 크기가 크면, 시간 초과를 받는 경우가 많다.
- 1초=1억=512MB
입/출력
-
C++의 경우
scanf/printf,cin,cout을 사용할 수 있다. -
cin,cout은scanf/prinf보다 느리기 때문에, 입/출력이 많은 문제의 경우,scanf/printf사용을 권장한다. -
cin,cout의 경우 아래 세 줄을 추가하면scanf/printf만큼 빨라진다.ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); -
이 경우에는
scanf/printf와cin/cout을 섞어 쓰면 안된다. 즉,cin/cout만 써야 한다. -
endl를 사용했을 경우,\n이 훨씬 빠르기에,\n권장.
테스트 케이스 형식의 코드
- 입력 for문, 출력 for문을 두는 것보다, 한 번에 입력/출력을 두는게 훨씬 빠름.
- 배열의 크기를 정하기 어렵고, 전체 입력이 매우 큰 경우 매우 큰 크기의 배열을 필요로 하기 때문.
int t;
int a, b;
scanf("%d", &t);
while(t--){
scanf("%d %d", &a, &b);
printf("%d\n", a+b);
}테스트 케이스의 개수가 명확히 주어지지 않은 경우
- 입력이 몇 개인지 주어지지 않은 경우에는 입력을 EOF까지 받으면 됨.
- EOF: End Of File
- cin의 리턴 값은 성공적으로 입력 받은 변수의 개수로, 2개가 아니면 false로 처리될 것임.
while (cin >> a >> b)