알고리즘
[알고리즘 기초] 복잡도
[1] 시간 복잡도 일반적으로 코딩 테스트 환경에서는 O(n^3)을 넘어가면 문제풀이에서 사용하기 어려움. CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요. N의 크기가 5,000이 넘는다면 족히 10초 이상의 시간이 걸리고 파이썬은 더욱 오래 걸림. 보통 코테의 시간 제한은 1~5초 가량. 따라서 연산횟수가 10억을 넘어가면 오답 판정을 받을 수 있음. N이 1000일 때 연산 횟수 O(N) 1,000 O(NlogN) 10,000 O(N^2) 1,000,000 O(N^3) 1,000,000,000 O(NlogN)인 알고리즘은 시간복잡도가 동일하더라도 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번에서 100,000번까지 실제 연산의 횟수..
