[코딩테스트] 코드를 평가하는 방식, 시간 복잡도

코드를 평가하는 방식, 시간 복잡도

 

이번 시간에는 '배열 연산의 시간 복잡도와 자주 사용하는 기능'에 대해 알아보기 전에 시간 복잡도(Time Complexity)의 개념에 대해 먼저 알아보려고 합니다. 저자님의 스터디 가이드를 참고했습니다.

 

코딩 테스트 평가 방식

---

코딩 테스트에서 코드를 평가하는 방식은 크게 두 가지입니다.

1. 내가 작성한 코드의 결괏값이 테스트 케이스의 결괏값과 일치하는지 (정확성)

2. 문제에서 요구하는 알고리즘 "성능"을 만족하는지 (효율성)

 

코딩 테스트의 문제들은 각각 '가장 효율적으로 해결하는 알고리즘'이 있다고 하는데요.

이때 이 알고리즘의 성능을 측정하는 데 쓰이는 것이 시간복잡도입니다.

시간복잡도는 입력값과 연산 횟수의 상관관계에 따라 성능을 측정하는 것입니다.

 

예를 들어 1차원 배열을 순회한다고 가정해 보겠습니다.

배열의 크기(입력값)가 N이라면 연산 횟수도 N일 것이고, 시간복잡도도 N입니다.

그러나 1차원 배열에서 특정 값을 찾는 경우를 생각해 보면 시간복잡도는 최선, 보통, 최악의 경우로 나눠집니다.

최선일 경우의 시간복잡도는 1이고, 보통의 경우는 N/2, 최악의 경우는 N입니다.

우리는 모든 경우의 수, 최악의 경우에서도 알고리즘이 문제를 처리하도록 해야 하기 때문에 시간 복잡도는 최악의 경우를 가정하는 것이 일반적입니다.

 

시간 복잡도

---

시간 복잡도를 표현할 때는 보통 빅오 표기법(Big-O)을 많이 사용하는데요.

빅오 표기법(Big-O)은 어떤 함수의 증가하는 추세를 표현하는 방법인 점근적 상한 표기법을 사용하는 방법입니다.

* 점근적 상한: 아무리 나빠도 이것보다 나쁘진 않다는 의미

정확한 연산 횟수를 구하는 것이 아니라, 성능의 추이를 파악하기 위한 것이기 때문입니다.

연산 횟수 f(x)가 다항함수로만 구성되어 있다면 최고차항만 남기고 계수는 지워줍니다.
예를 들어 f(x) = 2x^2 + 3x + 5라면 시간복잡도는 O(x^2)으로 표기.

연산 횟수 f(x)가 다항함수와 로그함수로 구성되어 있다면 증가폭이 더 큰 다항함수만 남기고 지워줍니다.
예를 들어 f(x) = x + logx 이면 시간 복잡도는 O(x)로 표기

연산 횟수 f(x)가 지수함수와 다항함수로 구성되어 있다면, 증가폭이 더 큰 지수함수만 남기고 지워줍니다.
예를 들어 f(x) = 2^x + 10x^5 + 5x^2 이면 시간 복잡도는 O(2^x)로 표기

연산 횟수 f(x) = x^2 + x! - 2^x이면 시간 복잡도는 O(x!)

아래는 Big-O 표기에 따른 알고리즘의 성능을 나타낸 차트입니다.

---

코딩 테스트에서 시간 복잡도를 활용하는 방법에 대해서도 알아보겠습니다.

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번인데요.

코딩 테스트에서는 여유 있게 연산 횟수를 1초에 1000만~3000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다.

아래는 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수를 정리한 표입니다.

초당 시간복잡도

예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3000만이 넘는 알고리즘은 사용하면 안 됩니다. 지금까지 시간복잡도의 개념과 활용법에 대해서 알아보았는데요.

이제 실제 문제를 풀이하고 작성한 코드의 시간 복잡도를 구해보도록 하겠습니다.

참고: 점근적 표기법을 실제 코딩테스트에 적용하기

 

문제풀이

---

문제 1.

def solution(money):
    return [money // 5500, money % 5500]

money의 값에 상관없이 바로 구할 수 있으므로, 시간 복잡도는 O(1)

---

문제 2.

def solution(array, n):
    answer = 0
    for i in range(len(array)):
        if array[i] == n:
            answer += 1
    return answer
    
#더 간단한 풀이
def solution(array, n):
  	return array.count(n)

배열 array의 길이만큼 순회하므로, 시간복잡도는 O(n)

---

문제 3.

def solution(n):
    factorial = 1
    i = 1
    while True:
        factorial *= i
        if factorial > n:
            answer = i - 1
            break
        i += 1
    return answer

코드를 보면 결국 1부터 1씩 큰 숫자를 곱하고 있는데요. 입력값 제한사항에 따라 i의 크기는 최대 10입니다.

입력값이 커진다고 해서 연산 횟수가 커지지 않습니다.

시간복잡도는 O(1)입니다.

아래 댓글 내용도 참고가 되어서 첨부합니다.

이상으로 시간복잡도와 활용법에 대해서 알아보았습니다.

다음에는 배열 연산의 시간 복잡도와 자주 사용하는 기능에 대해 알아보겠습니다.