[이것이 코딩테스트다] 1. 복잡도(Complexity)

이것이 취업을 위한 코딩테스트다

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

 

1. 복잡도(Complexity)

복잡도 : 알고리즘의 성능을 나타내는 척도이며, 시간복잡도와 공간복잡도로 나눌 수 있다.

• 시간복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 시간이 얼마나 걸리는가. 즉, 그 알고리즘을 수행하는 데 걸리는 시간
• 공간복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘이 얼마의 메모리를 차지하는가. 즉, 그 알고리즘을 수행하는 데 필요하는 메모리
• 효율적인 알고리즘 구축에는 시간복잡도와 공간복잡도 간의 일종의 거래관계가 존재한다.
  • 알고리즘의 소요시간을 단축시키는 대신에, 메모리를 더 많이 잡아먹는다던가
  • 알고리즘의 소요 메모리 공간을 단축시키는 대신에, 소요 시간을 늘린다던가..
  • 메모이제이션(Memoization) : 메모리를 더 많이 사용해서 소요 시간을 비약적으로 줄이는 방법

 

2. 시간복잡도(Time Complexity)

• 일반적으로 복잡도라 함은, 시간복잡도를 의미한다.
• 빅오(Big-O) 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법으로, 시간복잡도를 표현할 때 사용한다.
• 시간복잡도  표(위쪽에 있을수록 빠름)
  •  

    빅오 표기법	명칭
    O(1)	상수 시간
    O(logN)	로그 시간
    O(N)	선형 시간
    O(NlogN)	로그 선형 시간
    O(N2)	이차 시간
    O(N3)	삼차 시간
    O(2n)	지수 시간

• 차수가 작은 항들을 완전히 무시하는 것도 좋은 것은 아니다. 예를 들면 연산 횟수가 3N³ + 5N²1000000 이다. 빅오표기법으로는 가장 큰 차수로 계산하여 O(N³)으로 표기되지만 실제로 N이 작으면 상수(1000000)의 영향이 크기 때문이다.

 

예시 1. 아래는 5개의 데이터를 받아 더하는 소스코드이다. 이 때 연산 횟수는 5개가 아니라 N개의 데이터를 받는다면 N개의 수에 따라 달라진 다는 것을 알 수 있다. 더하는 로직말고, summary 변수 선언과 결과 출력하는 부분이 있다. 하지만, N개가 상대적으로 많아진다면 무시할 수 있을 정도로 존재감이 없어진다. 따라서 본 소스코드에서 시간복잡도에 가장 영향력이 큰 부분은 N에 비례하는 반복문이므로, 시간복잡도를 O(N) 으로 표기한다.

#Python

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

# 배열 속의 데이터를 연산
for x in array:
	summary += x
    
# 덧셈 결과 출력
print(summary)

 

예시 2. 아래의 소스코드 시간복잡도는 O(1)이다. 단순하게 덧셈 연산이 한 번만 수행되는 상수 연산이기 때문이다.

#Python

num1 = 1
num2 = 2

print(num1 + num2)

 

예시 3. 아래의 소스코드 시간복잡도는 O(N²)이다.

#Python

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

for x in array:
	for y in array:
    	temp = x*y
        print(temp)

 

 

3. 공간복잡도

• 시간복잡도와 마찬가지로 공간복잡도에서도 빅오 표기법을 사용한다.
• 코딩테스트에서 복잡도 제한을 둘 때 시간복잡도에서는 초(Second) 단위로 기준이 되었지만, 공간복잡도에서는 MB단위로 제시된다.
• int 자료형 기준으로 리스트 크기에 따른 메모리 사용량은 일반적으로 아래와 같다.
  • int a[1000] : 4KB
  • int a[1000000] : 4MB
  • int a[2000][2000] : 16MB

4. 시간 측정 방법

여러 알고리즘을 설계한 후에, 시간 측정을 이용하여 더 좋은 알고리즘을 선택하는 것이 좋다.

시간 측정 방법은 아래와 같으며, 필자는 Java언어를 주로 사용하기에 Java 시간 측정 방법도 추가하였다.

 

Python

#python

import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

 

Java

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    
	    long start = System.currentTimeMillis();
	    
	    int a = 1;
	    int b = 2;
	    
	    System.out.println("연산 결과 : " + (a+b));
	    
	    long end = System.currentTimeMillis();
	    
	    System.out.println("실행시간 : " + (end - start));
	    System.out.println("초 단위 실행시간 : " + (end - start)/1000.0);
	    System.out.println("분 단위 실행시간 : " + (end - start)/1000.0/60.0);
	}
}