[PS] Time Out을 피하는 방법

알고리즘 문제를 풀다보면 흔히 제한 시간 초과 (Time Out)을 경험할 수 있습니다. 이번 포스팅에서는 어떻게 하면 제한 시간 초과를 피할 수 있는지 그 방법에 대해서 다루어보고자 합니다. 보통 시간복잡도를 표기할 때 빅오 표기법 (Big-O Notation)으로 표기하는 것이 일반적입니다. 대표적인 시간복잡도들을 대소 관계로 나타낸 그래프는 아래의 그림과 같습니다. 그래프를 보면 주어진 입력의 크기인 N이 점점 커짐에 따라 시간복잡도의 차이가 수행시간에 큰 영향을 준다는 것을 알 수 있습니다. 상수 시간인 O(1) 이 가장 좋고, 그 다음으로는 O(logN) 이후로 O(N) 순서이며, O(2N) 과 O(N!) 과 같은 지수시간 이상의 알고리즘 들은 N이 굉장히 작은게 아니라면 제한시간 내에 문제를 ..

2020.04.05