Ruby 개발자를 위한 시간 복잡도 완벽 가이드

시간 복잡도(Time Complexity)는 컴퓨터 과학에서 배울 수 있는 가장 흥미로운 개념 중 하나이며, 전공 학위 없이도 누구나 이해할 수 있습니다!

시간 복잡도가 흥미로운 이유는 특정 알고리즘이나 프로그램이 느려지는 원인을 파악하고, 이를 더 빠르게 만들 방법을 찾는 데 결정적인 도움을 주기 때문입니다.

여러분이 직접 작성한 코드에도 바로 적용할 수 있습니다.

그리고 이 개념은 컴퓨터 과학 교재에 나오는 화려한 알고리즘에만 국한되지 않습니다. 이 글 후반부에서 직접 확인해 보겠습니다.

먼저 '느리다'와 '빠르다'가 무엇을 의미하는지 살펴보겠습니다.

느림 vs 빠름

100만 개의 숫자를 정렬하는 데 150밀리초(ms)가 걸렸다면, 이것은 느린 걸까요 빠른 걸까요?

충분히 빠르다고 생각하지만, 사실 이것은 시간 복잡도가 답하려는 질문이 아닙니다.

시간 복잡도가 궁금해하는 것은 입력 크기(input size)가 커질 때 알고리즘의 성능이 어떻게 변하는가입니다.

여기서 '입력 크기'란 함수나 메서드에 전달되는 인자를 의미합니다. 메서드가 문자열 하나를 인자로 받는다면 그 문자열이 입력이고, 문자열의 길이가 곧 입력 크기입니다.

빅오(Big O) 표기법

빅오 표기법을 사용하면 알고리즘의 성능을 체계적으로 분류할 수 있습니다.

형태는 다음과 같습니다:

O(1)

위의 O(1)은 '상수 시간(constant time)' 알고리즘을 나타냅니다.

즉, 처리해야 할 작업량과 관계없이 항상 동일한 시간 안에 작업을 끝낸다는 뜻입니다.

또 다른 예로 '선형 시간(linear time)'이 있습니다:

O(n)

여기서 'n'은 입력의 크기(문자열 길이, 배열 크기 등)를 나타냅니다. 이 경우 작업 완료 시간이 입력 크기와 1:1 비율로 증가하므로, 입력 크기를 두 배로 늘리면 소요 시간도 두 배가 됩니다.

주요 빅오 표기법을 정리하면 다음과 같습니다:

표기법	이름	설명
O(1)	상수(Constant)	항상 동일한 시간이 걸립니다.
O(log n)	로그(Logarithmic)	루프가 한 번 반복될 때마다 작업량이 절반으로 줄어듭니다(이진 탐색).
O(n)	선형(Linear)	작업 완료 시간이 입력 크기와 1:1 비율로 증가합니다.
O(n log n)	선형 로그(Linearithmic)	내부 루프가 `log n` 시간에 실행되는 중첩 루프 구조입니다. 퀵소트, 머지소트, 힙소트 등이 여기에 해당합니다.
O(n^2)	이차(Quadratic)	작업 완료 시간이 입력 크기의 제곱(`input size ^ 2`)에 비례해 증가합니다. 모든 요소를 순회하는 루프 안에서 또 다른 루프가 모든 요소를 순회하는, 즉 중첩 루프가 있으면 이 유형이라고 판단할 수 있습니다.
O(n^3)	삼차(Cubic)	`n^2`과 같은 원리이지만, 시간이 입력 크기의 세제곱(`n^3`)에 비례해 증가합니다. 삼중 중첩 루프가 보이면 이 유형입니다.
O(2^n)	지수(Exponential)	작업 완료 시간이 `2 ^ 입력 크기`에 비례해 증가합니다. `n^2`보다 훨씬 느리므로 절대 혼동하지 마세요! 재귀 피보나치 알고리즘이 대표적인 예입니다.

알고리즘 분석하기

입력을 'n'개의 요소를 가진 배열이라고 상상하면 분석 감각을 기를 수 있습니다.

예를 들어 배열에서 짝수인 요소만 골라내고 싶다고 해봅시다. 조건에 맞는지 확인하려면 모든 요소를 한 번씩 읽는 방법밖에 없습니다.

[1,2,3,4,5,6,7,8,9,10].select(&:even?)

찾으려는 숫자를 놓칠 수 있기 때문에 어떤 숫자도 건너뛸 수 없습니다. 따라서 이것은 선형 시간 알고리즘, 즉 O(n)입니다.

같은 문제에 대한 3가지 해결책

개별 예제를 분석하는 것도 좋지만, 이 개념을 제대로 이해하는 데 진짜 도움이 되는 것은 같은 문제를 서로 다른 방식으로 풀어보는 것입니다.

