파이썬에서 시간 복잡도 줄이기

자료구조와 알고리즘을 공부하면서 시간 복잡도$_{time \space complexity}$에 대해 배웠을 것이다.

 

시간 복잡도를 이해하고 예측할 수 있으면 더 빠르게 실행되는 코드를 작성할 수 있다.

 

이번 포스팅에서는 파이썬에서 시간 복잡도를 줄이는 방법에 대해 알아볼 것이다.

 

파이썬에서 같은 결과를 내더라도 사용하는 함수에 따라 실행 속도가 달라질 수 있다.

 

예를 들어, 특정 자료형이나 자료구조를 적극적으로 활용하고, 반복문을 최소화하는 등의 방법으로 직접적인 연산량을 줄일 수 있다.

 

하지만 이런 사항들을 모두 고려하더라도 시간 초과가 발생하거나 예상치 못한 입력값으로 인해 실패하는 경우가 생길 수 있다.

 

파이썬에서 주의해야 할 점과 시간 복잡도를 줄이도록 코드를 짜는 방법에 대해 알아보자.

 

 

입력 값 받기

실제 코딩 테스트에서는 입력 값을 받는 코드를 직접 구현해야 하는 경우가 많다.

 

이럴 때는 sys 모듈의 readline()을 활용하는 것이 좋다.

 

다음은 readline()을 사용하는 예제이다.

import sys
input = sys.stdin.readline

n = int(input().strip())
data = list(map(int, input().strip().split()))

이렇게 받은 문자열을 다시 쪼개더라도 readline() 함수를 사용해 읽어오는 것이 훨씬 효율적이다.

 

특히 코딩 테스트에서는 시간 효율성이 중요한 만큼 이러한 작은 차이가 전체 실행 시간에 큰 영향을 미칠 수 있다.

 

 

리스트 곱셈

기본적으로 배열을 다룰 때는 동적으로 다루지만 가끔은 미리 할당해 놓은 고정 배열에다 계산해야 하는 경우가 있다.

 

이럴 때 리스트에 곱셈 연산을 활용해 초기화와 할당을 동시에 진행할 수 있다.

 

파이썬에서는 리스트에 곱셈 연산을 사용해 동일한 값으로 초기화된 리스트를 간편하게 생성할 수 있다.

 

예를 들어, 크기가 10인 리스트를 모두 0으로 초기화하고 싶다면 다음과 같이 작성할 수 있다.

array = [0] * 10

이 방법은 반복문을 사용해 리스트를 초기화하는 것보다 훨씬 간결하고 효율적이다.

 

다차원 리스트를 초기화할 때도 유용하다.

 

예를 들어, 2차원 리스트를 초기화할 때는 다음과 같이 작성할 수 있다.

array = [[0] * 3 for _ in range(3)]

다차원 리스트는 리스트 컴프리헨션(list comprehension)를 사용해 각 행을 개별적으로 초기화해야 한다.

 

그렇지 않으면 모든 행이 동일한 참조를 가리키게 되어 예기치 않은 결과가 발생할 수 있다.

 

 

문자열 합치기

문자열을 합칠 때에는 문자열의 개수가 정말 적은 것이 아니라면 + 연산자를 사용하면 안 된다.

 

다른 언어와는 다르게 파이썬의 문자열은 불변$_{immutable}$이기 때문에 + 연산자로 문자열을 합칠 경우 각각의 문자열을 새로운 메모리에 복사해 새 문자열을 만든다.

 

이 과정에서 시간 복잡도가 $O(n^2)$ 정도가 되어 비효율적이다.

 

따라서 ‘’.join() 메서드를 사용해 문자열을 합쳐야 한다.

 

join() 메서드는 반복 가능한$_{iterable}$ 객체의 요소들을 하나의 문자열로 결합시켜 새로운 메모리 할당을 최소화한다.

 

시간 복잡도가 O(n)으로 줄어들어 훨씬 효율적이다.

# Bad Case
result = ""
for s in ["Hello", "World", "Python"]:
    result += s

# Good!
strings = ["Hello", "World", "Python"]
result = ''.join(strings)

join() 메서드는 특히 반복적으로 문자열을 결합해야 할 때 유용하다.

 

큰 텍스트 파일을 읽어서 한 줄씩 처리하고 이를 하나의 문자열로 합칠 때 join()을 사용하면 성능이 향상된다.

 

추가로 문자열 포매팅을 할 때도 유사한 원칙이 적용된다.

 

많은 문자열을 결합하는 작업이 필요할 경우 f-string이나 format() 메서드를 사용하는 것이 좋다.

# f-string
name = "Alice"
age = 30
greeting = f"Hello, my name is {name} and I am {age} years old."

# format()
greeting = "Hello, my name is {} and I am {} years old.".format(name, age)

 

 

조건문 연산 줄이기

조건문에서 다중 조건을 사용할 때는 두 조건 중 실행 속도가 빠른 쪽을 앞쪽에 배치하는 것이 유리하다.

 

and 연산자와 or 연산자는 단축 평가$_{short-circuit \space evaluation}$를 수행하기 때문에, 첫 번째 조건의 결과에 따라 두 번째 조건을 실행할지 여부가 결정된다.

 

