개요

피보나치 수열을 생각해보면 시간복잡도가 O(2^n)인 것을 DP를 사용하면 O(n)까지 줄일 수 있다.
또한 리스트에서 특정 값을 제거하는 remove 메소드의 경우 시간복잡도는 O(n)이 된다.
반복문 아래 사용하면 O(n^2)까지 커진다.
그러나 set이나 dict를 사용하면 시간복잡도 O(1)로 값을 추가하고 삭제할 수 있기 때문에 시간 복잡도를 크게 줄일 수 있다.

이번 기회에 많이 사용하는 메소드들의 시간복잡도를 알아보자.

List 관련 메소드

파이썬의 List는 동적 배열로 구현되어있다.
메모리에 연속적으로 요소들이 저장되어있고 리스트가 꽉 차면 더 큰 메모리 공간을 할당하고 기존 데이터를 복사한다.
일반적으로 현재 크기보다 1.125배 큰 공간이라고 한다.

이러한 이유로 리스트의 인덱스를 통해 접근하는 경우 O(1)의 시간복잡도를 가지고
끝에 요소를 추가하는 경우O(1)
임의의 위치에 요소를 삽입하는 경우 그 뒤의 요소들을 이동시켜야하기 때문에 O(N)
새로운 배열을 할당하거나 모든 요소를 복사하는 데에는 O(N)의 시간복잡도를 가진다.

  • append()메소드는 단순히 끝에 초과하는 경우기 때문에 살펴본대로 O(1)의 시간복잡도를 가진다.
  • insert(i, x)는 뒤의 요소들을 하나씩 밀어야하기 때문에 최약의 경우 O(N)이 걸린다.
  • remove(x)리스트에서 처음으로 나오는 x를 제거하는 경우 해당 원소를 찾아야하는데 최약의 경우 O(n)이 걸린다.
  • pop(x)의 경우 특정 인덱스의 값을 제거하고 반환하는 메소드로 인덱스를 제거하면 insert와 같이 요소를 하나씩 당겨야한다. 따라서 최악의 경우 O(n)이 소요된다. 만약 별도의 인덱스를 넣어주지 않은 경우 가장 마지막 요소를 제거하게되는데 그럼 시간복잡도는 O(1)이 된다.
  • index(x)리스트에서 처음으로 나오는 x의 인덱스를 반환하는데 만약 값이 마지막에있다면 O(n)이 걸린다.
  • count(x)는 리스트 안에 있는 x의 개수를 세는 메소드로 리스트의 처음부터 끝까지 탐색해야하기 때문에 O(n)시간이 걸린다.
  • sort()는 리스트를 오름차순으로 정렬하는데 timsort 방식을 사용한다고 한다.(자세히는 모른다…) 그럼 O(nlogn)의 시간복잡도를 가진다.
  • reverse()는 리스트의 순서를 뒤집는데 각 원소에 한 번식 접근하고 순서를 바꿔야하기 때문에 O(n)이다.
  • extend(iterable)반복 가능한 객체의 모든 원소를 현재 리스트에 추가하는 메소드로 k개의 데이터를 추가한다면 반복하며 하나씩 추가하기 때문에 O(k)가 된다.
  • copy()는 리스트의 얕은 복사본을 반환하는 메소드로 모든 원소를 새로운 리스트에 옮기므로 시간복잡도는 O(n)
  • clear()리스트의 모든 원소를 메모리상에서 삭제하기 때문에 O(n)이 결린다.
  • slice()리스트의 일부분을 추출하여 새로운 리스트를 생성하는데 해당 구간의 원소들을 복사하므로 시간 복잡도는 O(k)가 나온다.
  • in 조건문에서 특정 값이 리스트안에 존재하는지 확인하는 명령어로 처음부터 끝까지 확인해야하므로 O(n)이 된다.

정리해보면 다음과 같다.

메소드명 시간복잡도
append(x) O(1)
insert(i, x) O(n)
remove(x) O(n)
pop(i) O(n)
pop() (마지막 원소) O(1)
index(x) O(n)
count(x) O(n)
sort() O(n log n)
reverse() O(n)
extend(iterable) O(k)
copy() O(n)
clear() O(n)
slice (lst[a:b]) O(k)
in (x in lst) O(n)

Set, Dict

리스트만큼이나 다른 자료형을 사용할 때도 많다. 예를 들어 dict라던지..
내부적으로 해시테이블이라는 구조를 사용하고 있는데
데이터를 삽입할 때 해시코드를 생성하고 마치 테이블처럼 해시코드 -> 값의 구조로, 저장하고 값을 입력하거나 제거하거나 변경, 확인할 때 시간복잡도는 모두 O(1)이 된다.

보다 구체적으로는 다음과 같다. Image

  1. 내부 배열 구조를 사용하여 각 슬롯에 키-값 쌍을 저장한다.
  2. 키를 해시함수를 통해 해시 값으로 변환한다. 이 때 해시값을 배열 크기로 나눈 나머지가 인덱스가 된다. 예를 들어 배열의 크기가 7이니 age의 해시 값인 8273을 7로 나눈 나머지는 6이된다. 여기에 값을 저장하는 것이다.
  3. 조회시 동일한 과정을 거쳐 인덱스를 계산하고 바로 접근한다.

Set

메소드 시간복잡도
add() O(1)
remove() O(1) (존재하지 않으면 KeyError 발생)
discard() O(1)
pop() O(1) (임의 요소 제거)
clear() O(n)
in (멤버십 검사) O(1)
union() O(len(s) + len(t))
intersection() (&) O(min(len(s), len(t)))
difference() (-) O(len(s))
symmetric_difference() (^) O(len(s) + len(t))
issubset() O(len(s)) (정렬된 경우 O(1)까지 가능)
issuperset() O(len(t))