스크래블(Scrabble) 단어 검증기를 통해 3가지 코드 예제를 살펴보겠습니다.

스크래블은 주어진 문자 목록(예: ollhe)으로 단어(예: hello)를 만들 수 있는지 확인하는 게임입니다.

첫 번째 해결책입니다:

def scramble(characters, word)
  word.each_char.all? { |c| characters.count(c) >= word.count(c) }
end

이 코드의 시간 복잡도가 무엇인지 짐작되시나요? 핵심은 count 메서드에 있습니다. 이 메서드가 무슨 일을 하는지 정확히 이해하는 것이 중요합니다.

정답은 O(n^2)입니다.

그 이유는 each_char로 문자열 word의 모든 문자를 순회하기 때문입니다. 이것만 보면 선형 시간 O(n) 알고리즘이지만, 블록 내부에 count 메서드가 있습니다.

count 메서드는 사실상 문자열의 모든 문자를 다시 한번 순회하며 개수를 세는 또 하나의 루프입니다.

두 번째 해결책

좋습니다. 그렇다면 어떻게 하면 더 잘할 수 있을까요? 루핑 횟수를 줄일 방법이 있을까요?

문자를 세는 대신 제거해 버리면 순회해야 할 문자가 줄어듭니다.

두 번째 해결책입니다:

def scramble(characters, word)
  characters = characters.dup
  word.each_char.all? { |c| characters.sub!(c, "") }
end

이 버전은 조금 더 흥미롭습니다. 찾는 문자들이 문자열 앞쪽에 있는 최선의 경우에는 count 버전보다 훨씬 빠릅니다.

하지만 문자들이 모두 문자열 끝쪽에 word의 순서와 반대로 배치되어 있다면 성능이 count 버전과 비슷해집니다. 따라서 이것 역시 여전히 O(n^2) 알고리즘이라고 할 수 있습니다.

word의 문자를 하나도 사용할 수 없는 경우는 걱정할 필요가 없습니다. sub!가 false를 반환하는 즉시 all? 메서드가 중단되기 때문입니다. 다만 이런 동작은 일반적인 Ruby 강좌에서 다루는 수준을 훨씬 넘어, Ruby를 깊이 공부해야만 알 수 있는 부분입니다.

다른 접근 방식 시도하기

블록 내부의 루핑을 아예 없애면 어떨까요? 해시(hash)를 사용하면 가능합니다.

def scramble(characters, word)
  available = Hash.new(1)

  characters.each_char { |c| available[c] += 1 }
  word.each_char.all? { |c| available[c] -= 1; available[c] > 0 }
end

해시 값의 읽기와 쓰기는 O(1) 연산입니다. 즉, 특히 루핑과 비교하면 매우 빠릅니다.

그래도 두 개의 루프가 남아 있습니다:

하나는 해시 테이블을 만드는 루프이고, 다른 하나는 이를 검사하는 루프입니다. 하지만 이 두 루프는 중첩되어 있지 않으므로, 이것은 O(n) 알고리즘입니다.

세 가지 해결책을 벤치마크하면 분석 결과가 실제 측정값과 일치하는 것을 확인할 수 있습니다:

hash    1.216667   0.000000   1.216667 (  1.216007)
sub     6.240000   1.023333   7.263333 (  7.268173)
count 222.866644   0.073333 222.939977 (223.440862)

꺾은선 그래프로 보면 다음과 같습니다:

Ruby 개발자를 위한 시간 복잡도 완벽 가이드

몇 가지 주목할 점:

Y축(세로)은 작업을 완료하는 데 걸린 시간(초)을, X축(가로)은 입력 크기를 나타냅니다.
이 그래프는 로그 스케일로 그려져 특정 범위의 값이 압축되어 있습니다. 실제로는 count 선이 훨씬 가파릅니다.
로그 스케일로 그린 이유는 흥미로운 현상을 보여주기 위해서입니다. 입력 크기가 아주 작을 때는 오히려 count가 더 빠릅니다!

마무리

이번 글에서는 알고리즘의 시간 복잡도, 빅오 표기법, 그리고 시간 복잡도 분석 방법을 배웠습니다. 또한 같은 문제에 대한 여러 해결책을 비교하며 각각의 성능을 분석해 보았습니다.

새롭고 흥미로운 내용을 배우셨기를 바랍니다!

도움이 되었다면 SNS에 이 글을 공유해 주시고, 아직 구독하지 않으셨다면 뉴스레터를 구독해 주세요. 앞으로도 이런 콘텐츠를 계속 전해 드리겠습니다.

읽어 주셔서 감사합니다.