스위프트 코딩테스트 강좌, 깊이 우선 탐색

본 강좌에서는 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘을 사용하여 알고리즘 문제를 해결하는 방법을 설명합니다. 이 글에서는 실제 알고리즘 문제를 다루고, 그 문제를 해결하기 위한 과정과 코드를 자세히 설명하겠습니다.

문제 설명

주어진 이진 트리에서 모든 경로의 합을 구하기를 원합니다. 각 경로는 루트에서 리프 노드까지의 경로입니다. 이진 트리는 다음과 같은 형태로 주어집니다:

        class TreeNode {
            var val: Int
            var left: TreeNode?
            var right: TreeNode?

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

여기서 각 노드는 값(val)을 가지고 있으며, 왼쪽 자식(left)과 오른쪽 자식(right)으로 이어져 있습니다. 만약 다음과 같은 이진 트리가 주어진다면:

루트 노드 1에서 시작하여 리프 노드 4와 5까지의 경로의 합은 7(1+2+4)과 8(1+2+5)이 되므로, 최종 답은 15가 됩니다.

문제 접근 방법

이 문제를 해결하기 위해 DFS 알고리즘을 사용할 것입니다. DFS는 특정 노드에서 시작하여 가능한 한 깊숙이 노드를 탐색하고, 더 이상 갈 수 없게 되면 돌아오는 방식으로 작동합니다. 이 경우, 우리는 각 경로의 누적 합을 계산하면서 리프 노드에 도달했을 때 그 합을 기록할 것입니다.

문제를 해결하기 위한 단계는 다음과 같습니다:

루트 노드에서 시작하여 DFS를 수행합니다.
현재 노드의 값(val)을 누적 합에 더합니다.
현재 노드가 리프 노드인 경우, 누적 합계를 결과에 추가합니다.
리프 노드가 아닌 경우, 왼쪽 자식과 오른쪽 자식으로 나아가 DFS를 재귀적으로 호출합니다.
모든 경로에 대해 위의 과정을 반복하여 누적 합을 구합니다.

스위프트 코드 구현

이제 스위프트를 사용하여 위의 알고리즘을 코드로 구현해 보겠습니다.

        class TreeNode {
            var val: Int
            var left: TreeNode?
            var right: TreeNode?

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

        class Solution {
            func sumNumbers(_ root: TreeNode?) -> Int {
                return dfs(root, 0)
            }

            private func dfs(_ node: TreeNode?, _ currentSum: Int) -> Int {
                guard let node = node else { return 0 }
                let newSum = currentSum * 10 + node.val

                if node.left == nil && node.right == nil {
                    return newSum
                }

                return dfs(node.left, newSum) + dfs(node.right, newSum)
            }
        }

위의 코드는 재귀적으로 DFS를 수행하여 경로의 합계를 계산합니다. sumNumbers 함수는 루트 노드를 인수로 받으며, dfs 함수는 현재 노드와 누적 합을 인수로 받아서 최종 합을 반환합니다. 과정은 다음과 같습니다:

sumNumbers 함수가 호출되면, 현재 누적 합 0으로 DFS를 시작합니다.
각 노드에 대해, 현재 합을 10배하고 노드 값을 더하여 새로운 합을 생성합니다.
리프 노드에 도달하면 해당 합을 반환하고, 왼쪽과 오른쪽 자식의 합을 더한 후 최종 결과를 반환합니다.

테스트 케이스

코드가 올바르게 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 생성해보겠습니다. 다음은 다양한 이진 트리 구조에 대한 예입니다.

        let root = TreeNode(1)
        root.left = TreeNode(2)
        root.right = TreeNode(3)
        root.left!.left = TreeNode(4)
        root.left!.right = TreeNode(5)

        let solution = Solution()
        print(solution.sumNumbers(root)) // 출력값: 15

위의 테스트 케이스에서는 1에서 시작하여 2를 거쳐 4와 5에 도달하는 모든 경로의 합을 계산합니다. 그 결과, 1-2-4와 1-2-5의 합이 더해져 15가 됩니다.

성과 및 최적화

이 문제에서는 DFS 방법을 사용하여 O(N) 시간 복잡도를 가집니다. 여기서 N은 노드의 수입니다. 공간 복잡도는 O(H)로, H는 트리의 높이입니다. DFS는 스택을 사용하기 때문에 최악의 경우에는 모든 노드를 방문해야 하므로 높이에 비례하는 메모리를 사용하게 됩니다.

이 외에도 BFS(Breadth-First Search) 방법을 사용해 문제를 풀 수도 있지만, 리프 노드까지의 경로의 합을 구하는 문제에서는 DFS가 더 직관적이고 효율적입니다.

결론

이번 강좌에서는 깊이 우선 탐색을 통해 이진 트리에서 리프 노드까지의 경로 합을 구하는 문제를 다뤘습니다. DFS 알고리즘의 개념을 이해하고, 이를 스위프트로 구현해 보았습니다. 이런 문제들은 많은 코딩 테스트에서 자주 출제되므로, 다양한 변형 문제를 통해 더 많은 연습을 해보시길 권장합니다.

이제 기초적인 DFS를 다루었으니, 더 복잡한 문제에 대해 도전해 보세요. 예를 들어, 그래프 탐색, 연결 요소 찾기, 최단 경로 문제 등으로 범위를 확장할 수 있습니다. 연습을 통해 더욱 능숙한 코딩 능력을 갖추시길 바랍니다.

문제 설명

문제 접근 방법

스위프트 코드 구현

테스트 케이스

성과 및 최적화

결론

관련