1. 복잡도

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 간단히 2가지로 나뉜다.

• 시간 복잡도: 알고리즘을 동작하는 데에 필요한 연산의 횟수
• 공간 복잡도: 알고리즘의 동작에 필요한 메모리의 크기

1.1 시간 복잡도

출처:제로베이스

코딩 테스트를 처음 접하게 되면 가장 당황하게 되는 것 중 하나가 'Time Limit Exceeded'로 시간 초과가 나며 오답처리 되는 경우다. 분명히 연습할 때 파이참이나 VS코드 등으로 연습할 때에는 답이 분명히 나왔는데 여러 사이트에서 실제 코딩 테스트 시험을 보게 되면 만나게 되는 오답 처리가 당황스럽다. 내가 작성한 코드의 연산 시행 횟수가 출제자가 의도한 풀이 시간을 넘겼기 때문이다. 이 때 빅오 표기법을 계산할 수 있다면 좀 더 수월하게 코드의 방향성을 구현할 수 있을 것이다.
시간 복잡도를 이야기 할 때 가장 많이 사용 되는 것은 위의 그림과 같이 빅오 표기법을 사용한다. 표기법은 표의 왼쪽으로 나타내고 오른쪽 표처럼 어떤 시간이 소요가 되는지 나타낸다.
표기법에서는 가장 높의 차수의 항만을 표기한다. 우리는 수학 시간에 2차, 3차 방정식을 배웠을 것이다. 'aX^3 + bX^2 + cX + d = 0'에서 a, b, c는 계수이고 d는 상수 그리고 최고 차항의 차수가 X^3이므로 3차 방정식으로 표기하는 것과 같이, 알고리즘의 연산 횟수를 고려할 때 위의 3차 방정식을 빅오 표기법에선 O(N^3) 삼차 시간이라고 한다. 앞의 계수 a와 상수항은 통상적으로 무시된다. 하지만 그 상수의 수가 너무 높은 경우에는 고려를 해야 하는 경우도 있다.

• O(1)은 상수 시간으로 가장 빠르게 동작되며 한 번의 연산을 한다. 예로 리스트에서 가장 뒤에 배열된 숫자 하나를 꺼내는 것이다.(예, list.pop()) 스텍이나 큐 자료구조에서 사용 된다.
• O(N)은 선형 시간으로 크기에 비례하여 연산 횟수가 증가한다. 예로 for 반복문을 N회 반복하는 것과 같다.
• O(N^2)은 간단하게 2중 반복문에서 데이터의 개수가 N개라면 N^2으로 나타낼 수 있다. 3중 반복문이라면 N^3이다.
• O(NlogN)은 로그 선형 시간으로 이진 탐색 때 사용되는 표기법이다.

파이썬에서는 통상적으로 1,000만회를 넘어가면 시간 초과가 발생하여 오답을 받을 수가 있다. 문제도 풀이도 힘든데 이것까지 알아야하니 너무 어렵다고 느껴질 수 있지만 이것은 반대로 이야기하면 출제자의 의도를 파악할 수 있는 힌트가 되며 풀이 방법까지 제시해주기도 한다. 예로 N으로 주어지는 데이터의 수가 1만개라면 2중 for 반복문으로는 풀면 안된다고 간접적으로 이야기 하는 것과 같다. 그래서 문제의 조건을 잘 보고 빅오 표기법으로 계산을 해보며 출제자의 의도를 파악하려는 노력도 같이 해보도록 하자.
실제로 1만을 2중 반복문을 통해 연산이 걸리는 시간을 아래와 같이 측정해 보았다.

import time
start_time = time.time()# <- 측정 시작 지점
n = 10000
sumN = 0
for i in range(n):
    for j in range(n):
        sumN += i * j
end_time = time.time()# <- 측정 끝 지점
print('time: {}'.format(end_time - start_time))#끝나는 시간에서 시작 시간을 빼서 측정한 전체 시간을 출력한다.
출력:
time: 13.043872356414795

대략 1억회의 연산을 하는데 걸리는 시간은 13초가 나온 것을 볼 수 있다. 이렇게 time()함수를 이용해서 자신의 코드가 실행되기 위한 시간이 얼마나 걸리는지 측정해가며 1초(통상적으로 아무런 시간 제시가 없다면 1초가 디폴트다)가 넘어간다면 다른 풀이 방법도 생각해보자. 걸리는 시간은 본인 컴퓨터의 하드웨어의 성능에 좌우되기에 너무 작은 단위의 시간까지는 신경 쓸필요는 없겠지만, 문제를 풀며 지금 적용한 알고리즘으로 시간 복잡도가 얼마나 걸리는지 유추해보고 연습해 볼 수 있는 좋은 방법이다.

1.2 공간 복잡도

코딩 테스트에서 복잡도라 하면 시간 복잡도를 이야기 하는 것과 같다. 하지만 시간 복잡도와 공간 복잡도는 'trade-off'의 관계로 공간 복잡도도 염두해 두어야 한다. 트레이드오프 관계는 시간 혹은 공간 가운데 어느 한편을 늘리면 다른 한편은 줄어드는 것을 말하는데, 아무리 시간 복잡도를 낮게 잡는다 하더라도 공간 복잡도 즉, 1만 * 1만의 2차원 배열을 만들어 진행하게 되어 시간복잡도와 마찬가지로 1,000만의 데이터 크기가 넘어가게 되어 현재 적용하는 알고리즘의 방법을 달리해야 할 것이다. 보통 메모리의 한계는 128~512MB로 제한하는데, 이는 1,000만을 넘어가지 않도록 알고리즘을 설계해야 한다는 이야기다.