『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

시간복잡도

💡 알고리즘 선택의 기준이 되는 시간 복잡도

• 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다.
• 왜 시간 복잡도가 알고리즘 선택의 기준이 되는가?

---

시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.

시간 복잡도 정의하기

실제 시간 복잡도를 정의하는 3가지 유형은 다음과 같다.

• 빅-오메가($\Omega(n)$)
  • 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타($\Theta(n)$)
  • 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오($O(n)$)
  • 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

다음처럼 0~99 사이의 무작위 값을 찾아 출력하는 코드가 있을 때,

• 빅-오메가 표기법의 시간 복잡도는 1번
  • findNumber가 0이 나오는 경우
• 빅-세타 표기법의 시간 복잡도는 $\frac{N}{2}$번
  • 평균적으로 50번 정도의 연산
• 빅-오 표기법의 시간 복잡도는 N번

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;
			}
		}
	}
}

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?

우리는 항상 최악의 케이스를 고려해야 한다.

코딩 테스트에서는 빅-오 표기법($O(n)$)을 기준으로 수행 시간을 계산하는 것이 좋다.

• 실제 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단한다.
• 따라서 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.

각각의 시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$

---

시간 복잡도 활용하기

알고리즘 선택의 기준으로 사용하기

버플 정렬과 병합 정렬의 시간 복잡도를 각각 $O(n^2)$, $O(n\log n)$이라고 알고 있다고 가정하자.

2750번: 수 정렬하기

연산 횟수 계산 방법

알고리즘 적합성 평가

주어진 시간 제한이 2초이므로, 연산 횟수 2억 번 안에 원하는 답을 구해야 한다.

• 버블 정렬 = $(1,000,000)^2=1,000,000,000,000>2000,000,000$
  • 부적합 알고리즘
• 병합 정렬 = $1,000,000log(1,000,000)=약2,000,000,000$
  • 적합 알고리즘

버블 정렬은 약 10억 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니다.

병합 정렬은 약 2000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이다.

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다.

즉, 데이터 크기(N)를 단서로 사용해야 하는 알고리즘을 추측해볼 수 있다.

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.

이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

예

• 연산 횟수가 N인 경우

int N = 100000;
int cnt = 0;
for(int i=0; i<N; i++) {
	System.out.println(cnt++);
}

• 연산 횟수가 3N인 경우

// 연산 횟수가 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배의 차이가 난다.

하지만 코딩 테스트에서는 일반적으로 상수를 무시하므로, 두 코드 모두 시간 복잡도는 $O(n)$이다.

시간복잡도 계산할 때 상수 무시 - 인프런

• 연산 횟수가 $N^2$인 경우

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에 따라 시간 복잡도의 변화 없이 $N^2$로 유지된다.

---

정리

이와 같이 자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩 테스트에서 시간 초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고, 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있다.

시간 복잡도를 따지는 건 다음 순서대로 확인한다.

• 알맞은 알고리즘 쓰기 → 선택 기준
• 비효율적인 로직 찾아서 효율적으로 바꾸기
  • 알맞은 알고리즘을 썼는데도 시간 초과가 나올 경우

---

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런