Big-O 시간 복잡도

시간 복잡도

코딩 테스트를 공부하면 시간 복잡도(Time Complexity)에 대해 꼭 다루게 됩니다. 코딩 테스트 문제를 효율적으로 풀기 위해서는 꼭 필요한 개념이기 때문입니다.

시간 복잡도는 입력값의 크기가 커짐에 따라 실행 시간이 얼마나 늘어나는지를 나타내는 알고리즘의 성능 지표입니다.

코딩테스트 문제를 풀 때 가장 첫 번째로 시간 복잡도를 분석하고, 적합한 알고리즘을 사용하면 최악의 시나리오에도 문제에서 주어진 제한 시간 내에 정답을 출력할 수 있는 코드를 작성할 수 있게 됩니다.

최악을 대비하는 Big-O 표기법

코딩 테스트 문제에는 제한 시간이 있어서, 문제를 풀기 전에 최악의 테스트 케이스까지도 시간 내에 정답을 출력할 수 있는지 확인할 수 있어야 합니다.

그래서 시간 복잡도를 표기 하는 많은 방법 중, 알고리즘 문제를 풀 때는 보통 Big-O 표기법을 사용합니다. Big-O 표기법은 최악의 경우에도 이 정도 시간은 보장한다는 의미를 담고 있습니다.

function solution(n) {
	// 1) n회 반복
  for (let i = 0; i < n; i++) {
    console.log(i);
  }
  
	// 2) n^2회 반복
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      console.log(i, j);
    }
  }
}

위 코드에서 solution 함수는 for 문이 n만큼 돌고 또 n²만큼 돌기 때문에, 연산 횟수는 f(n) = n² + n 입니다.

하지만, n이 무한히 커질 때, n²은 비교적 아주 빠르게 커지는 반면, n은 증가량에 미치는 영향이 미미합니다. 따라서, 최악의 경우를 고려하는 Big-O 표기법에서는 영향력이 가장 큰 항(이 경우에는 n²)만 남깁니다.

그래서 시간 복잡도는 n² + n에서 n을 무시한 O(N²)으로 표기합니다.

입력 크기에 따른 알고리즘 선택 가이드

코딩 테스트 문제의 제한 시간은 보통 1~2초 내외입니다. 일반적으로 파이썬은 1초에 약 2,000만 번, C++/Java는 약 1억 번의 연산이 가능하다고 가정하고 접근하는 것이 안전합니다.

데이터의 크기(N)에 따라 선택해야 하는 알고리즘의 기준은 다음과 같습니다.

결국 문제를 풀기 전에 입력값의 범위를 확인하는 습관이 정말 중요한 것 같습니다.

이전에는 시간 복잡도 개념을 잘 몰라서 '왜 이 코드가 시간 초과가 나지?', '어떻게 해결해야 하지?'라는 의문이 생기곤 했는데요. 이제 성능 지표를 배웠으니, 앞으로는 미리 시간 복잡도를 고려해서 시간 초과가 나지 않는 코드를 짜보려고 합니다.

만약 시간 초과가 나더라도 당황하지 않고, 배운 내용을 토대로 더 효율적인 알고리즘을 찾아낼 수 있을 것 같습니다!