Design Add and Search Words Data Structure 문제 Trie 풀이 복잡도 계산 개선 건의

[yhkee0404]

Design Add and Search Words Data Structure 문제 Trie 풀이의 시간 복잡도와 공간 복잡도가 일부 O(26^w)와 O(2^w)라고 계산된 것보다 더 줄여야 계산 가능성 설명에 유리할 것 같아서 제보 드립니다.

1. 풀이 3: Trie 2

AlgoDale/src/content/problems/design-add-and-search-words-data-structure.md

Lines 322 to 324 in 990d724

	트라이의 각 노드에서 최악의 경우 영어 알파벳 소문자 `26`개가 다음 글자가 될 수 있기 때문에 최대 `26`번의 재귀 호출이 일어날 수 있기 때문입니다.
	그리고 호출 스택은 찾으려는 단어에 들어있는 글자의 수와 비례해서 깊어지기 때문입니다.
	따라서 `search()` 메서드는 시간 복잡도는 `O(26^w)`가 되고, 공간 복잡도는 `O(w)`가 됩니다.

O(26^w)보다 더 낮은 상한이 있습니다.
문제에 다음 조건이 있으므로 경우를 나누어 셀 수 있습니다:

There will be at most 2 dots in word for search queries.

dot의 개수가 0인 최선의 경우 트라이의 각 노드에서 다음 글자의 Branch가 1개이므로 매번 1번의 재귀 호출이 일어납니다.
즉 O(w * 1^w) = O(w)입니다.

dot의 개수가 1이면 w번 중 1번은 Branch가 최악의 경우 26개일 때 다음 재귀 호출이 26번 일어날 수 있습니다.
그러나 그 1번을 제외한 나머지 (w - 1)번은 Branch가 1개라서 이전과 마찬가지로 매번 1번의 재귀 호출이 일어납니다.
따라서 O(w * 26 * 1^(w - 1)) = O(w)입니다.

최악의 경우는 dot의 개수가 2이면서 2번 다 Branch가 26개라면 다음 재귀 호출이 26번인 경우가 2번씩 있을 수 있습니다.
하지만 그 2번을 제외하면 여전히 1개의 Branch에 대해 매번 재귀 호출이 1번만 일어납니다.
그래서 O(w * 26^2 * 1^(w - 2)) = O(w)입니다.

다시 말해 O(26^w)을 O(w * (1 + 26 + 26^2)) = O(w)으로 줄일 수 있습니다.
그리고 문제의 다음 조건과 결합하면 w * (1 + 26 + 26^2) = 25 * (1 + 26 + 676) = 25 * 703 = 17575이라서 꽤 큽니다:

1 <= word.length <= 25

결론적으로 다음 조건에 따라 최대 17575 * 10^4번이라 아슬아슬합니다:

At most 10^4 calls will be made to addWord and search.

2. 풀이 2: Trie 1

AlgoDale/src/content/problems/design-add-and-search-words-data-structure.md

Lines 157 to 172 in 990d724

	def addWord(self, word: str) -> None:
	def dfs(node, idx):
	if idx == len(word):
	node["$"] = True
	return
	if "." not in node:
	node["."] = {"$": False}
	dfs(node["."], idx + 1)
	ch = word[idx]
	if ch not in node:
	node[ch] = {"$": False}
	dfs(node[ch], idx + 1)
	dfs(self.root, 0)

AlgoDale/src/content/problems/design-add-and-search-words-data-structure.md

Lines 183 to 184 in 990d724

	단어를 추가할 때, 재귀 함수 내에서 2번의 연쇄 호출이 일어나며, 호출 트리의 깊이는 글자의 수에 비례합니다.
	따라서 `addWord()` 메서드의 시간 복잡도와 공간 복잡도는 모두 `O(2^w)`이 됩니다.

이번에는 O(2^w)의 설명으로 충분합니다.
그런데 앞서 언급한 문제의 조건을 활용하면 약간의 변형으로 상한을 더 줄인 코드를 작성할 수 있습니다:

There will be at most 2 dots in word for search queries.

    def addWord(self, word: str) -> None:
        def dfs(node, idx, chance):
            if idx == len(word):
                node["$"] = True
                return

            if chance > 0:
                if "." not in node:
                    node["."] = {"$": False}
                dfs(node["."], idx + 1, chance - 1)

            ch = word[idx]
            if ch not in node:
                node[ch] = {"$": False}
            dfs(node[ch], idx + 1, chance)

        dfs(self.root, 0, 2)

역시 경우를 나누어 셀 수 있습니다.
dot의 개수가 0인 문자열, 1인 문자열, 2인 문자열이 생성됩니다.
dot의 개수가 0인 문자열은 1개, 1인 문자열은 26개, 2인 문자열은 26 choose 2 = 26 * 25 / 2 = 325개입니다.
그리고 문자열마다 최악의 경우 매번 새로운 w개의 노드를 중복 없이 처음으로 방문하거나 생성할 수 있습니다.

다시 말해 O(2^w)를 O(w * sum(k in [0, 2], 26 choose k)) = O(w * (1 + 26 + 325)) = O(352w) = O(w)으로 낮출 수 있습니다.
이번에는 이전 O(w) 풀이보다 w배 더 크게 계산되기 때문에 문제의 다음 조건과 결합하면 여유 없이 초과하는 이유를 설명할 수 있습니다:

1 <= word.length <= 25

그래서 최악의 경우 352w = 352 * 25 = 8800이라 8800 * 10^4 = 88 * 10^6번이면 시간은 나쁘지 않습니다:

At most 10^4 calls will be made to addWord and search.

그러나 공간은 적어도 4바이트씩 계산하더라도 4 * 88 * 10^6 B = 352 MB이므로 이 코드도 메모리 초과를 해결하지 못합니다.

한편 알고리즘 문제에서는 공간이 시간보다 4배 이상 비싼 경우가 있다는 교훈을 얻을 수 있군요!
1초의 시간은 허용하면서도 비슷한 복잡도의 공간 400MB 이상은 불허한다면요.

혹시 이 코드의 복잡도 상한을 더 낮춰서 계산하거나 이를 위해 추가로 코드를 변형할 아이디어가 있으신 분께서는 공유해 주시면 감사하겠습니다!