이진수를 트라이 구조로 저장한다는 발상이 신기한 트라이 응용문제입니다. 트라이 구조를 활용해 저장하고, 최대치를 탐색하면 일반적인 탐색에 비해 효율이 높습니다.

트라이

간단히 딕셔너리로 트라이구조를 구현했습니다.

그 후, compare 함수를 통해 해당 위치의 trie에 반대되는 이진수가 있는 경우 1을 더하여 내려가는 방식으로 구현했습니다.

최대 길이를 미리 구해두어 zfill메서드를 통해 길이을 동일하게 만들었습니다. 이를 통해, 자리수가 차이나는 숫자 간에도 추가적인 예외처리 없이 비교할 수 있습니다.

마지막으로, compare함수를 모든 숫자에 적용해보며 ans의 최대값을 찾아 출력합니다.

트라이

간단히 딕셔너리로 트라이구조를 구현했습니다.

그 후, search 함수를 통해 해당 위치의 trie의 원소가 1개만 있는 경우 카운트를 올리지 않고 내려가고, 그 이상인 경우 카운트를 올려 내려가는 방식으로 구현했습니다.

그리고,

3
h
he
hi

와 같이 첫 철자가 하나인 경우를 처리하기 위해 trie의 원소 개수가 1인 경우, 해당 N만큼 더해 예외 처리를 수행했습니다.

트라이

간단히 딕셔너리로 트라이구조를 구현했습니다.

단어를 저장하기 전에 search 함수를 통해 트라이가 존재하는지 확인한 후, 저장되지 않은 지점에서 출력해 정답을 출력합니다.

이후, 트라이에 저장하는 insert 함수를 통해 닉네임을 저장합니다. 0을 통해 단어의 끝을 나타내고, 중복되는 단어는 0에 카운트를 저장해 중복 닉네임을 검출합니다.

트라이

간단히 딕셔너리로 구현한 트라이 구조로 단어들을 저장하고, depth를 저장해 재귀하며 조건에 맞게 출력하는 함수를 구현해 간단하게 출력할 수 있습니다.

트라이

문자 검색을 효율적으로 구현하기 위해 트라이를 활용했습니다. 이를 별도의 클래스 구현 없이 딕셔너리만 활용했습니다. 문자열의 끝을 0으로 두어 0이 있는 경우 문자열의 끝이고, 여기에 전체 문자열을 저장해 백트래킹 시 별도의 저장이 필요 없도록 설계했습니다.

백트래킹

퍼즐 내에 있는 단어를 찾아가는 내용이기 때문에, 백트래킹을 통해 현재 위치에서 탐색을 통해 갈 수 있는 곳과, 지금까지 탐색을 진행한 trie의 위치를 저장하고, 현재 위치가 문자열의 끝인 경우 answer에 담습니다.

비트마스킹

퍼즐 내에서 중복된 블록은 사용이 불가능하기 때문에, 방문 처리가 필요합니다. 4*4의 배열을 사용하기 때문에 비트마스킹으로 구현하면 $$2^{16}$$ 범위 내에서 방문처리가 가능하기 때문에 visit 배열을 구성하는 것보다 공간적으로 더욱 효율적인 구현이 가능합니다.

트라이는 문자열 탐색을 위해 주로 사용되는 트리 구조입니다. 철자를 나눠 저장함으로써 빠른 검색과 공간 효율성이 높은 구조로, 검색어 추천 등 다양하게 사용될 수 있습니다.

구현방식

이를 구현하기 위해 Python에서 위와 같은 방식으로 클래스를 만들어 구현하는 경우가 많은데, 클래스 구현이 어렵거나 익숙하지 않은 사람들을 위해서 간단한 구현 방법을 같이 설명해보려고 합니다.

일반적인 트리도 파이썬에서 리스트와 인덱스 기반으로 구현하듯이, 트라이도 딕셔너리를 기반으로 간단하게 구현할 수 있습니다.

1. 클래스를 통한 구현

Class Node:
    def __init__(self,data):
        self.data = data
        self.child = dict()
        self.is_end = False

Class Trie:
    def __init__(self):
        self.root = Node("")

    def insert(self, word):
        now = self.root

        for char in word:
            if char not in now.child:
                now.child[char] = Node(char)
            now = now.child[char]
        now.is_end = True

    def find(self, word):
        now = self.root
        for char in word:
            if char not in now.child:
                return False
            now = now.child[char]
        if now.is_end:
            return True
        return False

2. 딕셔너리를 통한 구현

def insert(word):
    now = trie
    for char in word:
        now = now.setdefault(char, dict())
    now["is_end"] = True

