[코딩테스트 문제 풀이 전략] 시간 복잡도 / 시간 복잡도 줄이는 Tip

1. 시간 복잡도란 ?

O(1) < O(logn) < O(n) < O(nLogn) < O(n^2) < O(2^n) < O(n!)

코드를 실행하면 원하는 기능을 수행하고 종료되기까지 시간이 소요되는데, 이를 더 효율적이고 빠르게 작동시키고 싶다면 어느 알고리즘이 더 효율적인지 비교할 수 있는 '기준'이 필요하다.

 

문제 해결에 필요한 입력 값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는데 걸리는 정도를 복잡도라고 한다.

 

그 중에서 얼마나 시간이 걸리는지는 시간 복잡도로 평가하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도로 평가한다.

 

코딩테스트에서는 가장 먼저 제시된 '제한 시간'과 '메모리 사용량'을 확인한 후, 조건에 맞게 실행되도록 자료구조와 알고리즘을 선택하고 문제를 풀어야 한다 ⭐️⭐️⭐️⭐️

 

🚨 프로그래머스에서는 특별한 언급이 없다면 제한 시간이 10초이다.

⭐️ 컴퓨터는 대략 1초에 1억 번(100,000,000 = 10^8)의 연산을 할 수 있다.

1천 = 1,000 = 10^3
1만 = 10,000 = 10^4
10만 = 100,000 = 10^5
100만 = 1,000,000 = 10^6
1000만  = 10,000,000 = 10^7

2^27 = 134,217,728

 

ex) 입력 값이 10만이고, 제한 시간이 10초라면 해당 문제는 O(n^2)보다 작은 O(nLogn)의 시간 복잡도를 가진 알고리즘으로 풀이해야 한다.

 

 

2. 시간 복잡도 계산하기

🚨 print() 함수는 실행 시간이 매우 긴 편에 속하기 때문에, print() 함수를 시간 측정에 사용하면 알고리즘의 효율과 관계없이 출력 시간이 지연되어 실행 시간이 약 3배 이상 차이가 난다.

 

자료구조의 시간 복잡도

내장 함수 시간 복잡도

 

결론 : 스택(Stack), 큐(Queue - deque), 힙(Heap), 집합(Set), 사전(Dictionary) 자료구조를 적극적으로 활용하여 시간복잡도를 줄일 수 있다 ✨

 

3. 시간 복잡도 줄이는 코드 작성법 ⭐️⭐️

시간 복잡도 예측 방법을 대략 알았다면 이번에는 더 빠르게 실행하는 코드를 작성하는 방법을 알아보자.

 

지금까지의 알고리즘 시간 복잡도 줄이는 방법은 '입력 개수를 보고 그에 맞는 적절한 알고리즘을 선택한다', '자료형이나 자료구조를 적극적으로 사용한다', '반복문을 줄인다' 등 직접적으로 연산량 자체를 줄이는 방법만 살펴보았다.

 

하지만 코딩 테스트는 그렇게 만만하지 않다. 이 모든 사항을 고려했음에도 불구하고 시간초과가 발생하거나 예상치 못한 입력값으로 실패하는 경우가 많다.

 

이번에는 파이썬에서 주의해야 할 점과 시간 복잡도를 줄이도록 코드를 작성하는 방법에 대해 알아보겠다.

 

3-1. readline() : 입력 속도를 빠르게

import sys
input = sys.stdin.readline

 

코딩 테스트마다 입력 값을 제공하는 방법이 다르다. 프로그래머스의 경우에는 입력 값을 모두 주고, 원하는 기능만 구현하면 되는 함수 형태로 시작 코드가 주어지지만, 실제 테스트를 볼 때는 입력 값을 받는 코드도 직접 구현해야 하는 경우가 있다.

 

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

 

파이썬으로 값을 받을 때는 input()을 사용한다고 배웠지만, 이 함수는 데이터가 많을수록 효율이 떨어지기 때문에 받은 문자열을 다시 쪼개야 하더라도 readline() 함수를 사용하여 빠르게 읽어오는 것이 훨씬 효율적이다.

 

다만, sys.stdin.readline은 개행문자를 자동으로 삭제해주지 않기 때문에 'rstrip()'을 사용해서 처리해줘야 한다.

 

3-2. 리스트 곱셈 : 초기화와 할당을 빠르게(시간복잡도 X)

arr1 = [0 for _ in range(1000)]
arr2 = [0] * 1000

 

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

 

