해당 글은 나동빈님의 '이것이 취업을 위한 코딩테스트다 with Python'을 학습하며 정리한 글 입니다.
수정일 2023.02.26
복잡도 (Complexity)
- 알고리즘 성능을 나타내는 척도이다.
- 시간복잡도 (Time Complexity)
- 알고리즘을 위해 필요한 연산의 횟수 - 공간복잡도 (Space Complexity)
- 알고리즘을 위해 필요한 메모리의 양 - 시간 복잡도와 공간 복잡도는 일종의 거래 관계(Trade-off)가 성립한다.
- 메모리를 더 많이 사용하여 시간을 비약적으로 줄이는 Memoization 기법이 있다.
시간 복잡도 (Time Complexity)
알고리즘에서 단순히
복잡도라고 표현하면 보통 시간 복잡도를 의미한다. 코딩 테스트 에서시간 제한이란 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는데 걸리는 시간을 의미한다.시간 제한안에 동작하는 프로그램을 작성하지 못하면Time Limit Exceeded메시지와 함께 오답처리 된다.
시간 복잡도는 Big-O 표기법을 사용한다.
# O(N) -> O(5)
array = [1, 2, 3, 4, 5] # N = 5
summary = 0
for x in array :
summary += x # 모든 데이터를 확인하여 합계 계산
# O(1)
a = 5
b = 7
a + b
# O(25)
array = [1, 2, 3, 4, 5] # N = 5
for i in array:
for j in array:
temp = i * j | 빅오 표기법 | 명칭 |
|---|---|
| O(1) | 상수 시간 |
| O(logN) | 로그시간 |
| O(N) | 선형시간 |
| O(NlogN) | 로그 선형시간 |
| O(N²) | 이차시간 |
| O(N³) | 삼차시간 |
| O(2ⁿ) | 지수시간 |
- 소스 코드 내부적으로 다른 함수를 호출한다면 모든 이중 반복문 시간 복잡도가 O(N²)가 아닐수 있다.
| N이 1000일 때의 연산 횟수 | |
|---|---|
| O(N) | 1000 |
| O(NlogN) | 10000 |
| O(N²) | 1000000 |
| O(N³) | 1000000000 |
- 일반적인 코딩테스트에서 상수를 고려해야 하는 경우는 적지만, 빅오 표기법이 항상 절대적인 것은 아니라는 점을 기억할 것.
- 코딩 테스트 환경에서 O(N3)를 넘어가면 문제 풀이에 사용하기 어렵다.
보통은 시간 복잡도에서의
연산은 프로그래밍 연산에서 지원하는 사칙 연산, 비교 연산 등과 같은 기본 연산을 의미한다.
시간 복잡도 분석은 문제 풀이의 핵심이다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있다.
시간 제한이 1초인 문제 예시
- N의 범위가 500인 경우 -> 시간 복잡도가 O(N³)인 알고리즘을 설계하면 풀 수 있음
- N의 범위가 2000인 경우 -> 시간 복잡도가 O(N²)인 알고리즘을 설계하면 풀 수 있음
공간 복잡도 (Space Complexity)
시간 복잡도를 표기했던 것처럼 빅오 표기법을 이용한다. 시간 복잡도에서 1초라는 절대적인 제한이 있었던 것 처럼 일반적으로 MB단위로 기준이 제시된다.
시간 제한 1초, 메모리 제한 128MB
코딩 테스트 문제는 대부분 리스트(배열)를 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 코딩 테스트에서는 보통 128-512MB 정도로 제한한다. 일반적으로 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미이다.
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000] : 16MB
시간과 메모리 측정
실질적으로 알고리즘의 소요시간을 확인해야 자신이 제대로 알고리즘을 작성하고 있는지 체크할 수 있다. 실제 프로그래밍 수행 시간을 측정하는 것은 알고리즘의 효율성을 측정하는 가장 기본적인 방법이다.
선택 정렬과 기본 정렬 라이브러리 수행 시간 비교
import Foundation
var arr:[Int] = []
for _ in 1...100 {
arr.append(Int.random(in: 1..<100))
}
let startTime = CFAbsoluteTimeGetCurrent() // 측정시작
for i in 0...arr.count - 1 {
var minIndex = i
for j in 1...arr.count - 1 {
if arr[minIndex] > arr[j] {
minIndex = j
arr.swapAt(minIndex, i)
}
}
}
let durationTime = CFAbsoluteTimeGetCurrent() - startTime // 측정 종료
print("선택정렬 경과 시간: \(durationTime)") // 선택정렬 경과 시간: 0.5592410564422607import Foundation
var arr:[Int] = []
for _ in 1...100 {
arr.append(Int.random(in: 1..<100))
}
let startTime = CFAbsoluteTimeGetCurrent() // 측정시작
arr.sort()
let durationTime = CFAbsoluteTimeGetCurrent() - startTime // 측정 종료
print("기본정렬 경과 시간: \(durationTime)") // 기본정렬 경과 시간: 0.0007879734039306641이처럼 자신이 설계한 알고리즘의 성능을 실제로 확인하기 위해서, 시간 측정 라이브러리를 사용해 보는 습관을 기르는 것이 좋다. 코딩 테스트에서 문제를 풀 때는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다. '소스코드가 복잡하게 생겼다'와는 다른 말로 사용된다.