and 연산자는 첫 번째 조건이 False인 경우, 두 번째 조건을 평가하지 않고 바로 False를 반환한다.

 

and 연산에서 첫 번째 조건이 거짓일 가능성이 높거나 평가가 빠른 조건을 배치하면 성능을 최적화할 수 있다.

if is_simple_check() and is_heavy_computation():
    # do something

or 연산자는 첫 번째 조건이 True인 경우, 두 번째 조건을 평가하지 않고 바로 True를 반환한다.

 

or 연산에서 첫 번째 조건이 참일 가능성이 높거나 평가가 빠른 조건을 배치하는 것이 좋다.

if is_simple_check() or is_heavy_computation():
    # do something

이와 같은 최적화는 특히 조건문이 반복문 내에서 사용될 때 중요하다.

 

반복문 내에서 불필요한 조건 평가를 줄임으로써 전체 실행 시간을 크게 단축할 수 있다.

 

복잡한 조건문을 간결하게 작성하기 위해 파이썬의 all(), any() 함수도 활용할 수 있다.

 

이 함수들은 전달받은 iterable의 모든 요소가 참인지, 하나라도 참인지 평가한다.

conditions = [is_simple_check(), is_heavy_computation()]

if all(conditions):
    # 모든 조건이 참인 경우

if any(conditions):
    # 하나라도 조건이 참인 경우

 

 

슬라이싱

슬라이싱은 리스트, 튜플, 문자열과 같은 자료형에서 범위를 지정해 일부분만 추출하는 기능이다.

 

슬라이싱을 활용하면 많은 코드를 절약할 수 있어 개발하기 편리하다.

 

예를 들어, a 리스트가 있다고 하면 a[start:end:step] 형식으로 슬라이싱을 사용할 수 있다.

 

여기서 start는 시작 위치(포함)이며, end는 끝낼 위치(포함하지 않음)이다.

a = [1, 2, 3, 4, 5]
print(a[1:4])  # [2, 3, 4]

 

숫자를 생략할 수도 있는데, 시작 위치를 생략하면 리스트의 첫 번째 요소부터 시작하고 끝 위치를 생략하면 리스트의 마지막 요소까지 포함된다.

# 시작 위치 생략
print(a[:3])  # [1, 2, 3]

# 끝 위치 생략
print(a[2:])  # [3, 4, 5]

step은 start부터 end까지의 범위에서 step 만큼 건너뛰면서 값을 가져온다.

print(a[::2])  # [1, 3, 5]

특이사항으로는 음수를 사용할 수 있으며 양수 계산법과는 반대로 맨 끝에서부터 인덱스를 탐색한다.

print(a[-3:])  # [3, 4, 5]
print(a[:-1])  # [1, 2, 3, 4]

슬라이싱은 한정된 자료형에만 사용할 수 있는 제한적인 기능처럼 보일 수 있지만, 실제로는 연속된 자료형이라면 어떤 것이라도 슬라이싱할 수 있다.

 

예를 들어, 문자열에서도 슬라이싱을 사용할 수 있다.

s = "Hello, World!"
print(s[7:12])  # 출력: World

2, 3차원 배열도 가능하다.

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print([row[:2] for row in matrix])  # [[1, 2], [4, 5], [7, 8]]

for 문에서도 사용할 수 있다.

# 슬라이싱을 활용한 for 문
for value in a[1:4]:
    print(value)
# 2
# 3
# 4

시간 복잡도를 줄일 때는 직접적으로 연산량을 줄이는 것도 중요하지만, 슬라이싱으로 하나의 변수를 최대한 활용하는 것 또한 실행 속도를 높이는 데 많은 도움이 된다.

 

 

표준 라이브러리 활용

필요한 기능을 코드로 직접 구현할 경우 고려해야 할 사항이 많다.

 

입력값을 충분히 고려했는지, 실행 도중에 오류는 없는지, 효율은 따졌는지 등 작성한 코드를 사용하기 위해 많은 검증이 필요하다.

 

하지만 표준 라이브러리를 사용하면 검증할 필요가 없어지므로 이런 문제를 모두 해결할 수 있다.

 

단, 많은 코딩테스트에서 외부 라이브러리를 제한하므로, 표준 라이브러리는 적극적으로 사용하되 외부 라이브러리는 사용하지 않는 것이 좋다.

 

아래는 자주 사용되는 표준 라이브러리와 그 기능들이다.

 

heapq

heapq는 이진 트리 기반의 최소 힙 자료구조를 제공한다.

 

힙은 항상 정렬된 상태로 값의 추가 및 삭제가 이루어진다.

 

우선순위 큐나 최단 거리 알고리즘을 구현할 때 많이 사용된다.

import heapq

heap = []
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)

print(heapq.heappop(heap)) # 1

collections

Counter는 연속된 자료에서 동일한 원소가 몇 개인지 확인할 때 유용하다.

deque는 덱(양방향 큐)을 구현하는 자료구조로 양 끝에서 추가 및 삭제가 가능하다.

from collections import Counter, deque

