[알고리즘] 시간 복잡도 / JavaScript

진욱·2025년 11월 28일

알고리즘

목록 보기

1/11

📍 들어가며

25년 하반기 채용 시장도 끝나가고 있습니다. 이번 포스트에서는 하반기를 대비해 코딩 테스트를 준비하고 네 번의 시험을 치루며 몸소 느낀 점을 기록하려 합니다...

코딩 테스트를 위해 그리디, 완전탐색, DFS/BFS, 다익스트라, DP, 투포인터 등 다양한 유형의 풀이 방법을 익혔습니다. 계속 반복해서 문제를 풀다 보니 실력이 점점 향상되는 것도 느낄 수 있었습니다. 예전에는 손도 못 대던 DFS/BFS, 우선순위 큐(~~JavaScript는 우선순위 큐를 직접 구현해야 하기에...~~) 등을 구현할 수 있게 된 것이죠. 실제 코딩 테스트에서도 테스트 케이스 통과 빈도가 늘어났고, 문제 풀이 시간이 확실히 단축된 것을 체감했습니다.

하지만 아직도 몇 가지 부족한 점이 존재했습니다. 첫째, 문제를 딱 보고 "아 이 방법으로 접근해야겠구나!" 라고 떠오르는 단계가 아니라는 점. 둘째, 이번 포스트의 핵심인 시간 초과 및 효율성 테스트 실패가 그것입니다.

프로그래머스에서 코딩 테스트를 풀다가 다음과 같은 화면을 마주한 적이 있으실 것입니다.

분명 주어진 테스트 케이스는 모두 통과했는데, 코드 실행 및 제출하기를 눌러보면 시간 초과라고 뜨는 경우입니다. 연습 과정에서 다음 화면을 마주하는 것이 차라리 다행입니다. 실제 코딩 테스트에서는 문제에 주어진 테스트 케이스 이외에 다른 테스트에 대한 결과를 확인할 수 없기에, 테스트 케이스를 통과했다고 해서 제출한 코드가 정답인지 확신할 수 없기 때문입니다.

이번 하반기 진행한 코딩 테스트에서 모든 문제를 잘 풀이했다고 생각했는데 계속해서 좋지 않은 결과를 마주하게 되다 보니 그 이유를 찾아서 문제를 반드시 해결해야겠다는 생각이 들었고, 제 풀이에서 시간 복잡도와 효율성을 지키지 못한다는 점이 가장 중요한 문제라고 생각해 다시 한 번 개념을 잡고 문제 풀이에 적용하기로 결심했습니다.

📍 복잡도

먼저, 복잡도(Complexity)에 대해 알아보겠습니다. 복잡도는 알고리즘의 성능과 효율성을 나타내는 척도로, 일반적으로 복잡도가 낮을수록 좋은 알고리즘을 나타냅니다. 복잡도는 크게 시간 복잡도와 공간복잡도로 나눌 수 있는데, 알고리즘 수행을 위해 필요한 연산 횟수가 시간 복잡도, 메모리의 양이 공간 복잡도입니다.

시간 복잡도와 공간 복잡도 사이에는 Trade-off가 성립합니다. 메모리를 조금 더 사용하면 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 연산의 복잡도를 줄일 수 있습니다. 아래에서 시간 복잡도와 공간 복잡도에 대해 간단하게 알아보겠습니다.

⏰ 시간복잡도

시간복잡도(Time Complexity)

시간 복잡도란 특정 크기의 입력에 대해 필요한 연산 횟수를 의미합니다. 시간 복잡도는 낮으면 낮을수록 좋습니다.

코딩 테스트에 출제되는 문제들은 수행 시간이 제한되어 있습니다. 따라서 문제를 푸는 알고리즘이 여러 개 존재하는 경우, 당연히 더 빠르게 연산할 수 있는 알고리즘을 선택해야 합니다. 그런데 어떤 기준으로 알고리즘을 선정해야 할까요? 이 때 시간 복잡도가 필요합니다. 어떤 문제를 해결하는 알고리즘 A, B, C가 있을 때 시간 복잡도가 가장 낮은 알고리즘이 A라면, A를 사용하는 것이 더 효율적일 것입니다.

📦 공간복잡도

공간복잡도(Space Complexity)

공간 복잡도란 프로그램 실행과 완료에 필요한 메모리를 의미합니다. 알고리즘 실행을 위해 시스템이 필요로 하는 고정 공간, 문제 해결(변수, 배열, 스택 등)을 위해 알고리즘이 필요로 하는 가변 공간으로 구분할 수 있습니다.

위에서 언급하였듯이 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있으며, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 우선으로 판단합니다.

📍 수행 시간을 측정하는 방법

그렇다면 알고리즘의 수행 시간을 어떻게 측정할 수 있을까요?

