코틀린 코딩테스트 강좌, 이진 트리

안녕하세요, 여러분! 오늘은 이진 트리에 대해 알아보고, 관련 문제를 해결해보는 시간을 가지겠습니다. 이진 트리는 컴퓨터 과학과 알고리즘의 기본적인 구조 중 하나로, 많은 취업용 코딩 테스트에서 출제되는 주제입니다. 이 글에서는 이진 트리의 기본 개념을 소개한 후, 이를 활용한 문제를 제시하고, 코틀린을 이용하여 문제를 해결하는 과정을 자세히 설명하겠습니다.

이진 트리의 기본 개념

이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조입니다. 노드는 데이터와 자식 노드에 대한 참조를 가지고 있습니다. 이진 트리는 다양한 용도로 사용되며, 트리 탐색, 정렬 알고리즘 등에서 중요한 역할을 합니다.

이진 트리의 구조

class TreeNode(val value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

위의 코드에서 TreeNode 클래스는 이진 트리의 각 노드를 표현합니다. value는 노드의 값이며, left와 right는 각각 왼쪽 자식 및 오른쪽 자식을 나타냅니다.

문제 제시

지금부터 우리가 해결할 문제를 제시하겠습니다. 주어진 이진 트리의 모든 경로에서 각 경로의 합이 특정 값과 같은 경로의 수를 세는 문제입니다.

문제 설명

주어진 이진 트리의 루트 노드에서 각 리프 노드까지 가는 경로의 합을 계산하고, 이 합이 주어진 값과 같은 경로의 수를 출력하는 함수를 작성하세요.

입력:

  • 이진 트리의 루트 노드를 나타내는 root.
  • 정수 sum, 찾고자 하는 경로의 합.

출력:

  • 주어진 sum과 동일한 경로의 수.

예제

Input:
        5
       / \
      4   8
     /   / \
    11  13  4
   /  \      \
  7    2      1
sum = 22

Output:
3

문제 해결 과정

이 문제를 해결하기 위해 우리는 DFS(Depth-First Search) 알고리즘을 사용할 것입니다. DFS는 트리를 탐색할 때 유용한 방법으로, 재귀 호출을 통해 노드를 방문합니다.

문제 해결 접근 방식

  1. DFS를 사용하여 각 경로를 탐색합니다.
  2. 각 노드를 방문할 때, 누적 합을 유지합니다.
  3. 리프 노드에 도달했을 때, 누적 합이 sum과 같은지 확인합니다.
  4. 같은 경우 카운트를 증가시킵니다.

코틀린 코드

fun pathSum(root: TreeNode?, sum: Int): Int {
    return findPaths(root, sum, 0)
}

fun findPaths(node: TreeNode?, target: Int, currentSum: Int): Int {
    if (node == null) {
        return 0
    }

    val newSum = currentSum + node.value
    var pathCount = 0

    if (node.left == null && node.right == null && newSum == target) {
        pathCount += 1
    }

    pathCount += findPaths(node.left, target, newSum)
    pathCount += findPaths(node.right, target, newSum)

    return pathCount
}

코드 설명

위의 코드는 주어진 이진 트리의 경로의 합을 구하는 함수입니다. pathSum 함수는 주어진 root와 sum을 입력받아 경로의 수를 반환합니다. findPaths 함수는 재귀적으로 노드를 탐색하며 경로의 합을 계산합니다. 각 리프 노드에 도달했을 때 누적 합이 target과 같은지 확인하고, 만약 같다면 경로 카운트를 증가시킵니다.

테스트 케이스

이제 작성한 함수를 테스트해보겠습니다. 다양한 테케를 적용해 봄으로써 알고리즘의 정확성을 검증하겠습니다.

fun main() {
    // Sample test case
    val root = TreeNode(5).apply {
        left = TreeNode(4).apply {
            left = TreeNode(11).apply {
                left = TreeNode(7)
                right = TreeNode(2)
            }
        }
        right = TreeNode(8).apply {
            left = TreeNode(13)
            right = TreeNode(4).apply {
                right = TreeNode(1)
            }
        }
    }
    
    val sum = 22
    val result = pathSum(root, sum)
    println("Number of paths: $result") // Output: Number of paths: 3
}

결론

이번 글에서는 이진 트리를 이용한 알고리즘 문제를 해결해보았습니다. DFS를 활용하여 각 경로의 합을 구하는 방법을 배웠고, 코틀린 언어로 구체적인 코드 작성 방법을 알아보았습니다. 이진 트리는 다양한 문제를 푸는 데 기초적인 자료구조로 많이 활용되므로 여러 문제에 적용해보는 것이 좋습니다.

이상으로 이번 강좌를 마치겠습니다. 앞으로도 더 많은 알고리즘 문제를 함께 풀어보며 실력을 향상시켜 보아요!