이것이취업을위한코딩테스트다 - Chapter 01 코딩테스트 개요 1. 복잡도 - 시간 복잡도

  주제

복잡도는 알고리즘의 성능을 나타내는 척도이며, 시간 복잡도에 대해 알아보자.

 

  내용

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지는 의미한다.공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

 

효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(trade-off)가 성립한다.메모리를 조금 더 많이 사요아는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.

시간 복잡도

알고리즘 문제를 풀 때 단순히 '복잡도'라고 하면 보통은 시간 복잡도를 의미한다.

코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서 해당 시간 안에 동작하는 프로그램을 작성해야 정답 판정을 받을 수 있으며, 프로그램을 비효율적으로 작성하여 시간 제한을 넘기면 '시간 초과'라는 메세지와 함께 오답으로 처리된다.

 

시간 복잡도 - 빅오 표기법

시간 복잡도를 표현할 때는 빅오 (Big-O) 표기법을 사용한다. 쉽게 정의하면 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 

 

a = 5
b = 7
print(a+b)

a와 b에 값을 대입하는 대입 연산과 출력 함수를 무시하고 보면, 이 소스코드의 연산 횟수는 1이다.

단순히 더하기 연산 한 번이 수행되기 떄문이다. 이는 상수 연산이므로 O(1)로 표현할 수 있다.

 

array = [3, 5, 1, 2, 4]

for i in array:
    for j in array:
            temp = i * j
            print(temp)

이 소스코드는 데이터의 개수(array 리스트 변수의 길이)가 N개일 때, O(N^2)의 시간 복잡도를 가진다. 2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문이다. N X N만큼 연산이 필요하다는 것을 알 수 있다.

모든 2중 반복문의 시간 복잡도가 O(N^2)은 아니며, 내부적으로 다른 함수를 호출한다면 내부 함수의 시간 복잡도까지 고려되어야 한다. 따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다는 점을 기억하자.

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요하다. 또한 흔한 케이스는 아니지만 이론적인 계산이 아닌, '실제 코딩 테스트'에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란한다. 연산 횟수가 3*N^2+5*N^2+1000000인 알고리즘이 있다고 가정하면, 상수의 영향이 크기 때문이다. 항상 절대적인 것은 아니라는 점을 기억하자.

 

일반적으로 코딩 테스트 환경에서는 O(N^3)을 넘어가면 문제 풀이에서 사용하기 어렵다. CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 통상 1초 이상의 시간이 소요된다. 이 때 N의 크기가 5000이 넘는다면 족히 10초 이상의 시간이 걸릴 수 있다. 특히 파이썬은 더욱 오래 걸리며, 코딩 테스트 문제에서 시간 제한은 1 ~5초가량이므로 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정을 받을 수 있다.

 

	N이 1000일 때의 연산 횟수
O(N)	1000
O(NlogN)	10000
O(N^2)	1000000
O(N^3)	1000000000

 

시간 복잡도 분석은 문제 풀이의 핵심이다. 실제로 알고리즘 대회 참가에 익숙한 사람들은 문제의 조건을 확인한 뒤에 사용할 수 있는 알고리즘을 좁혀 나가는 전략을 채택하기도 한다.

 

다음은 시간 제한이 1초인 문제에 대한 예시이다.

- N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 2000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 100000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 10000000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.