CS/Algorithm

[Algorithm] 코딩 테스트 풀이 TIPs

코딩 테스트 풀이 TIPs 빅오 표기법 순위 명칭 O(1) 상수 시간(Constant time) O(logN) 로그 시간(Log time) O(N) 선형 시간 O(NlogN) 로그 선형 시간 O(N²) 이차 시간 O(N³) 삼차 시간 O(2ⁿ) 지수 시간 상수 시간에 가까울수록 성능이 좋고, 지수 시간에 가까울수록 성능이 좋지 않다. 알고리즘 설계 일반적인 기준의 컴퓨터에서 연산 횟수가 5억 회를 넘는 경우 파이썬은 5~15초가량의 시간이 소요된다. 코딩 테스트에서는 보통 1~5초 이내로 연산이 완료되어야 하므로(명시되지 않은 경우 대게 5초) 시간 복잡도를 잘 계산하고 알고리즘 설계를 작성해야 한다. 시간제한이 1초인 문제의 일반적 기준은 다음과 같다. 1. N의 범위가 500인 경우 : O(N³)인 ..