def find(word):
    now = trie
    for char in word:
        if char not in now:
            return False
        now = now[char]
    if "is_end" in now:
        return True
    return False

trie = dict()

insert("trie")
insert("tri")
insert("tire")
insert("tree")

print(find("tree")) # True
print(find("tre")) # False 
print(trie) 
'''
{
    "t": {
        "i": {
            "r": {
                "e": {
                    "is_end": True
                }
            }
        },
        "r": {
            "i": {
                "is_end": True,
                "e": {
                    "is_end": True
                }
            },
            "e": {
                "e": {
                    "is_end": True
                }
            }
        }
    }
}
'''

트라이에 문자열을 입력하고, 찾는 함수를 위와 같이 짧은 함수로 구현할 수 있습니다.

이후, 추가적인 메서드들의 구현 또한 딕셔너리를 기반으로 생각해서 구현하면 편합니다.

그리고 딕셔너리를 기반으로 구현하는 경우, Node 와 같은 자체 구현 클래스와 다르게 pprint를 통해 시각적으로 확인하기 편하다는 점 또한 장점입니다.

아래에는 간단한 트라이 문제들을 이러한 방식으로 구현하여 풀이한 것을 소개합니다.

관련 문제

[백준/python] 14725 개미굴 [백준/python] 16934 게임 닉네임 [백준/python] 9202 Boggle [백준/python] 5670 휴대폰 자판 [백준/python] 13505 두 수 XOR

def backtrack(i=1):
    global cnt
    if i == N+1:
        if all(i for i in arr):
            cnt += 1
        return

    if i == t:
        backtrack(i+1)
    else:
        for j in range(N*2):
            if arr[j]: continue
            if j+i+1 >= 2*N: continue
            if arr[j+i+1]: continue

            arr[j] = arr[j+i+1] = i
            backtrack(i+1)
            arr[j] = arr[j+i+1] = 0


N, X, Y = map(int, input().split())

arr = [0]*N*2

t = (Y-X-1)
arr[X-1] = arr[Y-1] = t

cnt = 0
backtrack()
print(cnt)

참고하여 개선한 풀이

def backtrack(idx=1):
    global cnt
    if idx == 2*N+1:
        cnt += 1
        return

    if arr[idx] !=0:
        backtrack(idx+1)
        return

    for i in range(1, N+1):
        if not visit[i] and idx+i < 2*N and not arr[idx+i+1]:
            arr[idx]=arr[idx+i+1]=i
            visit[i]=1
            backtrack(idx+1)
            arr[idx]=arr[idx+i+1]=visit[i]=0

N,X,Y = map(int,input().split())

arr = [0]*(2*N+1)
visit = [0]*(N+1)

t = Y-X-1
arr[X] = arr[Y] = t
visit[t] = 1

cnt = 0
backtrack()
print(cnt)

백트래킹

백트래킹을 통해 특정 패턴의 수열을 찾는 문제입니다. 제가 접근한 방법은 idx에 저장된 숫자를 하나씩 올려가며 arr의 각 자리를 순회하면서 그 자리가 비어있다면 넣어 모두 배치된 경우 카운트를 올리는 방식이었습니다.

이렇게 접근했을 때 5244ms 의 시간이 발생했고, 다른 풀이의 제출보다 훨씬 오래 걸리는 것 같아 어떻게 해야 더 빠르게 해결할 수 있는지 궁금하여 다른 사람들의 풀이를 찾아보았습니다.

결론적으로, 반대로 접근을 하면 훨씬 쉽게 해결되는 문제였습니다. 배열이 아닌 숫자를 순회하면서 접근하는 경우 훨씬 빠르게 답이 도출되었습니다.

별 차이도 없는 것 같은데 유의미한 결과를 만들어 내는 것이 신기했고, 이후에는 단순히 가지치기에만 더 신경을 쓰는 것이 아니라 다양한 관점에서 생각해보는 것도 필요하다고 느꼈습니다.

백트래킹

중복을 허용하지 않고 모든 나올 수 있는 애너그램을 만드는 문제입니다. 문제 자체는 N과 M (9) 문제와 비슷하다고 생각해서 같은 방식으로 접근했으나, 시간 초과가 발생했습니다.

문자열의 길이가 최대 20이기 때문에 같은 방식으로 문제 풀이가 불가능함을 깨닫고, 딕셔너리를 활용해 data변수에 각 문자의 개수를 순서대로 저장해두고, 백트래킹을 통해 남은 개수를 관리하는 방식을 사용했습니다.

import sys
input = sys.stdin.readline

arr = []
for _ in range(int(input())):
    s,e = map(int,input().split())
    arr.append((s,1))
    arr.append((e,-1))

