[코테] 99클럽 코테 스터디 18일차 TIL - 동적계획법

Question1 - [미들러] 모든 가능한 이진 트리 (All Possible Full Binary Trees)

 

문제설명 https://leetcode.com/problems/all-possible-full-binary-trees/description/

 

Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.

Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

 

Example 1:

Input: n = 7

Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

Example 2:

Input: n = 3

Output: [[0,0,0]]

 

Constraints:

1 <= n <= 20

 

---

문제풀이

 

문제 해설

아래 유튜브 해설을 참고하였다.

https://www.youtube.com/watch?v=nZtrZPTTCAo

 

우선 문제 자체는 간단하다. 

자연수 n이 주어지면, 노드가 총 n개인 이진트리를 만드는데, 이때 모든 노드의 하위노드는 0 또는 2개 여야 한다. 노드별 값은 0으로 고정.

위 조건에 만족하는 모든 이진 트리의 배열을 리스트에 담아 return하는 문제.

 

오늘의 문제를 완벽히 이해하기 위해서는 

1. 백트래킹 개념        2. 메모이제이션 개념      3. 동적 계획법 개념 

에 대한 이해가 선행되어야 한다.

 

우선 풀이 코드는 아래와 같다. 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution(object):
    def allPossibleFBT(self, n):
        # A dictionary to memoize the results
        dp = {0: [], 1: [TreeNode(0)]}  # Base case: 1 node results in a single tree with one node.

        def backtrack(n):
            if n in dp:
                return dp[n]

            res = []
            for l in range(1, n, 2):  # Only odd numbers (full binary trees must have odd numbers of nodes)
                r = n - 1 - l
                leftTrees = backtrack(l)
                rightTrees = backtrack(r)
                
                for t1 in leftTrees:
                    for t2 in rightTrees:
                        res.append(TreeNode(0, t1, t2))

            dp[n] = res
            return res

        return backtrack(n)

 

 

 

*** 백트래킹 (Backtracking) 

 

백트래킹은 재귀적으로 문제를 해결하는 기법이다.

가능한 모든 해를 탐색하는 과정에서 잘못된 해를 만났을 때 되돌아가서 다른 해를 찾는 방법이다.

주로 결정 문제(decision problem)나 조합 최적화 문제(combinatorial optimization problem)를 해결할 때 사용된다.

 

이 문제에서는 n 개의 노드를 가진 모든 가능한 풀 바이너리 트리를 생성하기 위해 재귀적으로 왼쪽과 오른쪽 서브트리를 생성하는 방식으로 백트래킹을 사용한다.

def backtrack(n):
    res = []
    for l in range(1, n, 2):  # 홀수만 반복 (l과 r의 합이 n-1이어야 하기 때문에 홀수)
        r = n - 1 - l
        leftTrees = backtrack(l)
        rightTrees = backtrack(r)
        
        for t1 in leftTrees:
            for t2 in rightTrees:
                res.append(TreeNode(0, t1, t2))
    dp[n] = res
    return res

 

위 코드에서,

for l in range(1, n, 2)로n개의 노드를 가진 트리를 만들기 위해 l개의 노드를 가진 왼쪽 서브트리와 r개의 노드를 가진 오른쪽 서브트리를 생성한다. (l과 r은 홀수여야함)

그리고 각각 l개와 r개의 노드를 가진 모든 가능한 서브트리를 생성한 다음, 

for t1 in leftTrees와 for t2 in rightTrees에서 각각의 왼쪽 서브트리와 오른쪽 서브트리를 조합하여 새로운 트리를 생성한다.

 

 

 

*** 메모이제이션 (Memoization) 

 

메모이제이션은 이미 계산된 결과를 저장하고, 동일한 계산이 필요할 때 저장된 결과를 재사용하는 방법이다.

이는 중복된 계산을 피하고 시간을 절약하는 데 유용하고, 주로 재귀 함수와 함께 사용된다. (백트래킹) 

이 문제에서는 dp 딕셔너리를 사용하여 이미 계산된 n에 대한 결과를 저장하여 메모이제이션 한다.

def backtrack(n):
    if n in dp:
        return dp[n]

    ... # 트리 생성 및 저장

    dp[n] = res
    return res

 

dp[n] = res: 계산된 결과를 dp 딕셔너리에 저장하여 이후 동일한 n에 대한 계산을 피한다.

 

 

***동적계획법 (Dynamic Programming)

 

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고, 이 하위 문제들의 해를 저장하여 같은 문제를 반복해서 계산하지 않도록 하는 알고리즘이다. 

이 문제에서는 n개의 노드를 가진 모든 가능한 풀 바이너리 트리를 생성하기 위해 하위 문제들을 해결하고 그 결과를 조합하여 전체 문제를 해결했으며, 메모이제이션 또한 동적 계획법의 일환이다. dp == 'dynamic programming'

 

• dp = {0: [], 1: [TreeNode(0)]}: 기본 경우를 초기화하여 0개의 노드는 빈 리스트를 반환하고, 1개의 노드는 하나의 노드를 가진 트리를 반환한다.
• def backtrack(n): 주어진 n에 대해 모든 가능한 풀 바이너리 트리를 생성하기 위해 재귀적으로 하위 문제를 해결한다.
• for l in range(1, n, 2): 문제를 더 작은 하위 문제로 나누어 각각의 하위 문제를 해결한다.
• dp[n] = res: 각 n에 대한 결과를 저장하여 이후에 재사용

대표적인 동적계획법을 사용하는 문제로는 

피보나치 수열 문제, 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 문제, 두 문자열 간의 최소 편집 거리를 찾는 문제 등이 있다.