실제로 알고리즘 문제를 풀다보면 O(n), O(n^2) 뿐만 아니라 다양한 시간 복잡도가 나옴
O(v+e), O(nlogn), O(logn) 등등
지금은 이정도만 알아도 문제 푸는데에는 지장 없음
나중에 알고리즘 수업 때 배우니 그때 제대로 배우면 됨
// 1번 코드 O(1)
// n이 아무리 커져도 연산의 횟수는 변하지 않음 -> O(1)
// 실제론 =, +, *, / 로 총 4번의 연산이지만, 시간 복잡도에선 1로 취급
int sum = (n+1) * n / 2
-------------------------------------
// 2번 코드 O(n)
// n번 반복하므로 시간 복잡도는 O(n)
// n이 10이면 10번 반복, 1000이면 1000번 반복
int sum = 0;
for(int i = 0; i < n; i++){
sum += array[i];
}
-------------------------------------
// 3번 코드 O(n^2)
// n번 반복하는 반복문 안에 n번 반복하는 반복문이 또 있으니 O(n^2)
// n이 10이면 100번 반복, 1000이면 1,000,000번 반복
int sum = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
sum += array[i][j];
}
}
O(n^2)부터n이 커질 수록반복 횟수는급격히 증가함
대부분 알고리즘은 O(n^2)을 마지노선으로 잡음
특수한 경우를 제외하고, 그 이상 O(n^3), O(n^4)은 좋은 알고리즘으로 보기 힘듦
1-1. 시간 초과 확인하기
일반적으로1초의 기준은1억번 연산으로 기준을 잡음 (알고리즘 문제 풀 때)
문제 조건이 시간 제한 1초이고, 입력이 총 N(최대 100,000)개 들어온다고 가정
내가 작성한 알고리즘이 O(N)이라면 10만번 연산하므로 1초 내에 통과 가능
O(N^2)이라면, 100,000 * 100,000 으로 총 10,000,000,000(100억)번 연산하므로 1초 내에 통과 불가
2. 공간 복잡도 계산
시간 복잡도와 비슷
N개의 배열을 저장하면 O(N), N^2개의 배열을 저장하면 O(N^2)
2-1. 메모리 초과 확인하기
자바 기준으로 int는 4byte, char는 2byte, String은 2byte (한 문자 당), Boolean은 1byte
원소가 100,000개인 Int 배열을 선언하면 100,000 * 4 byte => 400,000 byte => 400 KB => 0.4 MB
문제의 메모리 제한이 128MB라면, 약 32,000,000개의 원소를 갖는 Int 배열을 선언할 수 있음
알고리즘 문제 접근 방법
1. 문제 조건 확인
문제의 시간 제한, 메모리 제한, 입력의 개수, 숫자 범위 등을 확인
2. 일단 그냥 푸는 방법 생각하기
문제 조건에 맞게 풀 수 있는 방법이 떠오르면 바로 풀면 되지만, 바로 적합한 알고리즘을 떠올리기는 힘듦
문제 조건 (시간 제한, 메모리 제한, 숫자 범위)를 고려하지 않고무식하게라도 답을 낼 수 있는 방법을 먼저 생각하기
문제 조건에 부합하지 않더라도, 일단 푸는게 먼저
일단 답이 나오는 코드를 작성해두고, 문제 조건에 맞춰서 하나씩 고쳐 나가면 됨
3. 문제 조건 분석
내가 작성한 코드에서 문제의 조건에 어긋나는 부분을 찾기
시간이 오래 걸리는 지
메모리를 너무 많이 쓰고 있는 지
숫자 범위를 작게 받고 있는 건 아닌지
등등 문제에 따라 다양한 조건이 있을 수 있음
항상 최악의 경우를 생각하기 ★
1번에서 확인한 문제 조건 중최악의 경우를 생각 (항상 최악의 경우를 생각하는 습관 필요 ! )
