이 글에서는 트리 데이터 구조의 개념과 해당 구조를 기반으로 한 알고리즘 문제를 다루고, 이를 해결하는 과정을 상세히 설명하겠습니다.
트리란?
트리는 비선형 데이터 구조의 일종으로, 계층적인 관계를 표현하는 데 사용됩니다. 트리는 다음과 같은 특징을 가집니다:
- 트리는 노드의 집합으로 구성됩니다.
- 하나의 루트 노드가 있으며, 나머지 노드는 이 루트 노드를 기준으로 하위 트리를 형성합니다.
- 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.
- 트리는 사이클이 없습니다.
어떤 종류의 트리들이 있을까요?
트리는 그 구조와 규칙에 따라 여러 종류로 나눌 수 있습니다. 다음은 몇 가지 주요 트리의 종류입니다:
- 이진 트리: 각 노드가 최대 2개의 자식 노드를 가지는 트리입니다.
- 완전 이진 트리: 모든 레벨이 최대 노드 수를 가진 트리입니다.
- 균형 이진 트리: 높이 차이가 최소화된 이진 트리입니다.
- 이진 탐색 트리(BST): 왼쪽 서브트리의 모든 값은 부모보다 작고, 오른쪽 서브트리의 모든 값은 부모보다 큰 트리입니다.
- AVL 트리: 균형 잡힌 이진 탐색 트리의 일종입니다.
알고리즘 문제: 이진 트리의 최대 깊이
다음 문제를 해결해보겠습니다.
문제: 이진 트리가 주어질 때, 이 트리의 최대 깊이를 구하는 함수를 작성하시오. 트리의 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 경로에 있는 노드의 수입니다.
예를 들어, 주어진 트리가 다음과 같을 때:
3
/ \
9 20
/ \
15 7
이 트리의 최대 깊이는 3입니다.
문제 해결 접근법
이 문제를 해결하기 위해, 우리는 트리의 노드를 탐색하고 각 노드의 깊이를 계산할 수 있습니다. 깊이를 계산하는 방법으로는 여러 가지가 있지만, 깊이 우선 탐색(DFS)을 사용하면 간단하게 해결할 수 있습니다. 재귀적 접근법을 이용하면 코드가 간결해집니다.
파이썬 코드 구현
아래는 주어진 문제를 해결하기 위한 파이썬 코드입니다:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
else:
left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)
return max(left_depth, right_depth) + 1
위의 코드는 이진 트리의 루트 노드를 인자로 받아서 최대 깊이를 반환합니다. 재귀 함수를 사용하여 현재 노드가 비어있지 않은 경우, 왼쪽과 오른쪽 서브트리의 최대 깊이를 계산하고, 더 큰 깊이에 1을 더하여 반환합니다.
코드 실행 예시
아래는 트리를 생성하고, 최대 깊이를 계산하는 예시입니다:
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(maxDepth(root)) # 출력 결과: 3
위 코드를 실행하면, 주어진 이진 트리의 최대 깊이는 3이라는 결과를 얻습니다.
심화 학습: 트리의 다른 탐색 방법
트리 탐색에는 DFS 외에도 너비 우선 탐색(BFS) 방법이 있습니다. BFS는 큐를 사용하여 레벨 순서대로 노드를 탐색하는 방식입니다. 아래는 BFS를 사용하여 최대 깊이를 계산하는 방법입니다.
from collections import deque
def maxDepthBFS(root):
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
BFS 접근법을 사용하게 되면, 각 레벨을 반복하면서 노드를 탐색하므로 전체 깊이를 효율적으로 계산할 수 있습니다.
트리 문제 풀이의 중요성
코딩 테스트에서 트리 문제는 자주 출제됩니다. 트리는 복잡한 데이터 구조이므로, 이에 대한 이해가 없으면 어려운 문제를 해결하기 어렵습니다. 트리 문제를 통해 재귀, BFS, DFS, 백트래킹 등 다양한 알고리즘 문제 해결 전략을 익힐 수 있습니다. 따라서, 기업의 코딩 테스트에 대비하기 위해 트리 문제를 충분히 연습하는 것이 중요합니다.
결론
이번 글에서는 이진 트리의 개념과 최대 깊이를 구하는 알고리즘 문제를 통해 깊이 우선 탐색 및 너비 우선 탐색의 두 가지 접근 방식을 살펴보았습니다. 트리 문제는 알고리즘 문제의 기본이며, 실제 코딩 테스트에서도 자주 출제되는 중요한 주제입니다. 따라서, 이와 관련된 다양한 문제를 풀어보며 경험을 쌓는 것이 중요합니다.
트리와 관련된 문제를 풀어보면서 다양한 경험을 쌓고, 알고리즘 이해도를 높이는 계기가 되길 바랍니다. 앞으로도 다양한 자료 구조와 알고리즘에 대해 깊이 있게 공부해보세요.