이때 리스트에 곱셈 연산을 하여 초기화와 할당을 동시에 진행하도록 만들 수 있다. (모두 O(n) 시간이 걸리는데 왜 넣은건지 모르겠음)

 

3-3. 문자열 합치기 : "".join()을 쓰고 +는 사용하지 말자

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

 

다른 언어와는 다르게 파이썬의 문자열은 내용을 변경할 수 없기 때문에 +로 합칠 경우 각각의 문자열을 새로운 메모리에 복사하여 새 문자열을 만들기 때문에 사실상 시간 복잡도가 O(n^2)정도가 된다.

 

따라서 "".join()을 사용해서 문자열을 합쳐야 이러한 계산 과정을 거치지 않고 빠르게 합칠 수 있다.

 

3-4. 조건문 연산 줄이기 : 짧은 것부터 먼저 계산하자

if 조건문에서 다중 조건을 사용하면 두 조건 중 빠르게 실행되는 쪽을 앞쪽으로 배치하는 것이 유리하다.

 

and 연산을 할 때 앞의 연산 결과가 False라면 뒤의 연산은 실행하기 않고 바로 넘어가며, or 또한 앞의 연산 결과가 True라면 뒤의 연산을 실행하지 않기 때문이다.

 

3-5. 슬라이싱 : 불필요한 연산을 최소로

a = [1,2,3,4,5] 

sliced = a[start:end:step]

 

리스트, 튜플, 문자열과 같은 연속(Iterable) 자료형의 범위를 지정해 일부분만 추출하는 '슬라이싱' 기능으로 많은 코드를 절약할 수 있다.

 

start는 시작 위치에서 자신을 포함하지만, end는 끝낼 위치에 자신을 포함하지 않으며, 시작 위치를 생략하면 가장 첫번째부터 끝 위치를 생략하면 가장 마지막까지로 인식한다.

 

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

 

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

 

3-6. 표준 라이브러리 활용하기 : 속도와 안전성 모두 잡기

다음은 자주 사용하는 자료구조나 계산할 때 사용할 수 있는 라이브러리들 이다.

 

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

파이썬 - Collections 모듈 3종 정리

[Python] 순열과 조합 라이브러리 itertools

15_math 모듈(Math Module)

[파이썬] 이진 탐색 구현을 도와주는 bisect 라이브러리에 대해 알아보자!

파이썬 - 이진탐색 필수 bisect

 

교재와 별개로, 개인적으로 2진수 관련 문제는 따로 2진수화 함수를 구현할 필요 없이 파이썬에서 지원하는 bin() 함수를 사용하면 유용하다. ✨

파이썬에서 2진수, 8진수, 16진수 다루기

operator — Standard operators as functions

 

3-7. 리스트 컴프리헨션(시간복잡도 X)

data = [x for x in range(1,11)]
data2 = [x for x in range(1,11) if i % 2 == 0]
data3 = [x for x in range(1,11) if i % 2 == 0 if i % 5 == 0]
data4 = [x*2 for x in range(1,11)]

 

리스트 컴프리헨션을 사용하면 리스트의 선언과 할당이 한 번에 이루어지기 때문에 간단하고 짧은 문장으로 모든 일을 해결할 수 있다. 물론 튜플, 집합, 사전 자료형 모두 사용할 수 있다.

 

이 외에도 조건문을 추가하여 원하는 값만 추출하거나 값을 변형할 수도 있다.(if문 뒤에 또 다시 if문을 중첩할 수 있고 이때 if문은 and로 취급)

 

즉, 선언 - 할당 - 재구성 과정을 단 한줄로 끝낼 수 있으며, 시간 복잡도는 O(n)으로 여러 줄로 바꿔써도 차이가 없기 때문에 간편하게 데이터를 선언 및 할당할 수 있다.

 

3-8. 데이터 돌려쓰기 : 중복 피하기

불필요한 연산 낭비를 막기 위해서는 항상 의미없는 데이터의 복사나 연산이 발생했는지 확인해야 한다. ⭐️

def solution(data):
	answer = data
    
    for i in range(len(answer)):
    	temp = answer[i] * answer[i]
        answer[i] = temp
    
    return answer

 

이처럼 필요하지 않은 변수를 항상 할당하는 방식으로 코드를 작성하면 수정하지 말아야 할 데이터를 수정하는 등의 문제가 발생할 수 있다.

 

def solution(data):
	return [i*i for i in data]

 

이렇게 리스트 컴프리헨션을 사용하여 핵심은 유지하되 중복되는 연산이나 값의 복사로 인한 문제를 방지할 수 있다.