# Counter
counter = Counter([1, 1, 2, 3, 3, 3])
print(counter)  # Counter({3: 3, 1: 2, 2: 1})

# deque
d = deque([1, 2, 3])
d.appendleft(0)
d.append(4)
print(d)  # deque([0, 1, 2, 3, 4])

itertools

itertools는 경우의 수 문제에 사용한다.

 

순열 permutations, 조합 combinations, 중복순열 permutations_with_replacement, 중복조합 combinations_with_replacement 등에 사용한다.

from itertools import permutations, combinations

# 순열
perm = permutations([1, 2, 3], 2)
print(list(perm))  # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

# 조합
comb = combinations([1, 2, 3], 2)
print(list(comb))  # [(1, 2), (1, 3), (2, 3)]

math

math 모듈은 복잡한 수학 연산을 쉽게 수행해주는 라이브러리이다.

 

최대공약수 gcd, 최소공배수 lcm, 팩토리얼 factorial, 제곱근 sqrt, 로그 log 등을 계산한다.

 

파이, 자연상수와 같은 상수도 존재한다.

import math

print(math.gcd(48, 180))  # 12
print(math.factorial(5))  # 120
print(math.sqrt(16))  # 4.0

bisect

bisect 모듈은 이진 탐색 기능을 제공한다.

 

정렬된 데이터 내에서 특정 원소가 삽입될 위치를 찾거나, 특정 범위 안에 원소가 몇 개 존재하는지 확인한다.

import bisect

# 정렬된 리스트에 원소 삽입 위치 찾기
a = [1, 2, 4, 5]
bisect.insort(a, 3)
print(a)  # [1, 2, 3, 4, 5]

# 특정 원소의 위치 찾기
index = bisect.bisect_left(a, 3)
print(index)  # 2

리스트 컴프리헨션 vs 제너레이터

리스트에 1부터 10까지 데이터를 for문을 사용해 넣는다면 아래와 같은 코드를 작성할 수 있다.

data = []
for i in range(1, 11):
    data.append(i)

이 코드를 한 줄로 줄이려면 컴프리헨션$_{comprehension}$을 사용하면 된다.

[i for i in range(1, 11)]

컴프리헨션을 사용하면 선언과 할당이 한 번에 이루어지기 때문에 간단하고 짧은 문장으로 모든 일을 해결할 수 있다.

 

여기서는 리스트를 주로 다루기 때문에 리스트 컴프리헨션이라고 부르지만 튜플, 셋, 딕셔너리 같은 자료형에서도 모두 사용할 수 있다.

 

리스트 컴프리헨션은 다음처럼 사용한다.

[(변수 표현식) for (사용할 변수) in (순회 가능한 연속적인 데이터)]

조건문을 추가해 원하는 값만 추출할 수 있다. 예를 들어, 짝수만 뽑고 싶다면 뒤에 if문을 추가하면 된다.

[i for i in range(11) if i % 2 == 0]

컴프리헨션을 사용하면 선언, 할당, 재구성 과정을 단 한 줄에 끝낼 수 있어 간편하게 데이터를 준비할 수 있다.

 

그러나 데이터가 100만개 있을 때 모든 데이터를 한 번에 생성하기 때문에 공간 복잡도를 고려해야 할 수도 있다.

 

편리한 기능은 대부분 공간 복잡도가 커지는 경우가 많다.

 

이에 대한 대응책으로 제너레이터$_{generator}$를 사용할 수 있다.

 

제너레이터는 이터레이터$_{iterator}$ 형태의 값을 반환하는 함수로, 실행 중 yield를 만나면 값을 반환하고 next()가 호출되기 전까지 대기한다.

 

1부터 10까지의 데이터를 생성하는 코드를 제너레이터로 바꾸려면 컴프리헨션을 괄호로 감싸면 된다.

(i for i in range(11))

직접 next를 호출해야 1, 2, 3…의 값이 반환된다.

 

이 때 이전 값은 메모리에 남지 않으며, 필요하다면 list() 같은 함수를 통해 실행되는 값을 저장해야 한다.

gen = (i for i in range(1, 11))
print(next(gen)) # 1
print(next(gen)) # 2

제너레이터의 장점은 많은 양의 데이터를 처리할 때도 메모리 사용량이 고정된다는 점이다.

 

제너레이터는 데이터를 필요할 때마다 생성하므로 컴프리헨션보다 메모리를 절약할 수 있다.

 

반대로, 실행하기 전까지는 데이터를 갖지 않으므로 결과 정보를 저장하려면 실행 비용이 들고 추가적인 변수를 사용해야 하는 단점이 있다.

 

상황에 따라서 리스트 컴프리헨션을 사용할지 제너레이터를 사용할지 선택해야 한다.

 

데이터 양이 적고 메모리 사용량이 크게 문제가 되지 않는 경우 리스트 컴프리헨션을 사용하고,

 

데이터 양이 많고 메모리 사용을 최소화해야 하는 경우 제너레이터를 사용하면 될 것 같다.

 

 

references

product.kyobobook.co.kr

프로그래머스 코딩 테스트 문제 풀이 전략: 파이썬 편 | 김범수 - 교보문고