코딩 테스트에서 좋은 결과를 받으려면 단순히 코드만 잘 작성하는 것으로 충분할까요? 내가 짠 코드가 얼마나 효율적인지 면접관에게 잘 설명하는 것도 코딩 인터뷰에서 매우 중요하지만 간과하기 쉬운 부분입니다.
알고리즘의 복잡도
알고리즘을 평가하는 척도로 사용되는 복잡도(complexity)라는 개념에 대해서 먼저 짚고 넘어가겠습니다.
먼저, 알고리즘의 복잡도는 코드의 길이와는 전혀 무방한 개념으로서 코드가 길어도 복잡도는 낮을 수가 있고 코드가 짧아도 복잡도는 높을 수가 있습니다. 알고리즘의에서 복잡도의 개념은 오히려 코드의 길이 보다는 코드를 실행했을 때의 성능과 효율, 그리고 확장성(scalability)에 더욱 관계가 깊습니다. 알고리즘의 복잡도를 분석할 때는 시간 측면에서는 얼마나 실행 속도가 빠른지를 보기도 하고, 공간 측면에서 얼마나 많은 메모리가 쓰는지를 보기도 합니다. 전자를 시간 복잡도(time complexity)라고 하고, 후자를 공간 복잡도(space complexity)라고 합니다.
일반적으로 처리할 데이터의 양이 많아질수록 대부분의 경우 알고리즘의 성능은 떨어지기 마련입니다. 여기서 중요한 부분은 입력 데이터 증가량 대비 얼만큼의 실행 시간과 메모리 소모량은 늘어나는 것일텐데요. 우수한 알고리즘 일수록 처리할 데이터의 양이 증가함에 따라 성능 저하가 적게 나타나는 경향을 보입니다.
알고리즘의 성능을 비교할 때 일반적으로 입력 데이터의 크기가 작을 때는 어떤 알고리즘이 우수한지 티가 잘 안 나지만, 입력 데이터의 커지면 커질 수록 시간 복잡도가 높은 알고리즘은 오래 걸리고 공간 복잡도가 높은 알고리즘은 메모리를 많이 쓰게 됩니다.
코딩 테스트나 코딩 인터뷰에서는 아무래도 복잡도가 낮은 코드를 작성하는 지원자에게 좋은 점수를 줄 수 밖에 없습니다. 그리고 본인이 작성 코드의 복잡도를 정확하게 분석할 수 있는 지원자라면 더욱 신뢰가 갈 것입니다.
Big O
알고리즘 공부를 해보셨다면 Big O라는 것을 한 번 정도는 들어보셨을 것입니다. Big O는 알고리즘의 성능을 객관적으로 표현하기 위해서 코딩 테스트에서 널리 사용되고 있는 방법인데요. 최악의 조건에서 주어진 알고리즘이 입력 데이터 크기 대비 실행 시간이나 메모리 사용량이 얼마나 증가하는지를 수식으로 표현합니다.
Big O를 사용해서 복잡도를 분석할 때는 거시적으로 접근하면서 수식을 단순화시키는데요.
예를 들어, 어떤 알고리즘에 크기가 n인 입력이 데이터가 주어졌을 때, 실행 시간이 3n^2 + 5n + 100으로 계산된다면, Big O 계산법으로 O(n^2)이 됩니다.
즉, Big O 표현식에서는 수학적으로 가장 영향력이 큰 항만 고려되며, 그 항 앞에 붙은 상수도 의미가 없어지게 됩니다.
이 것은 어디까지나 이론적인 부분이고 실제 코딩 테스트에서 이렇게 복잡한 다항식의 수식을 Big O로 전환할 일은 거의 없습니다. 따라서 본 가이드에서는 코딩 테스트에서 실제로 자주 접할 수 있는 알고리즘의 복잡도를 한 번 정리해보려고 합니다.
O(1): Constant
O(1) 복잡도는 입력 데이터의 크기와 상관없이 항상 동일한 성능을 보여주는 알고리즘 성능의 끝판왕을 나타냅니다.
입력 데이터가 아무리 커지더라도, 시간 복잡도가 O(1)인 알고리즘은 실행 시간이 느려지지 않고, 공간 복잡도가 O(1)인 알고리즘은 고정된 크기의 메모리만 사용합니다.
가장 대표적인 예로 해시 테이블(Hash Table)이라는 자료구조를 들 수가 있는데요.
해시 테이블에는 데이터를 많이 저장하든 적게 저장하든 데이터를 찾는데 걸리는 시간은 항상 동일한 것으로 알려져있습니다.
다시 말해, 일반적으로 해시 테이블의 검색 알고리즘은 O(1)의 시간 복잡도를 보입니다.
하지만 실제 코딩 테스트에서 특히 시간 측면에서 O(1)의 복잡도의 답안을 낼 수 있는 문제를 접할 가능성은 (특히 시간 복잡도 측면에서) 그리 높지가 않습니다.
O(n): Linear
코딩 테스트에서 가장 흔하게 접할 수 있는 알고리즘의 복잡도는 단연 O(n)일 것입니다.
O(n) 복잡도의 알고리즘은 입력 데이터의 크기가 늘어나는 만큼 실행 시간 또는 메모리 성능이 저하되는 특징을 보입니다.
코딩 문제를 풀다보면 for나 while 반목문을 이용해서 주어진 데이터를 순회해야하는 경우가 비일비재 한데요.
이렇게 배열의 모든 원소나 링크드 리스트(linked list)의 모든 노드에 접근해서 무엇가를 처리하는 코드를 작성하고 있다면 해당 알고리즘은 시간 복잡도는 최소 O(n)일 것입니다. (“최소”라고 한 이유는 각 원소나 노드를 대상으로 어떤 작업을 처리하느냐에 따라서 복잡도가 얼마든지 더 올라갈 수 있기 때문입니다.)
반목문을 하나만 쓰든 여러 개를 쓰든 중첩만 하지 않는다면 시간 복잡도는 O(n)의 범주에서 벗어나지 않는데요.
Big O 계산 방법에 따르면 O(n)과 O(2n), O(100n)은 유의미한 차이를 내지않기 때문입니다.
O(log n): Logarithmic
O(n) 보다 입력 데이터의 크기의 영향을 적게 받는 O(log n)도 코딩 테스트에서 자주 쓰이는 대표적인 복잡도입니다.
O(log n) 복잡도의 알고리즘은 입력 데이터의 크기가 커지더라도 실행 시간이나 메모리 사용량이 크게 늘어나지 않습니다.
좀 더 수학적으로 얘기하면 전형적인 로그 함수의 그래프처럼 x축의 입력 데이터가 커지면 커질수록, y축의 시간/공간 소모량은 더욱 완만하게 증가합니다.
가장 유명한 O(log n) 알고리즘으로 이분 탐색(binary search)을 들 수 있는데요.
이분 탐색에서는 검색 범위가 계속해서 절반으로 줄어들기 때문에 모든 원소에 확인해야하는 선형 탐색(linear-search) 대비 데이터의 크기의 증가에 따른 성능 저하가 적습니다.
이진 트리(binary tree)나 힙(heap)을 다루는 코딩 문제에서도 O(log n) 알고리즘을 어렵지 않게 만날 수 있습니다.
O(n*log n): Super linear
O(n)과 O(log n)를 묘하게 섞어 놓은듯한 O(n * log n)도 코딩 테스트에서 흔하게 만날 수 복잡도입니다.
O(n * log n) 복잡도는 O(n) 복잡도보다 O(log n) 만큼 더 많이 입력 데이터가 크기에 영향을 받습니다.
입력 데이터를 대상으로 정렬을 필요로하는 대부분의 알고리즘이 O(n * log n)의 복잡도를 보여줍니다.
왜냐하면 대부분의 프로그래밍 언어에서 제공하는 정렬 알고리즘의 복잡도가 O(n * log n) 수준이기 때문입니다.
O(n^2): Quadratic, O(n^3): Cubic
지금까지 다룬 복잡도에 비해 성능이 많이 떨어지긴 하지만 O(n^2) 또는 O(n^3)도 코딩 테스트에서 심심치 않게 볼 수 있는 복잡도 입니다.
O(n^2) 복잡도는 입력 데이터의 크기가 늘어난 2배 만큼, O(n^3) 복잡도는 3배 만큼 실행 시간이 늘어나거나 메모리 소모량이 증가합니다.
예를 들어, 시간 복잡도가 O(n^2)인 알고리즘은 입력 데이터의 크기가 5배로 늘어나면 실행 시간은 그의 제곱인 25배로 늘어납니다.
만약 코딩 테스트에서 반목문 안에서 또 다른 반복문을 사용하고 계시다면 O(n^2) 복잡도의 알고리즘을 작성하고 있으실 확률이 높습니다.
마찬가지로 반복문을 3단계로 중첩해서 사용하고 있다면 O(n^3) 복잡도의 알고리즘이 되겠지요?
사실 이 정도까지가 실제 코딩 인터뷰에서 사용 가능한 복잡도라고 보시면 되겠습니다. 또한 온라인 코딩 체점 플랫폼에서 이 것보다 복잡도가 높은 답안을 제출한다면 timeout이 발생할 확률이 매우 높을 것입니다.
O(n^k): Polynomial
이제부터 소개해드릴 복잡도는 효율이 너무 떨어져서 대부분의 코딩 테스트에서 합격 기준에 미달할 가능성이 높을텐데요. 그래도 알아두셔야 피할 수 있으니 간단하게 살펴보도록 하겠습니다.
이전 섹션에서 다룬 O(n^2), O(n^3)와 같이 입력 데이터의 크기의 몇배로 시간/공간 소모량이 커지는 알고리즘을 O(n^k)로 분류하기도 하는데요.
여기서 k 값이 3보다 커지게되면 입력 데이터의 크기에 너무 큰 영향을 받기 때문에 좋은 알고리즘이라고 보기 어려울 것입니다.
O(k^n): Exponential, O(n!): Factorial
O(k^n) 복잡도는 입력 데이터의 크기가 증가하면 지수 함수의 그래프의 형태로 성능이 기하급수적으로 떨어집니다.
O(n!) 복잡도는 입력 데이터의 크기가 증가하면 팩토리얼 함수의 그래프의 형태로 성능이 폭발적으로 저하됩니다.
이 두 복잡도 모두 입력 데이터의 크기가 살짝만 증가해도 엄청난 연산량 또는 메모리를 필요로 하기 때문에 실제 제품에서는 쓸 수 없는 알고리즘이 대부분입니다. 제 아무리 컴퓨터의 성능이 좋아도 이러한 복잡도의 알고리즘을 돌리기에는 무리일 것입니다.
복잡도 서열
지금까지 코딩 테스트에서 볼 수 있는 알고리즘의 다양한 복잡도를 살펴보았는데요. 이 것들을 성능/효율이 좋은 순으로 나열하면 다음과 같이 됩니다.
O(1) > O(log n) > O(n) > O(n * log n) > O(n^2) > O(n^3) > O(n^k) > O(k^n) > O(n!)
코딩 테스트에 임할 때 이 복잡도 서열을 염두해 두고 주어진 문제에 접근하시면 좀 더 면접관이 만족할 만한 답안 코드를 작성하는데 도움이 되실 겁니다.
시간과 공간의 균형
모든 코딩 문제가 그런 것은 아니지만 공간 복잡도를 조금 희생하면 시간 복잡도 측면에서 훨씬 나은 알고리즘을 얻을 수 있는 경우가 많습니다. 따라서 본인의 코드의 실행 속도가 너무 느리다면, 메모리를 좀 더 사용해서 실행 시간을 단축할 수 있는 방법이 없는지 생각해보면 좋습니다.
당연히 메모리를 적게 먹으면서 빠르게 실행되는데 알고리즘이 이상적이겠지만, 실전에서는 이 두 마리 토끼를 동시에 잡는 것이 쉽지 않을 수 있습니다. 주어진 문제에서 알고리즘의 속도와 메모리 사용량 중 무엇이 중요한지에 따라 답안 코드를 최적화하는 것이 좀 더 현실적일 것입니다.