[99클럽 코테 스터디 18일차 TIL] LeetCode | 894. All Possible Full Binary Trees

18일차 동적계획법

Problem

https://leetcode.com/problems/all-possible-full-binary-trees/

 

Sol

n개의 노드를 가지는 가능한 모든 완전 이진트리(Full Binary Tree)를 생성하는 문제

 

Dynamic Programming

 

동적 프로그래밍

• 동적 프로그래밍 DP == 동적 계획법
• 문제를 작은 하위 문제로 나누고결과 저장➡ 동일 하위 문제에 대한 중복 계산 피하기
  1. 중복되는 하위 문제
     
     • 큰 문제를 해결하기 위해 동일한 하위 문제를 여러번 해결해야 하는 경우, 중복되는 계산을 피하기 위해 사용
     • 문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성될 수 있는 경우
  2. Memoization
     • 이미 계산한 하위 문제의 결과를 저장해두고 필요할 때마다 결과를 사용하는 방식
     • 주로 재귀를 사용해 문제 해결
     • Top-Down 방식
  3. Tabulation
     • 하위 문제부터 차례대로 해결하면서 그 결과를 테이블에 저장하고, 이를 이용해 상위 문제를 해결하는 방식
     • Bottom-Up 방식 

• 장점
  • 동일 하위 문제에 대한 중복 계산을 피할 수 있음
  • 이전에 계산된 결과를 재사용함으로써 효율성 향상
• 한계/단점
  • 단점1

 

해결 방법

👀 접근 방식

1. 로직 : 설명

 

시간복잡도 O(n)

• 세부 시간복잡도

---

✔ Answer

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        # n이 짝수인 경우
        if n % 2 == 0:  
            return []

        # 메모이제이션을 위한 dictionary
        memo = {}  

        def allPossibleFBTInner(n):
            if n == 1:  # n이 1인 경우
                return [TreeNode(0)]

            if n in memo:  # 이미 계산된 결과가 있는 경우
                return memo[n]

            result = []

            for left_tree_size in range(1, n, 2):
                right_tree_size = n - 1 - left_tree_size
                for left in allPossibleFBTInner(left_tree_size):
                    for right in allPossibleFBTInner(right_tree_size):
                        root = TreeNode(0)
                        root.left = left
                        root.right = right
                        result.append(root)

            memo[n] = result  # 결과를 메모이제이션에 저장
            return result

        return allPossibleFBTInner(n)

---

💬 소감

휴일에 하려니까 쉽지 않네요. 미리미리 해야겠습니다.! 대충 적어두고 다시 더 자세히 공부해서 수정하도록 하겠습니다.