이 글은 〈[되기] 코딩 테스트 합격자 되기(파이썬 편)〉에서 발췌했습니다.

골든래빗 출판사
박경록 지음

프로그램의 성능은 가장 중요한 요소입니다. 그러면 프로그램의 성능은 어떻게 측정할까요? 이 책에서는 시간 복잡도라는 개념을 기준으로 프로그램의 성능을 분석합니다.

 

코딩 테스트에서 여러분이 보게 될 문제들은 저마다 ‘가장 효율적으로 해결하는 알고리즘’이 있습니다. 이는 알고리즘이 실행되는 제한 시간과 관련이 있습니다. 문제를 풀 수 있는 알고리즘이 여럿 있을 때 어떤 알고리즘은 문제를 빠르게 풀고, 어떤 알고리즘은 문제를 느리게 푼다면 당연히 문제를 빠르게 푸는 알고리즘을 선택해야 할 것입니다. 그런데 그런 알고리즘은 어떤 기준으로 선정해야 할까요? 바로 시간 복잡도를 보고 선정해야 합니다. 시간 복잡도(Time Complexity)란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미합니다. 시간 복잡도는 낮으면 낮을 수록 좋습니다. 이 설명은 이후 내용에서 조금 더 자세히 설명하겠습니다. 예를 들어 어떤 문제를 해결하는 알고리즘 A, B, C가 있을 때 시간 복잡도가 가장 낮은 알고리즘이 A라면 A를 사용하는 게 좋을 겁니다.

 

 

※ 시간 복잡도는 알고리즘 코딩 테스트 공부를 막 시작하는 단계에서는 알 듯 말 듯하게 느껴질 수 있는 개념입니다. 만약 초반부 내용을 조금 읽다가 당장 이해가 잘 되지 않는다는 생각이 들면 바로 ‘04장 코딩 테스트 필수 문법’으로 넘어가 공부를 진행하다가 추후에 돌아와 여기를 다시 읽어도 좋습니다. 그러나 시간 복잡도는 여러분이 결국 알아야 하는 개념입니다. 지금 당장은 넘어간다고 하더라도 언젠가는 꼭 돌아와 공부하기 바랍니다.

 

 

1차원 배열 검색하기

1차원 배열에 값이 있을 때 특정 값을 배열의 맨 앞에서 순서대로 검색한다고 해봅시다. 이때 값을 가장 빨리 찾는 경우와 가장 늦게 찾는 경우는 언제일까요?

 

값을 가장 빨리 찾는 경우

값을 가장 빨리 찾는 경우는 검색 시작 위치에 찾을 값이 바로 있는 경우입니다. 다음 그림에서는 배열의 1번째 위치부터 값을 찾고 있는데 찾을 값인 1이 배열 1번째 위치에 있으므로 1번만 비교하여 검색을 끝냅니다.

 

 

값을 가장 늦게 찾는 경우

값을 가장 늦게 찾는 경우는 아예 찾으려는 값이 없거나 가장 마지막에 위치하는 경우입니다. 다음은 전체 배열을 탐색해도 찾으려는 값이 없는 경우입니다. 연산 횟수가 최대입니다.

※ 이 경우 비교 횟수는 8번입니다.

 

 

알고리즘 수행 시간을 측정하는 방법

그럼 진짜 시간을 측정하는 방법, 알고리즘 수행 시간을 측정하는 방법을 알아보겠습니다. 알고리즘 수행 시간 측정 방법으로는 절대 시간을 측정하는 방법과 시간 복잡도를 측정하는 방법이 있습니다.

 

절대 시간을 측정하는 방법

절대 시간을 측정하는 방법은 말 그대로 시간을 측정하면 됩니다. 예를 들어 배열에서 검색하는 프로그램을 작성한 다음 프로그램을 실행하여 결과가 나올 때까지의 시간을 측정하면 됩니다. 그러나 이 방법은 프로그램을 실행하는 환경에 따라 달라질 수 있어서 코딩 테스트에서는 잘 활용하지 않습니다.

 

시간 복잡도를 측정하는 방법

시간 복잡도를 측정하는 방법은 앞서 검색 문제에서 살짝 언급한 ‘연산 횟수’와 관련이 있습니다. 즉, 시간 복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타냅니다. 그리고 시간 복잡도를 측정한 결과는 다음과 같이 최선(Best), 보통(Normal), 최악(Worst)의 경우로 나눕니다.

 

 

앞에서는 ‘배열의 맨 앞부터 하나씩 검사하기’라는 알고리즘을 사용했습니다. 이 알고리즘은 상황에 따라 최선의 연산 횟수는 1번, 최악의 연산 횟수는 8번이었죠.

 

시간 복잡도를 표현할 방법이 필요합니다

그러나 이렇게 최선은 1, 최악은 8이라는 특정한 입력 크기에 따른 연산 횟수로 시간 복잡도를 이야기하는 건 특정 상황에 한한 것이므로 무의미합니다. 예를 들어 위에서 설명한 1차원 배열에서 검색하는 문제에서 배열 크기가 1이면 최선, 보통, 최악의 경우는 모두 연산 횟수가 1입니다. 이 결과만 보고 ‘이 알고리즘은 모든 경우에 연산 횟수가 1인 성능을 가지는 것이구나’라고 생각하면 안 됩니다.

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

 

최악의 경우 시간 복잡도를 표현하는 빅오 표기법

그렇다면 최악의 경우에 대하여 시간 복잡도를 표현하는 방법은 무엇이 있을까요? 가장 많이 사용하는 점근적 표기법은 상한선을 활용하는 방법입니다. 그리고 이 표기법을 빅오 표기법(Big-O Notation)이라고 합니다.

빅오 표기법은 어렵지 않습니다. 어떤 프로그램의 연산 횟수가 f(x)라고 할 때 함수의 최고차항을 남기고 차수를 지워 O(…)와 같이 표기하면 됩니다. 예를 들어 어떤 프로그램의 연산 횟수가 f(x) = 2x² + 3x + 5라면 시간 복잡도를 O(x²)과 같이 표현하면 됩니다. 빅오 표기법은 다음 표를 보면 더 쉽게 이해할 수 있을 겁니다.

※ 점근 표기법이란 어떤 함수의 증가하는 추세를 표현하는 표기법입니다. 다만 점근 표기법은 이 책에서 자세히 설명하기는 적합하지 않으므로 이 정도만 이야기하겠습니다.

※ 상한선은 빅오 표기법, 하한선은 빅오메가 표기법으로 표시합니다.

 

 

그나저나 왜 이렇게 표기할까?

빅오 표기법으로 최악의 시간 복잡도를 표기하는 방법 자체가 어렵진 않습니다. 그런데 이 식은 어디서 나온 걸까요? 예를 들어 다음과 같은 코드가 있다고 생각해봅시다.

 

 

solution( ) 함수는 주석 영역별로 각각 n², n + 2_n, 5번의 증가 연산을 하며 결과값은 곧 연산 횟수를 의미합니다. 지금의 경우 solution(6)을 호출하면 6² + 3*6 + 5, 즉, 연산 횟수는 59입니다.

이때 solution( ) 함수는 식으로 다음과 같이 표현할 수 있습니다.

 

이때 다음을 만족하는 C가 있으면 f (x)의 최악의 시간 복잡도는 O(g(x))라고 쓰는 겁니다.

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

쉽게 말해 g(x)에 상수 C를 곱했을 때 특정 시점부터 f (x)를 넘어서는지 여부를 보면 됩니다. 필자가 찾은 C는 2, g (x)는 x2입니다. 그래프를 살펴보면 금방 이해할 수 있습니다.

 

 

그래프를 보면 대략 x = 4부터 항상 2x²가 f(x)를 넘으므로 위 공식을 만족합니다. 그런데 위 공식을 만족하는 g(x)는 하나만 있을까요? 이렇게 생각해볼 수도 있을 것 같습니다.

“g(x) = x, C = 50인 경우 x에 값을 몇 개 넣어보니 f(x)보다 값이 크네…? 그렇다면 시간 복잡도는 O(x)라고 해도 되는 것 아닐까?”

조금만 생각해보면 아니라는 걸 알 수 있습니다. 왜냐하면 50x는 대략 x=47에서 다시 역전당하기 때문이죠. 이런 이유로 𝑓(x) = x² + 3_x + 5의 시간 복잡도는 O(x²)이라고 쓸 수 있습니다.

 

 

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 차수를 지울까?

앞서 빅오 표기법은 다음과 같이 f(x)의 최고차항만 남기고 차수를 지워 O(…)와 같이 쓸 수 있다고 했습니다. 어떻게 이렇게 해도 되는지 설명하겠습니다.

• 𝑓(x) = x² + 3_x + 5에서 최고 차항인 x²만 남김
• x2는 앞의 차수가 1이므로 제거할 것이 없음
• 시간 복잡도는 O(x2)

다음은 x, x², x³를 비교한 그래프입니다. 그래프를 보면 데이터가 커질수록 세 그래프의 차이는 확연히 벌어집니다. x값이 무한하게 커지면 그 격차는 더 심해지겠죠. x³에 비해 x와 x²는 무시할 수 있을 정도로 작을 겁니다.

 

 

지수함수와 로그함수의 경우도 ‘x가 무한히 커진다’라는 것만 상상만 할 수 있으면 쉽게 이해할 수 있습니다. 로그함수는 다항함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가합니다. 그러므로 최고차항만 남기는 작업에서 우선 순위는 다음과 같을 겁니다.

 

 

이 우선 순위대로면 다항함수와 로그함수가 섞여 있을 때 로그함수를, 지수함수와 다항함수가 섞여 있다면 다항함수를 지워야 할 것입니다.

 

 

2편에서는 시간 복잡도를 코딩 테스트에 활용하는 방법을 알아보고, 계산해 봅시다.

 

자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지

[되기] 코딩 테스트 합격자 되기(파이썬 편)

저자 박경록

매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.