알고리즘 수행 시간 측정 방법으로는 절대 시간 축정 방법과 시간 복잡도 측정 방법이 있습니다. 절대 시간 측정 방법은 말 그대로 프로그램을 실행하여 결과가 나올 때까지 시간을 측정하는 것이지만, 이는 프로그램 실행 환경에 따라 달라질 수 있기 때문에 코딩 테스트에서는 시간 복잡도 측정 방법을 사용합니다.

⏰ 시간 복잡도 측정 방법

시간 복잡도는 알고리즘이 시작한 순간부터 결과값이 나올 때까지 연산 횟수를 나타냅니다. 또한 시간 복잡도 측정 결과는 다음과 같이 최선(Best), 보통(Normal), 최악(Worst)로 나눕니다.

알고리즘 성능 평가 Case

최선(Best)
최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우

보통(Normal)
여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

최악(Worst)
최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우

이제 시간 복잡도를 표현할 방법이 필요합니다. 특정 입력 크기에 한하여 연산 횟수를 기준으로 시간 복잡도를 측정하는 것이 아니라, 입력 크기를 N으로 일반화하여 연산 횟수의 추이를 나타내야 합니다. 이처럼 입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다. 또한 코딩 테스트에서는 모든 경우의 수에 대해 알고리즘이 문제를 처리하는 것을 고려해야 하므로 최악의 경우를 가정하는 것이 일반적입니다.

🅾️ Big-O 표기법

시간 복잡도를 표현할 때 상한선을 활용하는 점근적 표기법을 가장 많이 활용하며, 이를 Big-O 표기법(Big-O notation) 이라고 합니다. Big-O 표기법의 수학적 정의는 다음과 같습니다.

Big-O 표기법의 수학적 정의

$f(x)$ 와 다음을 만족하는 $C$ 가 있으면 $f(x)$ 의 최악의 시간 복잡도는 $O(g(x))$ 로 표현할 수 있습니다.

특정 $x$ 시점 이후부터 항상 $f(x) <= C * g(x)$ 를 만족 ( $C$ 는 상수)

어떤 프로그램의 연산 횟수가 $f(x)$ 라고 할 때, 함수의 최고차항만 남기고 차수를 지워 $O(...)$ 와 같이 표기하면 됩니다.

Big-O 표기법의 특징

Big-O 표기법은 N이 충분히 크다고 가정하고 있기 때문에 계수는 무시합니다.
$O(2n) = O(n)$

Big-O 표기법은 N의 크기에 영향을 받으므로 최고차항 이외에 다른 항은 무시합니다.
$O(n^2 + logn) = O(n^2)$

예를 들어 어떤 프로그램의 연산 횟수가 $f(x)=2x^2+3x+5$ 라면 시간 복잡도를 $O(x^2)$ 과 같이 표현하면 됩니다.

다음 solution 함수의 시간 복잡도는 어떻게 계산할 수 있을까요?

function solution(n) {
  let count = 0;
  
  // n * n 번 연산 수행
  for (let i = 0; i < n; i++) {
  	for (let j = 0; j < n; j++) {
      count += 1;
    }
  }
  
  // n 번 연산 수행
  for (let i = 0; i < n; i++) {
    count += 1;
  }
  
  // 2n 번 연산 수행
  for (let i = 0; i < n * 2; i++) {
    count += 1;
  }
  
  // 5 번 연산 수행
  for (let i = 0; i < 5; i++) {
    count += 1;
  }
  
  return count;
}

console.log(solution(6)); // 함수 호출 (결과값: 59)

solution 함수는 각 반복문을 돌면서 $n^2$ , $n$ , $2n$ , $5$ 번의 증가 연산을 하므로 $f(n)=n^2+3n+5$ 로 표현할 수 있으며 시간 복잡도는 $O(n^2)$ 로 나타낼 수 있습니다.

📍 코딩 테스트에 적용

그렇다면 Big-O 표기법을 어떻게 활용하면 좋을까요? 코딩 테스트의 문제에는 제한 시간이 있으므로 문제를 분석한 후, Big-O 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 연산을 수행할 수 있는지 확인할 수 있습니다.

보통 다음을 기준으로 알고리즘을 선택합니다.

컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다.

따라서 연산 횟수는 1000 ~ 3000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다. 제한 시간이 1초인 문제라면 각 시간 복잡도별 최대 연산 횟수와 가능한 N의 범위는 다음과 같습니다.

📍 결론

각 시간 복잡도를 하나하나 공부하고 외울 수는 없을 것입니다. 하지만 어떤 경우에 어떤 시간 복잡도가 나오는지 코드를 짤 때 파악하는 것이 중요합니다.

앞으로는 코드를 작성하면서 문제에 주어진 제한시간을 확인하고, 주어진 입력값 N에 대해 적절한 알고리즘을 선택해 나가며 문제 풀이를 진행해야겠습니다.

코딩 테스트를 안정적으로 통과하는 그 날까지 모두 화이팅 💪

📖 참고자료

진욱

다음 포스트