시간복잡도 실전 이해: 문자열 결합 연산 쓰지 마!

시간복잡도

 프로그래밍 언어에서 시간복잡도란 입력의 크기(N)에 따라 알고리즘이 얼마나 많은 "시간"을 소모하는지를 나타내는 척도이다. 표기법은 다양하나, 일반적으로는 O(1), O(n), O(log n), O(n^2) 등의 표기법을 사용한다.

 

실제 코드 시간복잡도 분석

import sys

N = int(sys.stdin.readline())
result = ""

for i in range(N // 4):
    result += "long "

result += "int"

print(result)

 백준 25314번 문항을 풀며 실제 내가 제출한 코드로, 입력값 N에 따라 "long "을 N // 4번 반복해서 결과 문자열에 추가한 후, 마지막에 "int"를 붙여서 출력하는 프로그램이다. 다음은 코드를 쪼개어 각 코드의 시간복잡도를 알아보겠다.

N = int(sys.stdin.readline())

 사용자 입력을 읽고 정수로 변환하는 부분으로, 시간복잡도는 O(1)이다.

result = ""

 result 변수의 문자열을 초기화하는 부분으로, 시간복잡도는 O(1)이다.

for i in range(N // 4):
    result += "long "

 for 반복문이 N // 4번 실행되는 부분으로, "long " 문자열을 result 변수에 추가하는 작업이다. 여기서 핵심은, 파이썬에서 문자열은 immutable 객체이므로, 매번 새로운 문자열을 생성하게 된다는 점이다. 참고로 문자열 결합 연산의 시간복잡도는 O(m)이다. 결합 연산된, 결과 문자열 길이인 m에 비례하여 시간이 소요된다.

 

 위에 제시된 for 반복문에서는 문자열 결합을 반복하고 있다. 즉, 첫 번째 결합에서는 O(5), 두 번째 결합에서는 O(10), 세 번째 결합에서는 O(15) ... 마지막 k번째 결합에서 소요되는 시간은 O(5k)가 된다.

 

 따라서, 전체 시간 복잡도는 T = O(5) + O(10) + O(15) + ... + O(5k)이다. 식을 간단히 정리하면 T = O(5) * (1 + 2 + 3 + ... + k)이 되고, 최종적으로는 T = O(5) * k(k + 1) / 2이다. 여기에 k = N // 4를 대입하면, 마침내 O(n^2)이라는 시간복잡도가 도출된다.

 

시간복잡도 개선을 위한 리스트 활용

import sys

N = int(sys.stdin.readline())
result = []

for i in range(N // 4):
    result.append("long ")

result.append("int")

print("".join(result))

 반복되는 문자열의 결합 연산 부분이 비효율적인 것이므로, 문자열 대신 리스트에 요소를 추가한 후, join() 메서드를 사용해 최종 문자열을 만들어내는 방식으로 코드를 수정해 보았다.

 

 그러나 조금 더 나아졌음에도, 반복문을 꼭 써야 할까라는 의문이 남았다. 문자열 대신 리스트를 사용한다는 것 역시도 메모리 사용 측면에서 불필요한 공간을 낭비하는 것일 수 있겠다는 생각이 들었다.

 

반복문 자체를 제거하고 리스트도 사용하지 않는다면?

import sys

N = int(sys.stdin.readline())
count = N // 4
result = "long " * count + "int"

print(result)

 실행 시간을 줄이기 위해 리스트와 반복문을 제거해 보았다. 이론상 시간복잡도 차이는 없을 수 있으나, 실제 사용에 있어서는 미세하게나마 더 나을 것이라 판단된다. 이제 실제로 실행 시간을 테스트해 볼 일만 남았다.

 

평균 실행 시간 실험

Test Case 1

Test Case 2

Test Case 3

 

결론

 리스트와 반복문을 제거했기 때문에 더 나아졌을 거라고 추측했던 3번의 경우, 1번 대비 아주 미세하게 향상되었다. 거의 무의미하다고 보아도 무방할 듯하다.

 

 이번 실험의 핵심은 문자열을 결합함에 있어서 문자열 결합 연산을 사용하기보다, 리스트를 만들어 요소를 추가하고 join() 메서드를 통해 하나의 문자열로 나타내는 것이 실행 속도 측면에서 훨씬 낫다는 점이다. (문자열 결합 연산은 편리하기 위해 존재할 뿐, 최적의 메서드가 아니다.)

 

 문자열을 결합하는데 문자열 결합 연산을 사용하면 비효율적이라니, 어떻게 보면 웃긴 일이다. 하지만 이러한 결과가 도출된 주요 원인은 문자열이 immutable 객체이기 때문에 그런 것이라는 점을 꼭 알고 가자.