들어가며
컴퓨터는 1초에 대략 3~5억 개 정도의 연산을 처리할 수 있다. 예를 들어서 시간 제한이 1초인 문제가 있으면 이는 3~5억번의 연산 안에 답을 내고 종료하여 시간 초과가 아닌 코드를 짜라는 것을 알려주는 것이다. 밑에 함수 하나를 보고 생각해보자.
int func(int arr[], int n) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 5 == 0) {
cnt++;
}
}
return cnt;
}위의 함수에서 연산이 몇 번 필요할까?
cnt 변수를 선언하고 0을 넣는 과정에서 1번, for문의 i에 0을 대입할 때 1번, n번에 걸쳐 반복되는 일에서 i가 n보다 작은지 확인하고 작으면 i++ 과정을 하니까 연산 2번, if문으로 5로 나눈 나머지를 계산하고 그게 0인지 확인할 때 연산 2번, 나머지가 0일 경우에 cnt++ 과정을 하니까 1번, 마지막으로 cnt를 반환할 때 연산 1번을 한다.
=> 1 + 1 + n * (2 + 2 + 1) + 1 = 5n + 3
이 함수는 5n + 3번의 연산이 필요하다. n이 일정 수를 넘어가면 1초 안에 다 돌 수 없다는 것을 알 수 있을 것이다. 이 연산의 시간 복잡도를 빅오로 표기하면 O(n)이 된다.
시간 복잡도(Time Complexity)
시간 복잡도는 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미한다. 그리고 계산 복잡도를 표기하는 대표적인 방법이 빅오 표기법이다.
빅오 표기법(Big-O notation)
빅오 표기법은 알고리즘의 시간 복잡도를 나타내는 표기법을 의미한다. 빅오 표기법으로 시간 복잡도를 표현할 때는 최고차항만을 표기하고 계수는 무시한다. 만약, 5n^2 + 3n + 1번만큼 연산하는 함수가 있다면 이 함수의 시간 복잡도는 최고차항인 5n^2만을 고려한다. 그리고 계수를 무시하여 n^2만을 고려한다. 따라서 시간 복잡도를 빅오 표기법으로 표현하면 O(n^2)이 된다. 시간 복잡도를 빅오 표기법으로 표기할 때는 입력값에 따른 알고리즘의 실행 시간의 추이만을 고려한다. 이 추이에 따른 빅오 표기법의 종류는 다음과 같다.
- O(1): 입력값이 크더라도 실행 시간은 일정하다. 최고의 알고리즘이라고 할 수 있다. 해시 테이블의 조회 및 삽입이 이 시간 복잡도에 해당한다.
- O(log n): 로그는 매우 큰 입력값에도 크게 영향을 받지 않는다. 이진 검색이 이 시간 복잡도에 해당한다.
- O(n): 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례한다. 이러한 알고리즘을 선형 시간(Linear-Time) 알고리즘이라고 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이 시간 복잡도에 해당한다.
- O(n log n): 병합 정렬과 더불어 대부분의 효율 좋은 정렬 알고리즘이 이 시간 복잡도에 해당한다. 적어도 모든 수에 대해 한 번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘이라도 O(n log n)보다 빠를 수 없다. 만약 입력값이 최선인 경우에 비교를 건너뛰어 O(n)이 될 수 있다. 이는 팀소트(Timsort)가 해당한다.
- O(n^2): 버블 정렬과 같은 비효율적인 정렬 알고리즘이 이 시간 복잡도에 해당한다.
- O(2^n): 피보나치 수를 재귀로 계산하는 알고리즘이 이 시간 복잡도에 해당한다.
- O(n!): 각 도시를 방문하고 돌아오는 가장 짧은 경로를 찾는 외판원 문제(Travelling Salesman Problem, TSP)를 브루트 포스로 풀이할 때 이 시간 복잡도에 해당한다. 가장 느린 알고리즘이다.
아래의 표는 N의 크기에 따라 어떤 시간 복잡도로 해결해야 문제를 통과할 수 있는지에 대한 대략적인 지표이다.
| N의 크기 | 허용 시간복잡도 |
| N <= 11 | O(n!) |
| N <= 25 | O(2^n) |
| N <= 100 | O(n^4) |
| N <= 500 | O(n^3) |
| N <= 3,000 | O(n^2 log n) |
| N <= 5,000 | O(n^2) |
| N <= 1,000,000 | O(n log n) |
| N <= 10,000,000 | O(n) |
| OVER | O(log n), O(1) |
상한과 최악
빅오(O)는 상한(Upper Bound)를 의미한다. 이외에도 하한(Lower Bound)를 나타내는 빅오메가(Ω), 평균을 의미하는 빅세타가 있다. 상한으로만 표현하는 것이 혼동되지 않아 주로 상한으로만 표현한다.
상한을 최악의 경우와 혼동하는 것을 조심해야 한다. 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 '적당히' 표현하는 방법일 뿐이다. 최악의 경우나 평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이다.
공간 복잡도(Space Complexity)
공간 복잡도는 프로그램을 실행시킨 후 완료하는 데 필요한 공간의 양을 의미한다. 공간 복잡도로 문제가 생기는 경우는 거의 없다!
기억하면 좋을 것: 메모리 제한이 512MB일 때, int 변수를 약 1.2억개 정도를 선언할 수 있다. int를 4바이트로 계산하면 이 값이 나온다.
정수 자료형
정수 자료형에는 char(1 byte), short(2 byte), int(4 byte), long long(8 byte) 자료형이 있다. 주로 정수를 표현할 때 int나 long long 자료형을 사용한다.
실수 자료형
실수 자료형에는 float(4 byte), double(8 byte) 자료형이 있다. 실수를 저장하는 방식은 'IEEE-754 format'이라고 부른다.
실수 자료형의 성질은 다음과 같다.
- 실수의 저장과 연산 과정에서 반드시 오차가 발생한다. (float: 유효숫자 6자리, double: 유효숫자 15자리)
- double 자료형에 long long 범위의 정수를 함부로 저장하면 안된다. double 자료형은 유효숫자가 15자리인데 long long 자료형은 최대 19자리 까지이다. 따라서 double 자료형에 long long 범위의 정수를 담을 경우에 오차가 생길 수 있다.
- 실수를 비교할 때는 등호를 사용하면 안된다.