『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
💡 알고리즘 선택의 기준이 되는 시간 복잡도
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같다.
다음처럼 0~99 사이의 무작위 값을 찾아 출력하는 코드가 있을 때,
public class timeComplexityExample1 {
public static void main(String[] args) {
// 1~100 사이 값 랜덤 선택
int findNumber = (int)(Math.random()*100);
for(int i=0; i<100; i++) {
if (i = findNumber) {
System.out.println(i);
break;
}
}
}
}
우리는 항상 최악의 케이스를 고려해야 한다.
코딩 테스트에서는 빅-오 표기법()을 기준으로 수행 시간을 계산하는 것이 좋다.
각각의 시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.
버플 정렬과 병합 정렬의 시간 복잡도를 각각 , 이라고 알고 있다고 가정하자.
주어진 시간 제한이 2초이므로, 연산 횟수 2억 번 안에 원하는 답을 구해야 한다.
버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니다.
병합 정렬은 약 2000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이다.
이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다.
즉, 데이터 크기(N)를 단서로 사용해야 하는 알고리즘을 추측해볼 수 있다.
시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.
이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.
int N = 100000;
int cnt = 0;
for(int i=0; i<N; i++) {
System.out.println(cnt++);
}
// 연산 횟수가 N인 경우
int N = 100000;
int cnt = 0;
for(int i=0; i<N; i++) {
System.out.println(cnt++);
}
for(int i=0; i<N; i++) {
System.out.println(cnt++);
}
for(int i=0; i<N; i++) {
System.out.println(cnt++);
}
두 코드 연산 횟수는 3배의 차이가 난다.
하지만 코딩 테스트에서는 일반적으로 상수를 무시하므로, 두 코드 모두 시간 복잡도는 이다.
int N = 100000;
int cnt = 0;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
System.out.println(cnt++);
}
}
시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로, 이 코드에서는 이중 for 문이 전체 코드의 시간 복잡도 기준이 된다.
만약 일반 for문이 10개 더 있다 하더라도 도출 원리의 기준 2에 따라 시간 복잡도의 변화 없이 로 유지된다.
이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.
시간 복잡도를 따지는 건 다음 순서대로 확인한다.