알고리즘 코딩 테스트 개요 및 주요 개념

시간 복잡도

알고리즘의 성능을 나타내는 척도
특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 우수

빅오 표기법 (Big-O Notation)

가장 빠르게 증가하는 항만 고려하는 표기법
함수의 상한을 나타낸다.
$3N^3 + 5N^2 + 1,000,000$인 알고리즘이 있다고 가정했을 때, $N$이 증가함에 따라 $3N^3$을 제외한 다른 항의 영향력은 작아진다.
Big-O 표기법에서는 차수가 가장 큰 항에서 계수를 제외하여 $O(N^3)$으로 표현한다.

시간 복잡도	의미
$O(1)$	상수 시간 (constant time)	좋음
$O(logN)$	로그 시간 (log time)
$O(N)$	선형 시간 (linear time)
$O(NlogN)$	로그 선형 시간 (log-linear time)
$O(N^2)$	이차 시간 (quadratic time)
$O(N^3)$	삼차 시간 (cubic time)
$O(2^N)$	지수 시간 (exponential time)	나쁨

시간복잡도 예시

$O(N)$

let arr = [1, 2, 3, 4, 5];
let sum = 0;

for (let i = 0; i < arr.length; i++) {
	sum += arr[i];
}

console.log(sum);

수행 시간은 데이터의 개수 N에 비례할 것임을 예측 가능

$O(N^2)$

let arr = [1, 2, 3, 4, 5];

for (let i = 0; i < arr.length; i++) {
	for (let j = 0; j < arr.length; j++) {
		let temp = arr[i] * arr[j];
		console.log(temp);
	}
}