tmp,ans = 0,0
for k,v in sorted(arr):
    tmp += v
    ans = max(ans,tmp)
print(ans)

2. 딕셔너리를 활용한 방법

import sys
input = sys.stdin.readline

data = dict()
for _ in range(int(input())):
    s,e = map(int,input().split())
    data[s] = data.get(s,0)+1
    data[e] = data.get(e,0)-1

tmp,ans = 0,0
for key in sorted(data):
    tmp += data[key]
    ans = max(ans,tmp)
print(ans)

들어오는 입력이 최대 1,000,000개 이므로, 이중 for문만 해도 1조 번의 연산이 필요하기에 시간에 대한 고려는 필수적입니다.

스위핑 테크닉을 활용해 시작점이면 +1, 도착점이면 -1을 셈하며 한번의 순회로 계산이 마무리되게 할 수 있습니다.

이렇게 계산하면, $$O(N log N)$$의 시간복잡도가 발생합니다.

또한, 100만개의 입력에서 겹치는 숫자 또한 존재할 수 있으므로, 일반적인 경우에 딕셔너리를 활용해 각 시작점과 끝점의 좌표에 더해질 값을 미리 계산해두고 순회를 한다면 더 적은 양의 순회로 계산을 마칠 수 있습니다.

이로 인해 공간복잡도 또한 개선된 모습을 보여주었습니다.

다익스트라 알고리즘

이 문제는 1번 노드에서 N번 노드까지 갈 때의 최단 거리를 구하는 문제로, 다익스트라 알고리즘을 활용해야 합니다.

heapq자료구조와 distance 배열을 활용하여 다익스트라 함수를 만들고, 문제에서 요구하는 각 열차의 운행시간을 맞추기 위해 time_nxt를 구할 때 현재 시간에서 가장 가까운 운행 주기를 찾고, 소요 시간을 더해 계산합니다.

그 외에는 일반적인 다익스트라와 다른 점이 없는 문제입니다.

전체를 순회하는 탐색 문제에서, 비트마스킹을 더한 문제입니다.

크게 사용된 알고리즘은 3가지 입니다.

1. DFS

일반적으로 배열을 탐색하는 경우 BFS를 사용하는 것이 일반적입니다. 하지만 문제에서 주어지는 배열의 크기가 1 <= M,N <= 50 으로 매우 작기 때문에 deque를 불러오는 것이 더 걸릴 것이라 판단하여 리스트를 활용한 DFS로 탐색을 진행했습니다.

2. 비트마스킹

입력으로 주어지는 리스트는 각 방향을 1,2,4,8 로 두고 벽이 있는 방향의 총 합을 나타냅니다. 따라서 델타 탐색을 할 때, 벽이 있는지 여부를 비트 연산으로 확인하여 탐색을 진행하게 됩니다.

3. 플러드 필

문제에서 요구하는 방의 개수를 계산하기 위해 cnt 변수를 1씩 올려가며 탐색함과 동시에 visit배열에cnt로 방문 표시를 함으로써 각 칸에 cnt로 주소를 부여했습니다.

또한, 문제에서 요구하는 가장 큰 방의 크기 max_v를 계산하기 위해 방의 크기를 tmp 변수에 넣어 비교하는 동시에, 각 칸의 크기를 data 딕셔너리에 넣어 계산된 tmp 값을 저장해둡니다.

이를 통해 마지막으로 한 번 더 순회하면서 인접한 칸의 visit에 저장된 값이 다른 경우, 둘을 합치고 max_sum 에서 최대값을 비교함으로써 원하는 세 가지의 값을 모두 찾을 수 있습니다.

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
data = set(input().strip() for _ in range(N))

for _ in range(M):
    arr = set(input().strip().split(","))
    data -= arr
    print(len(data))

2. 딕셔너리를 이용하는 방법

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
data = {input().strip(): True for _ in range(N)}

for _ in range(M):
    arr = input().strip().split(",")
    for keyword in arr:
        if data.get(keyword):
            data[keyword] = False
            N -= 1
    print(N)           

파이썬을 다루면서 딕셔너리를 우선적으로 생각하게 되어 바로 떠오르는 풀이는 2번이었으나, 딕셔너리의 값이 True/False 두 종류뿐이라면 이는 세트와 크게 다르지 않을 것이라는 생각에 세트로 풀이하는 방법 또한 작성했습니다.

세트로 풀이하는 경우, 마지막에 len을 거쳐 정답을 출력하기에 추가적인 비용이 발생할 것이라 생각했는데 오히려 걸린 시간이 더 짧아서 신기하긴 했습니다.