스위프트 코딩테스트 강좌, 트리 순회하기

트리는 컴퓨터 과학에서 중요한 자료구조 중 하나입니다.
다양한 문제를 해결할 때 트리를 깊게 이해하면 유리한 경우가 많습니다.
이번 강좌에서는 트리의 기본 개념과 스위프트를 이용한 트리 순회 방법을 함께 살펴보겠습니다.
마지막에는 실제 코딩테스트에서 출제될 수 있는 문제를 풀어보도록 하겠습니다.

1. 트리의 기본 개념

트리(tree)는 노드(node)로 구성된 자료구조입니다.
각 노드는 값과 해당 노드에 연결된 다른 노드(자식 노드)를 가집니다.
트리는 다음과 같은 특징을 가지고 있습니다.

루트 노드(Root Node): 트리의 최상위 노드입니다. (부모가 없는 노드)
리프 노드(Leaf Node): 자식이 없는 노드를 의미합니다.
부모 노드(Parent Node): 자식을 가진 노드를 말합니다.
서브트리(Subtree): 자신의 자식 노드를 루트로 하는 트리를 의미합니다.

2. 트리 순회 방법

트리를 순회(traversal)하는 방법은 여러 가지가 있습니다.
가장 대표적인 방법으로는 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order)가 있습니다.

2.1 전위 순회 (Pre-order Traversal)

순서: 노드 => 왼쪽 서브트리 => 오른쪽 서브트리
특징: 루트 노드를 가장 먼저 방문합니다.

2.2 중위 순회 (In-order Traversal)

순서: 왼쪽 서브트리 => 노드 => 오른쪽 서브트리
특징: 이진 검색 트리를 순회할 때, 값이 오름차순으로 출력됩니다.

2.3 후위 순회 (Post-order Traversal)

순서: 왼쪽 서브트리 => 오른쪽 서브트리 => 노드
특징: 자식 노드를 먼저 모두 방문한 후 부모 노드를 방문합니다.

3. 코딩테스트 문제: 이진 트리의 깊이

이제 이진 트리를 구현하고, 각 순회 방법을 적용해 보겠습니다.
주어진 문제는 이진 트리의 깊이(최대 높이)를 계산하는 것입니다.

문제 설명

주어진 이진 트리의 루트 노드를 기준으로 최대 깊이를 구하는 함수를 작성하세요.
깊이는 루트 노드로부터 리프 노드까지의 가장 긴 경로의 노드 수로 정의됩니다.

예시

입력: 
    1
   / \
  2   3
 / \
4   5

출력: 3 (루트 1에서 4 또는 5까지의 경로)

3.1 이진 트리 노드 클래스 구현

먼저 이진 트리의 노드를 나타내기 위해 클래스(Node)를 구현합니다.

class Node {
    var value: Int
    var left: Node?
    var right: Node?

    init(value: Int) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

3.2 깊이 계산 함수 구현

이진 트리의 최대 깊이를 계산하는 함수는 다음과 같이 구성할 수 있습니다.

func maxDepth(_ root: Node?) -> Int {
    guard let node = root else { return 0 }

    let leftDepth = maxDepth(node.left)
    let rightDepth = maxDepth(node.right)

    return max(leftDepth, rightDepth) + 1
}

3.3 전체 코드

전체 코드는 다음과 같습니다.

class Node {
    var value: Int
    var left: Node?
    var right: Node?

    init(value: Int) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

func maxDepth(_ root: Node?) -> Int {
    guard let node = root else { return 0 }

    let leftDepth = maxDepth(node.left)
    let rightDepth = maxDepth(node.right)

    return max(leftDepth, rightDepth) + 1
}

// 예제 트리 생성
let root = Node(value: 1)
root.left = Node(value: 2)
root.right = Node(value: 3)
root.left?.left = Node(value: 4)
root.left?.right = Node(value: 5)

// 최대 깊이 출력
let depth = maxDepth(root)
print("트리의 최대 깊이는: \(depth)")  // 출력: 트리의 최대 깊이는: 3

4. 느낀 점 및 마무리

이번 강좌에서는 트리의 개념과 스위프트를 이용한 트리 순회 방법,
그리고 코딩 테스트 문제를 통해 트리 깊이를 계산하는 방법을 배웠습니다.
트리는 다양한 알고리즘과 자료구조에서 활용되는 만큼,
이러한 기초 개념을 확실히 이해하고 연습하는 것이 중요합니다.
스위프트를 통해 구현하면서 코드를 디버깅하고 최적화하는 과정 또한 필수적입니다.
앞으로 더 많은 알고리즘 문제를 해결하면서 경험을 쌓아가길 바랍니다.