코딩 테스트 문제 중에는 프로그램 실행 시간이 특정 시간 미만이어야 하는 조건이 있습니다. 일반적으로 시간은 1초를 기준으로 하며, 문제에서 주어지는 모든 형태의 입력을 처리하는 데 프로그램이 1초 이상 걸리면 안 됩니다. 시간제한이 있는 문제에서 실행 시간이 해당 제한 시간을 넘어가면 시간 초과가 발생하여 오답 처리 됩니다.
하지만 효율성을 측정하는 문제의 경우 대부분 입력 크기가 매우 큽니다. 1만 개의 입력을 받는 문제를 풀 때 코드가 효율적인지 측정하기 위해 모든 입력을 직접 넣기 힘듭니다.. 이때 우리가 작성하는 코드의 실행 시간이 입력 데이터의 크기와 어떤 관계가 있는지 파악해서 그 효율성을 계산해야 합니다. 이렇게 코드 혹은 알고리즘의 실행 시간과 데이터의 상관관계를 시간 복잡도라고 합니다.
시간 복잡도는 코딩 테스트에서 매우 중요한 개념으로, 제대로 학습해야 코딩 테스트에서 요구하는 효율적인 코드를 작성할 수 있습니다.
복잡도를 측정함으로써 다음의 2가지를 계산할 수 있습니다.
- 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양
알고리즘이란, 어떤 목적을 해결하기 위한 일련의 과정을 의미합니다. 문제를 해결하는 알고리즘은 다양하며 여러 가지 상황에 따라 시간 복잡도가 가장 낮은 알고리즘을 선택해서 사용하면 됩니다. 시간 복잡도는 알고리즘의 시간적 효율성, 공간 복잡도는 알고리즘의 메모리 효율성을 의미합니다.
알고리즘의 실행 시간
- 입력 값의 크기에 따라 알고리즘의 실행시간을 검증해 볼 수 있습니다.
- 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데, 이를 점근적 표기법이라고 합니다. 여기서, 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미입니다.
효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립합니다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있습니다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있습니다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션(memoization) 기법이 있습니다.
시간 복잡도(Time Complexity)
알고리즘 문제를 풀 때 단순히 복잡도라고 하면 보통은 시간 복잡도를 의미합니다. 코딩 테스트를 처음 접하는 사람이 가장 어렵다고 느끼는 부분이 시간제한입니다. 여기서 시간제한이라고 한다면 문제를 푸는 시간을 정한 것처럼 보일 수 있지만, 코딩 테스트에서는 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미합니다. 그래서 해당 시간 안에 동작하는 프로그램을 작성해야 하며, 비효율적으로 작성하여 시간제한을 넘기면 '시간 초과'라는 메시지와 함께 오답 처리됩니다.
시간 복잡도 분석은 문제 풀이의 핵심입니다. 알고리즘 문제 풀이에 능숙한 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 합니다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치챌 수 있기 때문입니다. 그렇기 때문에 입력 값이 커지면 커질수록 증가하는 시간의 비율을 최소화한 알고리즘을 구성해야 합니다.
시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용합니다. 빅오 표기법을 간단하게 정의하자면 가장 빠르게 증가하는 항만을 고려하는 표기법입니다. 즉, 함수의 상한만을 나타냅니다. 시간 개념이 아니라 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇 번인지 세는 것입니다.
시간 복잡도를 줄이는 방법으로는 반복하는 연산 횟수를 줄이거나, 적절한 자료구조 및 알고리즘을 사용하면 됩니다.
빅오 표기법
빅오 표기법은 인자가 특정한 값이나 무한대로 향할 때 함수의 극한적인 동작을 설명하는 수학적인 표기법으로, 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용합니다.
시간 복잡도 표기법
- Big-O(빅-오) → 상한 점근
- Big-Ω(빅-오메가) → 하한 점근
- Big- θ(빅-세타) → 평균
위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 평균의 경우에 구분하여 나타내는 방법입니다.
알고리즘의 성능 평가 유형에서는 이 중 빅오 표기법의 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있습니다. 어느 정도의 시간이 "걸린다." 보다는 "걸릴 수 있다"를 고려하게 된다면 그에 맞는 대응이 가능합니다.
알고리즘에서 영향력이 없는 계수와 낮은 차수의 항은 무시할 수 있습니다. 가장 차수가 제일 높은 항 이외에 나머지 항은 무시할 수 있습니다. 예를 들어, O(5N^2 + N) = O(N^2)가 됩니다.
그리고 Big-O 표기법에서 데이터의 입력값의 크기에 따라 영향을 받기 때문에 상수는 1로 통일시킵니다.
예를 들어, O(N + 2) = O(N)이 됩니다.
위 그래프를 보면 시간 복잡도에 상관되어 n(인풋)의 크기에 따라 얼마나 많은 시간이 걸리는지 예상할 수 있습니다.
빅오 표기법 | 표현 |
O(1) | 상수 |
O(logN) | 로그 |
O(N) | 선형 |
O(NlogN) | 로그 선형 |
O(N^2) | 다항 |
O(2^N) | 지수 |
왼쪽부터 오른쪽까지 점점 시간 복잡도가 길어지는 표기법입니다.
n이 작을 때는 알고리즘 간에 차이가 거의 없지만 값이 커질수록 복잡한 알고리즘은 수행 시간이 기하급수적으로 길어집니다.
시간 복잡도를 낮출 수 있다면 프로그램에 대한 성능 개선을 기대할 수 있습니다.
- O(1)
- O(1)은 입력값이 증가하더라고 시간이 일정한 복잡도입니다.
- 예) 배열 또는 리스트에서 특정 인덱스 탐색 등
- O(logN)
- 입력값이 증가할 때마다 시간이 로그 스케일로 증가하는 로그 복잡도입니다.
- 예) 이진 탐색 알고리즘 등
- O(N)
- O(N)은 입력값이 증가하면 시간도 같은 비율로 증가하는 선형 복잡도입니다.
- 예) 반복문, 선형 탐색 알고리즘 등
- O(NlogN)
- 입력값이 증가할 때마다 시간이 로그 값에 비례하여 증가하는 로그 선형 복잡도입니다.
- 예) 병합 정렬, 힙 정렬 알고리즘 등
- O(N^2)
- 입력값이 증가하면 시간이 n의 제곱수의 비율로 증가하는 2차 복잡도입니다.
- 예) 선택 정렬, 버블 정렬, 퀵 정렬 알고리즘 등
- O(2^N)
- 입력값이 증가하면 시간이 기하급수적으로 증가하는 기하급수적 복잡도입니다.
- 예) 부분집합
코딩 테스트 대비 계산 방법
코딩 테스트 문제를 풀 때 가능한 연산의 횟수는 시간제한 초수 * 1억입니다. 즉, 알고리즘의 최악의 경우에서 계산한 가능 연산 횟수를 초과하지 않으면 됩니다. 그렇기 때문에, 문제에서 주어지는 최대 입력 데이터 수를 보고 대략 가능한 시간 복잡도를 파악하고 구상할 수 있습니다.
시간복잡도 / N | 10 | 20 | 100 | 10,000 | 1,000,000 | 100,000,000 |
O(1) | 1 | 1 | 1 | 1 | 1 | 1 |
O(logN) | 3 | 4 | 7 | 13 | 20 | 27 |
O(N) | 10 | 20 | 100 | 10,000 | 1,000,000 | 100,000,000 |
O(N logN) | 33 | 86 | 664 | 132,877 | - | - |
O(2^n) | 1,024 | 1,048,576 | - | - | - | - |
O(N!) | 3,628,800 | - | - | - | - | - |
입력 데이터 개수별 사용 가능한 시간 복잡도 알고리즘
시간 복잡도는 프로그램 실행 시간을 결정짓는 중요한 요소이기 때문에 코딩 테스트에서 코드를 작성할 때는 자신이 생각한 풀이의 시간 복잡도를 고려해야 합니다. 1초를 만족하는 정해진 시간 복잡도는 문제별로 다릅니다. 문제별로 주어지는 입력 데이터의 종류와 그 개수가 다르기 때문에 정해진 시간 복잡도는 있을 수 없습니다. 하지만 입력 조건에서 명시되어 있는 최악의 경우를 시간 복잡도에 대입해 보았을 때 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 수 있습니다.
자신의 시간 복잡도에 문제의 제한 사항에 표기된 가장 큰 입력을 대입하여 계산했을 때 아무리 커도 1억을 넘기지 않아야 시간제한에서 안전한 코드입니다. 풀이를 고안한 후 문제의 입력 조건을 시간 복잡도에 대입한 결과가 1억보다 큰 경우는 생각보다 매우 빈번히 발생합니다. 이 경우에는 풀이법이 문제를 충분히 효율적으로 해결하지 못하므로 다른 풀이를 찾아봐야 합니다.
풀이를 고안하는 정도가 아닌 코드까지 작성한 후 시간 초과를 발견한다면 코드마저 새로 작성해야 하는 상황이 발생합니다. 따라서 코드를 작성하기 전에 풀이를 먼저 생각하고, 시간 복잡도를 이용하여 효율성이 검증되면 그 이후에 코드를 작성해야 합니다.
비효율적인 문제 풀이 과정과 효율적인 문제 풀이 과정
비효율적인 문제 풀이 과정
문제 확인 → 풀이 고안 & 작성 → 제출 → 통과 → 완료
제출 통과 실패 시 → 풀이 고안 & 작성 → 제출 → 통과 → 완료
효율적인 문제 풀이 과정
문제 확인 → 풀이 고안 → 효율성 검증 → 통과 → 풀이 작성 → 제출 → 통과 → 완료
효율성 검증 통과 실패 시 → 풀이 고안 → 통과 → 풀이 작성 → 제출 → 통과 → 완료
제출 통과 실패 시 → 풀이 고안 → 통과 → 풀이 작성 → 제출 → 통과 → 완료
시간 복잡도 계산하기
시간 복잡도를 계산하는 가장 기본적인 방법은 반복 횟수를 세는 것입니다. 일반적으로 입력되는 값들을 순회하면서 처리하는 데 반복문이 사용됩니다. 이렇게 사용되는 반복문이 어떤 값에 비례해서 반복하는지 따져 보면 시간 복잡도를 계산할 수 있습니다.
시간 복잡도는 정확한 실행 시간을 계산하는 게 아니라 단지 실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일 뿐입니다. 따라서 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않습니다.
시간 복잡도를 줄이는 방법
시간 복잡도 수식에 가장 큰 입력에 대입하여 계산한 결과가 1억 이상이라면 풀이가 충분히 효율적이지 않은 것입니다. 따라서 더욱 효율적인 풀이를 생각해 내어 시간 복잡도를 줄여야 합니다. 따라서 더욱 효율적인 풀이를 생각해 시간 복잡도를 줄여야 합니다.
예를 들어서, 배열에서는 배열의 모든 원소를 순회한다면 O(N)의 시간 복잡도가 소요됩니다. 하지만 정렬되어 있다는 조건에 주목하면 이진 탐색을 적용할 수 있다는 것을 알 수 있습니다. 이진 탐색의 시간 복잡도는 O(logN)이므로 훨씬 효율적으로 탐색할 수 있습니다.
또 배열에서 중복을 제거한 원소들을 찾고 싶을 때 원소별로 배열 전체를 순회하면 O(N^2)의 시간 복잡도가 소요됩니다. 이때 자료 구조 Set을 이용하면 O(N)으로 해결할 수 있습니다. O(N^2)과 O(N)은 N의 크기가 커질수록 엄청난 효율성 차이를 보입니다.
따라서 문제 조건에 맞는 적절한 알고리즘과 자료구조를 이용하는 것이 코딩 테스트의 핵심입니다.
문제를 보고 효율적인 풀이를 보고 떠올리기 어렵다면 문제에서 주어진 입력 조건을 이용해 풀이의 시간 복잡도를 먼저 유추하는 것도 풀이를 생각해 내기에 좋은 힌트가 될 수 있습니다. 이처럼 시간 복잡도를 이용하면 문제에서 주어진 조건으로 풀이에 대한 힌트를 얻을 수 있습니다. 하지만 시간 복잡도와 상관없이 작은 입력 제한을 주는 문제도 나올 수 있으므로 유추 가능한 알고리즘은 어디까지나 힌트로 사용해야 합니다. 무조건 해당 알고리즘을 사용하여 문제를 해결해야 한다는 의미는 아닙니다.
자료구조 지표
자료구조 | 평균 | 최악 | |||
탐색 | 추가 | 탐색 | 추가 | 삭제 | |
알고리즘 지표
알고리즘 | 공간 복잡도 | 시간 복잡도 | ||
최악 | 최선 | 평균 | 최악 | |
이진 탐색 | O(log n) |
*위 자료구조 및 알고리즘 표는 개인 공부 및 개발 블로그 작성 동기를 위해 포스트 작성할 때마다 추가하도록 하겠습니다 :)
공간 복잡도
공간 복잡도를 표기할 때도 시간 복잡도를 표기했던 것처럼 빅오(Big-O) 표기법을 사용합니다.
즉, 공간 복잡도 또한 O(NlogN), O(N^2) 등으로 표기합니다. 다만, 앞서 시간 복잡도에서 절대적인 제한 시간이 있던 것처럼, 메모리 사용량에도 절대적인 제한이 있습니다. 일반적으로 메모리 사용량 기준은 MB단위로 제시되어 있습니다. 즉, 코딩 테스트 문제에서 보이는 '시간제한 1초, 메모리 제한 128MB'와 같은 문장은 시간 복잡도와 공간 복잡도를 함께 제한하기 위해 명시하는 것입니다.
코딩 테스트 문제는 대부분 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 리스트(배열)를 사용해서 풀어야 합니다. 코딩 테스트에서는 보통 메모리 사용량을 128 ~ 512MB 정도로 제한합니다. 다시 말해 일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 알고리즘 설계를 해야 한다는 의미입니다.
공간 복잡도는 소프트웨어가 메모리를 다루는 양이 얼마인지에 대한 지표입니다.
최근 컴퓨터의 성능 발전으로 예전에 비해서 중요도는 떨어졌지만, 빅데이터 분야에서는 여전히 중요한 지표로 사용됩니다.
공간 복잡도에서 알고리즘을 실행시키기 위해 필요한 공간은 두 가지로 나눌 수 있습니다.
- 알고리즘과 무관[고정 공간] : 코드를 저장하는 공간, 알고리즘을 실행할 시스템이 필요로 하는 공간 등이 있습니다.
- 알고리즘과 연관[가변 공간] : 문제 해결을 위해 알고리즘이 필요로 하는 공간, 변수를 저장하는 공간, 순환 스택 등이 있습니다.
'🐥Algorithm[알고리즘]' 카테고리의 다른 글
[Algorithm] 알고리즘 코딩 테스트를 왜 공부해야 하나요..? ㅠㅅㅠ.. -Gyunny (0) | 2024.05.01 |
---|