Programming/Etc.
코딩테스트 시간 설계 방법
Dandy Andy
2023. 8. 16. 00:31
시간 복잡도
실제 코딩 테스트 문제의 연산 시간 제한은 1~2초 가량이며,
보통 연산 횟수가 1억(10의 8승, 100,000,000)을 넘어가도록 작성하면 오답 판정 받을 수 있음에 주의해야 한다.
연산 시간 제한이 1초인 문제의 경우
- N의 범위가 500: 시간 복잡도가 O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000: 시간 복잡도가 O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000: 시간 복잡도가 O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000: 시간 복잡도가 O(N) 알고리즘을 설계하면 문제를 풀 수 있다.
공간 복잡도
공간 복잡도를 표기할 때도 빅오 표기법을 이용한다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.
정수형 자료형인 int는 4B이고 배열 크기에 따른 메모리 사용량은 다음과 같다.
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB
가장 이상적인 프로그램은 시간복잡도와 공간복잡도가 모두 낮은 것이지만, 시간 복잡도와 공간 복잡도는 반비례한다.
그러므로 두 개의 복잡도 중 한 가지를 포기해야하는 trade-off 상황이 발생하는데, 우리는 시간 복잡도를 우선으로 생각해야 한다.
시간은 돈으로 살 수 없지만, 메모리는 부족하면 돈으로 구매하여 추가 가능하다. 현대의 하드웨어는 성능이 좋아서 일반 개발자들은 평소 메모리 부족을 느낄 일이 사실상 없다.
항상 메모리보다는 수행 시간을 중요하게 여겨야 한다.
Java int, long 범위
종류설명저장 공간값의 범위 (최소값~최대값)
| int | 부호 있는 정수 | 32 bits | -2,147,483,648 ~ 2,147,483,647 |
| long | 부호 있는 정수 | 64 bits | -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 |
출처