[1주차] 코딩 테스트 합격자 되기 C++ (코딩테스트 문법) - part 1

1. 알고리즘 효율 분석

시간 복잡도란?

대부분의 코딩테스트를 공부하는 분들이라면 시간복잡도, 공간복잡도에 대해 많이 들어봤을 것이고 이게 무엇인가? 싶을 것이다.

나 또한 그랬다...

 

시간 복잡도란?? 알고리즘의 성능을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미한다. 주로 Big O 표기법으로 표현하며, 최악의 경우를 기준으로 분석한다. 시간 복잡도는 낮으면 낮을수록 좋다. 

코딩테스트 문제를 풀다 보면 아래처럼 시간제한, 메모리 제한을 본 적이 있을 것이다. (백준에서 가져옴)

이것을 보면 "읭? 이게 뭐지?" 싶다. 하지만 이 시간 복잡도를 알아야 어떤 알고리즘에 접근해야 할지 알 수 있다. 

보통은 다들 "컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다."로 알고 있을 것이다.

코딩 테스트 문제의 경우 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유 있게 지정한다. 따라서 코딩 테스트의 경우 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 된다.

예를 들어, 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안된다.

시간제한이 1초인 문제는 연산 횟수가 보통 3000만이 넘는 알고리즘은 사용하면 안 된다. 

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2ⁿ)	20 ~ 25
O(N³)	200 ~ 300
O(N²)	3,000 ~5,000
O(NlogN)	100만
O(N)	1,000 ~ 2,000만
O(logN)	10억

 

위의 표를 보면 최대 연산 횟수들의 간격이 크다. 이것은 우리가 구현하는 코드의 시간 복잡도가 문제에서 요구하는 성능을 만족하면 모두 통과할 수 있도록 한 것이다. 대충 "데이터가 1000만 개 정도면 O(N)을 사용해야 하는구나!!" 정도로 생각하자. 

 

그럼 이제 시간 복잡도를 계산해 봐야 어떤 알고리즘, 자료구조를 사용할지 감이 온다. 

여기서는 1. 문제 정의 -> 2. 연산 횟수 측정 -> 시간 복잡도 분석 순서로 해보겠다.

제일 쉬운 별 찍기-1 문제로 진행해 보자. (https://www.acmicpc.net/problem/2438)

문제는 숫자 N을 입력받으면 N번째 줄까지 별을 1개부터 N개까지 늘려가며 출력하는 것이다.

다음 출력의 예를 보면

*                       →  (1번) 연산 횟수
**                     →  (2번)
***                   →  (3번)
****                 →  (4번)
*****               →  (5번)
...
...
***** ... *        → (N-1)번
***** ... **       → (N)번

결국 연산 횟수 𝑓(𝑁) 은 아래의 등차수열의 공식처럼 나온다. 최고차항만 남기게 되면 빅오 표기법으로는 O(N²)이라고 할 수 있다.

그렇다면 갑자기 문득 생각이 들었다. 행렬의 덧셈은..? 

백준의 행렬 덧셈 문제를 예를 들어보자. (https://www.acmicpc.net/problem/2738)

입력은 N x M 크기의 두 행렬 A, B이고 출력은 두 행렬의 합 A+B다. 제약은 N과 M은 100보다 작거나 같다.

그렇다면 알고리즘 구조만 짜본다면 다음과 같을 것이다.

for(int i = 0; i < N; i++) {        // N번 반복
    for(int j = 0; j < M; j++) {    // M번 반복
        result[i][j] = A[i][j] + B[i][j]; 
    }
}

그러면 총 연산 횟수는 N x M번 즉, O(N x M)이다.

만약 정방행렬(정사각형 행렬)이라면? N = M = 100인 경우라면 연산 횟수가 10000번이다. 그러면 표에서는 O(N²)은 3000 ~ 5000번이라고 되어있는데? 엇? 그럼 초과돼서 안되는 거 아냐?라고 생각할 수 있다. 하지만 박경록 저자분께서 그랬다. 아까도 얘기했지만 간격이 큰 이유는 성능에 대해 충분히 여유를 두는 가용범위이기 때문에 대충 10000번 정도면 O(NlogN)은 100만이기도 하고, 실제로 덧셈 연산 10,000번은 충분히 빠르고 간단하기 때문에 O(N²)에 좀 더 가깝지 않을까란 생각이 든다. (이게 맞나..?🙄)

---

[출처] 코딩 테스트 합격자 되기 C++ 편 - 저자 박경록에서 인용