복잡도

코딩 테스트

복잡도

도담_dodam 2024. 11. 22. 00:50

1. 시간 복잡도

: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미

알고리즘을 위해 필요한 연산의 횟수를 알 수 있음.

빅오(Big-O) 표기법을 사용: 가장 빠르게 증가하는 항만을 고려하는 표기법

for문 1번: O(N)

a와 b에 값을 대입하는 연산: O(1)

일반적인 2중 반복문: O(N^2)

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 가장 중요

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

흔한 케이스는 아니지만 실제 코딩 테스트에서는 차수가 작은 항들을 완전히 무시하는 것도 곤란.

빅오 표기법이 항상 절대적인 것은 아니라는 것을 기억하자.

2. 공간 복잡도

: 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

알고리즘을 위해 필요한 메모리의 양을 알 수 있음.

빅오 표기법 사용: 공간 복잡도도 또한 O(NlogN), O(N^2) 등으로 표기

일반적으로 메모리 사용량 기준을 MB 단위로 제시

코딩 테스트 문제에서 보이는 ‘시간 제한 1초, 메모리 제한 128MB’와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위하여 명시하는 것.

코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문.

고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량

int a[1000]: 4KB
int a[1000000]: 4MB
int a[2000][2000]: 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB 정도로 제한, 즉 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계 필요

시간과 메모리 측정

파이썬에서는 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다.

실제 프로그램의 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법

수행 시간 측정 코드

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

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

선택 정렬을 사용할 때 최악의 경우 시간 복잡도가 O(N^2)이며, 파이썬의 기본 정렬 라이브러리는 최악의 경우 시간 복잡도 O(NlogN)을 보장하여 상대적으로 빠르다.

from random import randint
import time

# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
	array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수

# 선택 정렬 프로그램 성능 측정
start_time = time.time()

# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
	min_index = i # 가장 작은 원소의 인덱스
	for j in range(i+1, len(array)):
		if array[min_index] > array[j]:
			min_index = j
	array[i], array[min_index] = array[min_index], array[i] # 스와프

end_time = time.time() # 측정 종료
print("선택 정렬 성능 측정:", end_time - start_time) # 수행 시간 출력

# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
	array.append(randint(1, 100)) # 1 부터 100 사이의 랜덤한 정수

# 기본 정렬 라이브러리 성능 측정
start_time = time.time()

# 기본 정렬 라이브러리 사용
array.sort()

end_time = time.time()
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) # 수행 시간 출력

자신이 설계한 알고리즘의 성능을 실제로 확인하기 위해서, 시간 측정 라이브러리를 사용해 보는 습관을 기르는 것이 좋다.

동일한 기능을 수행하는 알고리즘이 2개(각각 A와 B) 있을 때

만약 A 알고리즘이 B보다 시간 복잡도가 더 높다면,

실행 시간 측면에서의 성능: A 알고리즘 < B 알고리즘

일반적으로 알고리즘 문제 풀이에서의 복잡도는 계산 복잡도를 의미

[출처] 나동빈, 『 이것이 취업을 위한 코딩 테스트다 with 파이썬 』, 한빛미디어(2020), p.46-53.