[알고리즘 마스터] 14. 트리와 트라이

안녕하세요! 개발감자입니다🥔

오늘은 알고리즘 중 트리와 트라이에 대해서 정리하고 백준 문제를 통해 구현해보는 시간을 가져보도록 하겠습니다.

 

1. 트리 알아보기

트리는 그래프의 특수한 형태로 노드와 에지로 연결되어있습니다.

1-1. 트리의 특징

1) 순환구조가 아니며, 1개의 루트 노드가 존재합니다.

2) 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖습니다.

3) 트리의 부분 트리 역시 트리의 모든 특징을 따릅니다.

 

1-2. 트리의 구성 요소

트리의 구성 요소

• 노드 : 데이터의 index와 value를 표현하는 요소
• 에지 : 노드와 노드를 연결하는 선
• 루트 노드 : 트리에서 가장 상위에 존재하는 노드
• 부모 노드 : 두 노드 사이 관계에서 상위 노드에 해당하는 노드
• 자식 노드 : 두 노드 사이 관게에서 하위 노드에 해당하는 노드
• 리프 노드 : 트리에서 가장 하위에 존재하는 노드
• 서브 트리 : 전체 트리에 속한 작은 트리

1-3. 백준 문제로 트리 알아보기

백준 11725번 트리의 부모 찾기 문제를 풀어보면서 코딩 테스트에서 트리를 어떻게 구현하고 활요하는지 알아볼까요?

 

import sys
sys.setrecursionlimit(10**6)  # 예: 최대 재귀 호출 횟수를 10^6으로 설정
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
answer = [0 for _ in range(n+1)]
visited = [False for _ in range(n+1)]

for i in range(n-1):
    a,b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# DFS 탐색
def DFS(num):
    visited[num] = True
    for i in tree[num]:
        if not visited[i]:
            answer [i] = num
            DFS(i)
DFS(1)

for i in range(2,n+1):
    print(answer[i])

 

트리를 구현할 때에는 에지 리스트를 활용합니다. 이 경우에는 양방향 에지 리스트라고 생각하고 구현하였습니다.

문제에서 원하는 것은 각 노드의 부모를 구하는 것이기 때문에, 깊이 우선 탐색을 이용하여 부모노드를 구현하였습니다.

 

 

2. 트라이

 

트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계된 트리 형태의 구조입니다.

출처  TWpower's Tech Blog

 

 

2-1. 트라이의 특징

1) N진 트리 : 문자 종류의 개수에 따라 N이 결정됩니다.

2) 루트노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지합니다.

 

2-2. 백준 문제를 보며 트라이 알아보기

 

백준 문제 14425번 문자열 찾기를 보며 트라이를 구현해봅시다!

import sys

input = sys.stdin.readline
n,m = map(int, input().split())
textList = set([input() for _ in range(n)])
count = 0

for i in range(m): # 검사해야 하는 문자열들
    subText = input()
    if subText in textList:
        count += 1
        
print(count)

 

이 경우에는 set 함수를 활용하면 쉽게 구현할 수 있습니다. 트라이의 기본 원리를 이용한 풀이보다 훨씬 간단하게 구현할 수 있습니다.

일단 n번의 문자열을 set로 textlist에 넣습니다. m번 동안 검사해야 하는 문자열들을 보며 testlist안에 포함되어 있는지 확인하고 포함되어 있으면 count를 1씩 증가시켜줍니다.

 

이렇게 오늘 트리와 트라이에 대해서 알아보았습니다. 

이진트리에 대해서 알고싶은 분들은 아래의 포스팅을 참고해주세요.

이진트리의 개념과 종류 / 전위순회, 중위 순회, 후휘 순회 알아보기

 

개발감자였습니다!