Dict

메소드 시간복잡도
setitem (d[key] = value) O(1)
getitem (d[key]) O(1)
del d[key] O(1)
get() O(1)
pop() O(1)
popitem() O(1)
clear() O(n)
keys() O(n)
values() O(n)
items() O(n)
in (key in dict) O(1)
update() O(m) (m은 추가되는 키-값 쌍의 개수)

리펙토링 과정

프로그래머스의 여행경로 문제의 답안을 다음과 같이 작성했다.
1번 테스트 케이스에서 런타임 에러가 났고 문제에는 명시되어있지 않았지만 중복된 티켓이 있었다. 이걸 모른 상태로 set을 통해 방문 여부를 저장하고 확인했고 이번엔 list안에 티켓을 넣고 방문하였다면 삭제하는 방식으로 코드를 수정했다.
그 결과 런타임에러는 나지 않았지만 시간초과가 생겼다.

import copy

def dfs(start, save_arr, ticket_dict, visited_yet, length, answer):
    if start not in ticket_dict:
        return
    
    for end in ticket_dict[start]:
        if (start, end) in visited_yet:
            next_visited_yet = copy.deepcopy(visited_yet)
            next_arr = copy.deepcopy(save_arr)
            next_arr.append(end)
            next_visited_yet.remove((start, end))
            dfs(end, next_arr, ticket_dict, next_visited_yet, length, answer)
            
            if len(next_visited_yet) == 0:
                answer.append(next_arr)
                
def solution(tickets):
    answer = []
    first = "ICN"
    ticket_dict = {}
    length = len(tickets)
    visited_yet = []
    sorted_tickets = sorted(tickets, key=lambda x: (x[0], x[1]))
    
    for start, end in sorted_tickets:                            
        if start not in ticket_dict:
            ticket_dict[start] = []
        ticket_dict[start].append(end)
        visited_yet.append((start, end))
    
    dfs(first, [first], ticket_dict, visited_yet, length, answer)
    
    return min(answer)

DFS를 수행하며 기존 리스트를 복사하고 그 다음으로 넘겼다.
이렇게 하면 수형도처럼 가능한 경로를 기록하고 문제를 풀 수 있을 것으로 생각했다.

# 방문할 수 있는 최대 깊이까지 방문했다면
if start not in ticket_dict:
  return
...
# 모든 티켓을 다 사용했다면
if len(next_visited_yet) == 0:
  answer.append(next_arr)

결과는 시간초과.

문제의 dfs의 시간복잡도는 약 O(n!)가 된다.
그리고 매번 배열을 복사해서 넘겨주는 deepcopy의 시간복잡도는 O(n)이니 전체 시간 복잡도는 약 O(n!*n)이 된다.

아마 테스트케이스 1번이 큰 값의 티켓 수를 입력받는 테스트 케이스로 보인다.

어떻게 최적화시킬 수 있을까?
현재 코드의 문제는 2가지다.

  1. 중복된 티켓
  2. 재귀 호출의 경로마다 다른 값들을 저장

우선 중복된 티켓을 어떻게 처리할 수 있을까?
티켓 자체를 값으로 저장하는 것이 아니라 출발-도착을 묶어 하나의 키로 사용하고 값으로는 티켓의 개수를 저장하는 것이다. 이렇게 하면 중복된 값을 처리할 수도 있고 빠르게 조회할 수 있다.
출발, 도착을 튜플로 묶어 키로 사용하고 티켓의 개수를 추가해주면 만약 중복된 티켓이 있더라도 카운트할 수 있다.
만약 경로탐색에 실패했다면 복구시킨다.(백트래킹)

for start, end in sorted_tickets:
  if (start, end) not in visited:
    visited[(start, end)] = 0
  visited[(start, end)] += 1

또한 유효한 경로는 티켓을 모두 사용하는 경로, 알파벳순으로 더 빠른 경로가 되고 이미 정렬해두었기 때문에
여러 경로를 다 탐색할 필요 없이 가장 먼저 발견된 티켓을 모두 사용하는 경우가 정답이 된다.
그러니 answer 리스트를 하나만 두고 append와 pop을 반복하면서 별개의 리스트를 사용하지 않고 시간복잡도 O(1)로 처리할 수 있다.

[["ICN", "AAA"], ["DDD", "ICN"], ["ICN", "DDD"]]와 같은 경우가 있다고 했을 때 가장 먼저 AAA를 탐색하고 경로가 끊기니 경로탐색에 실패한 경우
재귀를 거슬러 올라가며 answer에 넣은 값들을 pop시킨다.

그럼 [“ICN”, “AAA”] -> 유효하지 않은 경로 ->[“ICN”]으로 복구시킨 다음 dfs(DDD)를 수행할 수 있는 것이다.(백트래킹)

def solution(tickets):
    answer = []
    visited = {}
    ticket_dict = {}
    sorted_tickets = sorted(tickets, key=lambda x: (x[0], x[1]))
    
    for start, end in sorted_tickets:
        if start not in ticket_dict:
            ticket_dict[start] = []
        ticket_dict[start].append(end)
    
    for start, end in sorted_tickets:
        if (start, end) not in visited:
            visited[(start, end)] = 0
        visited[(start, end)] += 1
        
    answer = []
    def dfs(current):
        answer.append(current)
        # 종료조건
        if len(answer) == len(tickets)+1:
            return True
        # 경로가 끊긴경우
        if current not in ticket_dict:
            return False

        for end in ticket_dict[current]:
            if visited[(current, end)] > 0:
                visited[(current, end)] -= 1
                if dfs(end):
                    return True
                visited[(current, end)] += 1
                answer.pop()
                
        return False
    
    dfs("ICN")
    return answer