[Algorithm] 01. 알고리즘(Algorithm) 개념 및 평가 기준

 알고리즘

 

알고리즘이란 문제를 해결하기 위한 절차나 단계의 집합으로 완전탐색, BFS, DFS, 정렬 등이 자주 사용된다.

알고리즘 평가 기준에는 시간/공간/구현 복잡도가 있는데 기업 코딩 테스트에서는 시간 복잡도를 중요하게 생각한다.

 

 

 시간 복잡도

 

시간 복잡도는 실행 시간과 연관이 있다.

실행 시간은 프로그램이 시작되고 모든 코드를 실행하는데 걸리는 시간을 의미한다. 

 

실행 시간에 영향을 주는 요소는 다양하게 존재하지만, 코드 관점에서는 크게 두 가지로 볼 수 있다.

1. 처리해야 하는 코드의 개수
2. 한 줄의 코드를 처리하는데 걸리는 시간

 

💡  빅오(Big-O)

 

입력 크기(n)에 따라 알고리즘이 실행되는데 필요한 시간 복잡도를 빅오(Big-O)로 표현할 수 있다.

 

빅오(Big-O)는 계산 결과를 단순화 하기 위해서 최고차항을 제외한 나머지 항들은 모두 무시한다.

• $T(n) = 2n^{3} + 4n^{2} + 3n + 1 = O(n^{3})$
• $T(n) = 17n^{4} + 4n^{3} + 3n + 8 = O(n^{4})$
• $T(n) = 16n + logn = O(n)$
• $T(n) = 2^{n} + 4n^{2} + 3n! + 1 = O(n!)$

※  $n! > 2^n > n^3 > n^2 > nlogn > n > logn > 1$

 

 

💡  평균 시간 복잡도

 

같은 코드라도 입력값에 따라 다르게 동작하므로 실행 시간이 다르게 나올 수 있다.

 

if (condition) {
    for (int i = 0; i < n; i++) {
    }
    
} else {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
        }
    }
}

 

if 문이 실행되면 $O(n)$ 이므로 Best case인 경우이고, else 문이 실행되면 $O(n^{2}) $ 이므로 Worst case인 경우이다.

시간 복잡도를 묻는 질문에는 Worst case인 경우로 대답해야 하므로 위 코드의 시간 복잡도는 $O(n^{2}) $ 이다.

 

시간 복잡도가 $O(n)$ 인 알고리즘은 구현이 어렵고 생각해내기 어렵지만 시간 초과가 발생할 가능성이 낮고,

시간 복잡도가 $O(n^{2}) $ 인 알고리즘은 구현이 쉽고 직관적이지만 시간 초과가 발생할 가능성이 높다.

 

많은 기업 코딩테스트의 실행 시간은 1~10초이고, 1초 안에 처리 가능한 연산의 개수는 약 $10^{8}$~ $10^{9}$ 개이다.

따라서 $n$ 의 최대값을 시간 복잡도에 대입한 숫자가 $10^{8}$ 이상이면 시간 초과가 발생할 가능성이 높다.