1. 트리(소개)
트리는 계층 구조를 표현하기 위한 자료구조로, 각 노드가 여러 자식을 가질 수 있는 구조입니다. 트리는 노드와 엣지로 이루어져 있으며, 가장 위에 있는 노드를 루트 노드(root node)라 하고, 트리의 끝에 있는 노드는 리프 노드(leaf node)라고 합니다. 트리는 다양한 문제를 해결하고 알고리즘을 구현하는 데 필수적인 개념입니다.
1.1. 트리의 성질
- n개의 노드를 가진 트리는 항상 n-1개의 엣지를 가진다.
- 루트 노드는 유일하고, 노드의 부모는 오직 하나이다.
- 모든 리프 노드는 동일한 깊이에 위치하고 있지는 않다.
2. 알고리즘 문제
문제: 이진 트리의 최대 깊이를 구하라
주어진 이진 트리의 최대 깊이를 계산하는 함수를 작성하시오. 이진 트리의 깊이는 루트 노드에서 가장 깊은 리프 노드까지의 경로에 있는 노드의 수이다.
입력
- 이진 트리는 노드 유형으로 정의되며, 각 노드는 정수 값을 가진다.
- 노드는 자식 노드를 가질 수 있으며, 자식 노드는 두 개까지이다.
출력
- 최대 깊이를 정수로 반환한다.
3. 문제 풀이 과정
3.1. 문제 이해하기
문제를 이해하기 위해 주어진 이진 트리의 특징을 잘 살펴봐야 합니다. 깊이란 루트에서 리프 노드까지 가는 최장 경로를 의미하므로, 탐색을 통해 얻을 수 있습니다. 일반적인 방법은 깊이 우선 탐색(DFS)입니다.
3.2. 트리 노드 클래스 정의하기
우선 트리의 노드를 표현하기 위한 클래스를 정의하겠습니다. 코틀린으로 아래와 같이 구현할 수 있습니다:
data class TreeNode(val value: Int, var left: TreeNode? = null, var right: TreeNode? = null)3.3. 최대 깊이를 구하는 알고리즘 구현하기
최대 깊이를 재귀적인 방법으로 구할 수 있습니다. 아래의 코드는 DFS를 활용하여 구현한 예제입니다.
fun maxDepth(node: TreeNode?): Int {
if (node == null) return 0
val leftDepth = maxDepth(node.left)
val rightDepth = maxDepth(node.right)
return Math.max(leftDepth, rightDepth) + 1
}위의 함수는 다음과 같이 작동합니다:
- 트리 노드가 null인 경우, 깊이는 0입니다.
- 왼쪽과 오른쪽 자식 노드의 깊이를 재귀적으로 호출하고, 둘 중 더 깊은 깊이를 선택합니다.
- 그리고 1을 더하여 최대 깊이를 반환합니다.
3.4. 전체 예제 구현
최대 깊이를 구하는 전체 코드를 직접 구현해 보겠습니다:
fun main() {
val root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left!!.left = TreeNode(4)
root.left!!.right = TreeNode(5)
val depth = maxDepth(root)
println("최대 깊이는: $depth") // 출력: 최대 깊이는: 3
}4. 결론
이진 트리는 알고리즘 문제를 풀기 위한 중요한 주제입니다. 문제를 풀면서 트리의 구조를 이해하고, 재귀적 사고를 활용하는 연습을 통해 코딩테스트에서 유용한 스킬을 익힐 수 있습니다. 앞으로 다양한 트리 관련 문제도 풀어보시길 권장합니다.
5. 추가 연습 문제
- 이진 검색 트리에서 특정 값을 찾는 문제
- 이진 트리의 모든 경로를 출력하는 문제
- 이진 트리의 균형 여부를 확인하는 문제
6. 참고 자료
트리에 대한 이해를 높이기 위해 다음의 자료를 참고하시기 바랍니다: