algorithm

복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 일반적으로 코딩테스트 환경에서 O(n3)을 넘어가면 문제 풀이에서 사용하기 어렵다 (c 기준 n의 크기가 5000이 넘어가면 10초 이상의 시간 소요) 다음은 모두 시간 제한이 1초인 문제에 대한 예시이다. N의 범위가 500인 경우 : O(n3)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 5,000인 경우 : O(n2)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 1,000,000인 경우 : O(nlogn)인 알고리즘을 설계하면 문제를 풀 수 있다. N의 범위가 10,000,000인 경우 : O(..