코딩테스트 문제를 풀다가 약수를 구하는 문제를 접했다.처음에는 다음과 같은 코드가 더 효율적이라고 생각했다.for(int i = 1; i 반복문 안에 if가 하나밖에 없기 때문이다.반면, 제곱근을 이용한 풀이를 보면 다음과 같은 구조가 나온다.for(int i = 1; i 반복문 안에 if가 두 개나 들어가 있으니 처음에는 오히려 더 비효율적인 코드가 아닐까 하는 의문이 들었다.하지만 시간복잡도를 공부하면서 중요한 사실을 알게 되었다.시간복잡도는 if문의 개수가 아니라 반복문의 횟수가 결정한다예를 들어 다음 코드를 보자.for(int i = 1; i 이 코드는 약 100만 번 반복된다.반면,for(int i = 1; i 이 코드는 if가 두 개 있지만 실제 검사 횟수는 약 2000번 정도이다.100만 번..