코딩테스트 복잡도
코딩테스트에서 복잡도는 매우 중요한 개념입니다. 복잡도를 효과적으로 이해하고 코드에 적용할 수 있으면, 테스트에서 높은 점수를 얻을 가능성이 크게 높아집니다. 본 글에서는 복잡도에 대해 알아볼 예정이며, 간략한 코드 예시와 함께 시간 복잡도와 공간 복잡도를 다룰 것입니다. 파이썬으로 예시 코드를 작성하며, 실행 시간과 메모리 사용량 측정 방법도 소개합니다.
복잡도란
복잡도는 알고리즘의 성능을 나타내는 척도입니다. 복잡도는 시간 복잡도와 공감 복잡도로 나눌 수 있습니다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하고 있는지를 의미합니다.
동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘입니다.
즉, 복잡도를 측정함으로써 다음 2가지를 계산할 수 있습니다.
- 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양
효율적인 알고리즘을 사용했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계가 성립합니다. 메모리를 조금 더 많이 사용하는 대신에 반복되는 연산을 생략하거나 , 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있습니다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 많습니다.
실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션 기법이 있습니다.
*컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
시간 복잡도
시간 복잡도는 알고리즘의 성능을 나타낼 때 주로 사용되며, 입력 데이터의 크기에 따라 연산에 소요되는 시간을 설명합니다. 시간 복잡도의 대표적인 형태에는 상수 시간, 로그 시간, 선형 시간, 로그-선형 시간, 이차 시간, 지수 시간 등이 있습니다. 이들 복잡도에 대해 알아보고, 각각의 장단점을 알아보겠습니다.
상수 시간(Constant Time) - O(1)
상수 시간 복잡도는 입력 데이터의 크기와 관계없이 일정한 시간이 소요되는 경우입니다. 보통 배열의 요소 접근, 해시 테이블 연산 등이 포함됩니다.
장점: 입력 크기에 관계없이 빠른 연산이 가능하다.
단점: 복잡한 문제의 해결에 적합하지 않다.
def constant_time_example(lst, index):
return lst[index]
로그 시간(Logarithmic Time) - O(log n)
로그 시간 복잡도는 입력 데이터의 크기가 늘어남에 따라 로그 함수의 성질에 따라 증가하는 경우입니다. 보통 이진 탐색과 같은 알고리즘이 해당됩니다.
장점: 큰 데이터셋에서도 효율적인 연산이 가능하다.
단점: 코딩의 난이도가 높을 수 있다.
def binary_search(lst, target):
left, right = 0, len(lst) - 1
while left <= right:
mid = (left + right) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
선형 시간(Linear Time) - O(n)
선형 시간 복잡도는 입력 데이터의 크기에 비례하여 연산이 진행되는 경우입니다. 순차 탐색과 같은 알고리즘을 예로 들 수 있습니다.
장점: 코딩 난이도가 상대적으로 낮다.
단점: 데이터 크기가 클수록 성능이 떨어진다.
def linear_search(lst, target):
for i, value in enumerate(lst):
if value == target:
return i
return -1
로그-선형 시간(Log-linear Time) - O(n log n)
로그-선형 시간 복잡도는 입력 데이터의 크기와 로그 시간 복잡도를 곱한 것으로 표현됩니다. 병합 정렬과 같은 효율적인 정렬 알고리즘이 이에 해당됩니다.
장점: 큰 데이터셋에도 상대적으로 효율적인 연산이 가능하다.
단점: 코딩 난이도가 상대적으로 높다.
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
이차 시간(Quadratic Time) - O(n^2)
이차 시간 복잡도는 입력 데이터의 크기의 제곱에 비례하여 연산되는 경우입니다. 버블 정렬과 같은 비효율적인 정렬 알고리즘에 주로 나타납니다.
장점: 알고리즘 이해가 쉽다.
단점: 데이터 크기가 크면 성능이 급격하게 떨어진다.
def bubble_sort(lst):
for i in range(len(lst)):
for j in range(len(lst) - 1 - i):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
지수 시간(Exponential Time) - O(2^n)
지수 시간 복잡도는 입력 데이터 크기에 따라 지수함수처럼 급격하게 증가하는 경우입니다. 문제를 풀기 어려운 경우에 이런 복잡도가 나타납니다.
장점: 복잡한 문제를 완전 탐색할 때 사용할 수 있다.
단점: 데이터 크기가 증가함에 따라 급격히 성능이 나빠진다.
def fibonacci(n): # 재귀함수를 사용한 피보나치 수열
if n == 0:
return 0
if n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
각 시간 복잡도의 형태들은 서로 장단점이 다르며, 사용하는 알고리즘과 문제의 특성에 따라 성능이 크게 달라집니다. 시간 복잡도에 대한 이해를 바탕으로 알고리즘을 최적화할 수 있는 기법들을 학습하실 것을 추천드립니다.
공간 복잡도
공간 복잡도는 알고리즘의 성능을 평가할 때 사용되며, 알고리즘이 수행되는 동안 필요한 메모리 공간에 대한 설명입니다. 공간 복잡도의 대표적인 형태에는 상수 공간, 선형 공간, 이차 공간, 지수 공간 등이 있습니다. 이들 복잡도에 대해 알아보고, 각각의 장단점을 살펴보겠습니다.
상수 공간(Constant Space) - O(1)
상수 공간 복잡도는 입력 데이터의 크기와 관계없이 일정한 공간이 소요되는 경우입니다. 이러한 경우 공간 복잡도는 주로 단순 변수, 포인터 등에 사용됩니다.
장점: 입력 크기에 관계없이 일정한 메모리를 사용한다.
단점: 상황에 따라 배열이나 다른 자료구조가 필요한 경우 최적화가 어려울 수 있다.
def constant_space_example(a, b):
return a + b
선형 공간(Linear Space) - O(n)
선형 공간 복잡도는 입력 데이터의 크기에 비례하여 공간이 사용되는 경우입니다. 선형 공간 복잡도를 갖는 대표적인 예는 배열과 같은 자료구조입니다.
장점: 간단한 자료구조와 알고리즘에 적합하다.
단점: 데이터 크기가 클록 메모리 사용량이 증가한다.
def linear_space_example(n):
lst = [0] * n
for i in range(n):
lst[i] = i ** 2
return lst
이차 공간(Quadratic Space) - O(n^2)
이차 공간 복잡도는 입력 데이터 크기의 제곱에 비례하여 메모리 공간이 사용되는 경우입니다. 이차 공간 복잡도의 대표적인 예는 2차원 행렬입니다.
장점: 복잡한 자료구조와 알고리즘에 적용할 수 있다.
단점: 데이터 크기가 클수록 메모리 사용량이 급격히 늘어난다.
def quadratic_space_example(n):
matrix = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
matrix[i][j] = i * j
return matrix
지수 공간(Exponential Space) - O(2^n)
지수 공간 복잡도는 입력 데이터 크기에 따라 지수 함수럼 급격하게 공간이 필요한 경우입니다. 일반적으로 지수 공간 복잡도는 백트래킹 및 완전 탐색과 같이 복잡한 문제에 사용됩니다.
장점: 완전한 탐색 결과를 얻을 수 있다.
단점: 데이터 크기가 증가함에라 필요한 메모리 공간이 급격하게 증가한다.
def fib_recursive_with_cache(n, cache={}):
if n == 0:
return 0
if n == 1:
return 1
if n in cache:
return cache[n]
cache[n] = fib_recursive_with_cache(n 1, cache) + fib_recursive_with_cache(n - 2, cache)
return cache[n]
각 공간 복잡도 형태들의 장단점이 다르고, 사용하는 알고리즘과 문제의 특성 따라 최적의 메모리 사용량이 변화합니다. 공간 복잡도에 대한 이해와 관련 기법들을 학습하여 알고리즘을 최적화하는 데 도움이 되길 바랍니다.
결론
이 글에서는 복잡도에 대해 소개하였습니다. 시간 복잡도와 공간 복잡도는 코딩테스트에서 핵심적인 요소로 작용하며, 그 성능을 개선하기 위한 노력이 필요합니다. 본 글에서 소개한 내용이 코딩테스트에서 좋은 결과를 이끌어낼 수 있도록 도움이 되길 바랍니다. 당신의 성공을 응원합니다!
