시간복잡도 팁
- 1억의 연산 당 1초가 걸린다고 생각하자.
- log(1,000,000,000)는 log 안의 0의 개수가 3개면 2^10이라고 가정한다. 즉,log(1,000,000,000)은 2^30(2^10 * 2^10 * 2^10) 번만큼의 연산을 하게 된다.
공간복잡도 팁
- 입력의 제한 조건에 따라 공간 복잡도를 계산한다.
- 배열이나, 메모리를 관리할 때 공간복잡도를 차지한다고 생각하면 된다. 이를 유의해서 메모리 초과를 조심하자.
1,000,000,000
| | |
G---M---K byte
- 만약 출력 값이 100,000 * 100,000이 넘을 경우, long long 자료형을 생각해봐야한다.
- char : 1byte
- int : 4byte (100,000,000)
- long long : 8byte
- float : 4byte
- double : 8byte
반응형
'algorithm > BOJ' 카테고리의 다른 글
| [백준 1202번] 보석도둑 c++ 풀이 (1) | 2023.12.07 |
|---|---|
| [백준 2042번] 구간 합 구하기 c++ 풀이 (0) | 2023.10.30 |
| [백준 2143번] 두 배열의 합 C++ 풀이 (1) | 2023.10.28 |
| [백준 1062번] 가르침 C++ 풀이 (0) | 2023.09.14 |
| [백준 16924번] 십자가 찾기 파이썬 완전탐색 풀이 (0) | 2023.03.01 |
