코딩 테스트 공부 - 시간 복잡도

 

 

C++ 기준에서 1억번의 연산 = 약 1초로 볼 수 있다.

 

코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것

 

코딩 테스트에서는 빅-오 표기법($O(n)$)을 기준으로 수행 시간을 계산하는 것이 좋다.

 

예를 들어보자.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{
    int findNumber;
    int N = 1000000;
    srand(time(NULL));
    findNumber = rand() % 1000000;
    
    for (int i = 0; i < N; i++) {
        if (i == findNumber) {
            cout << i;
            break;
        }
    }
}

 

 

위 코드에서 시간 복잡도는 $O(n)$ 이다. 이유는 for 문을 돌 때, N 만큼 반복하기 때문이다.

 

만약, for 문이 두 번 반복된다면 시간 복잡도는 어떻게 될까?

#include <iostream>
using namespace std;

int main()
{
    int N = 10000;
    int cnt = 1;
    
    for(int i = 0; i < N; i++)
        cout << "연산 횟수 : " << cnt++ << endl;

    for(int i = 0; i < N; i++)
        cout << "연산 횟수 : " << cnt++ << endl;
}

 

for 문이 두 번 반복되면 2N 만큼 반복적인 연산을 수행한다. 그러나, 시간 복잡도 기준으로는 $O(n)$과 동일하다.

(2배가 되던 3배가 되던 $O(n)$이 된다. 만약, N 번 이상 반복될 경우 그때의 시간 복잡도는 $O(n)$이 아닌 $O(n^{2})$이 되기 때문이다.)

 

그럼 for 문이 중첩된다면?

#include <iostream>
using namespace std;

int main()
{
    int N = 10000;
    int cnt = 1;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++)
            cout << "연산 횟수 : " << cnt++ << endl;
    }
}

 

위와 같이 for 문이 두 번 중첩된 경우 $O(n^{2})$ 이 된다.

 

가장 처음에서 말한 C++ 에서 1억 번의 연산이 1초라고 가정한다면, 알고리즘 문제의 시간 제한이 2초일 경우 2억 번의 연산만으로 해결해야하는 문제가 된다.

이를 통해 시간 복잡도를 적용하여 더 나은 알고리즘을 적용하는 것이 코딩 테스트의 핵심이라고 한다.

 

이를 통해 앞으로의 코딩 테스트 공부에서 생각해보고 사용할 수 있도록 적용할 예정이다.

 

참고한 영상

https://www.youtube.com/watch?v=v0ZF1cA0afA