99클럽 코테 스터디 18일차 TIL + DP(All Possible Full Binary Trees)

오늘의 과제

리트코드 Medeum으로 분류된 All Possible Full Binary Trees입니다.

 

처음으로 등장한 유형인 DP(Dynamic Programing)입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

n이 주어질 때 말단 노드를 제외한 모든 노드가 양쪽 노드를 갖고 있는

완전 이진 트리를 만들어 List에 담아 반환하면 됩니다.

 

문제의 유형처럼 DP를 활용하는 문제로 이전 결과값을 캐싱해

이후 계산에 사용하는 방식입니다.

 

완전 이진트리 여부를 확인하는 방법은 여러가지가 있겠지만

이전에 lt, rt를 활용한 이분탐색과 비슷하게 트리를 반으로 나누어 진행했습니다.

 

즉, 왼쪽으로 뻗어나가는 재귀, 오른쪽으로 뻗어나가는 재귀를 한 곳에 묶어 호출하면

매 호출은 양쪽 노드를 갖고 있을 수 밖에 없으니 자연스레 완전 이진 트리가 됩니다.

 

코드입니다,

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 import java.util.*;

class Solution {
    private List<TreeNode>[] memo;

    public List<TreeNode> allPossibleFBT(int n) {
        memo = new List[n + 1];
        return dfs(n);
    }

    private List<TreeNode> dfs(int n) {
        // 이미 캐싱되어 있다.
        if (memo[n] != null) {
            return memo[n];
        }
        // 노드가 한 개인 경우도 완전 이진 트리다.
        if (n == 1) {
            return List.of(new TreeNode(0));
        }

        List<TreeNode> result = new ArrayList<>();

        // 왼쪽과 오른쪽 트리로 나누어 탐색한다.
        for (int i = 0; i < n - 1; ++i) {
            int j = n - 1 - i;
          
            for (TreeNode leftSubtree : dfs(i)) {
                for (TreeNode rightSubtree : dfs(j)) {
                    result.add(new TreeNode(0, leftSubtree, rightSubtree));
                }
            }
        }
        
        // 현재 결과를 캐싱한다.
        return memo[n] = result;
    }
}

 

배운 점

가장 어려워하던 DP입니다.

 

점화식만 찾으면 되는데 그 찾는게 너무 어려워 머리 아팠었는데 다시 아파오기 시작하네요.

 

사실 여행지라 집중을 못했는지 시간 내 문제를 풀지 못해 다른 사람의 코드를 이해하는 방식으로 풀었습니다.

 

재귀가 많아 코드는 단촐하지만  3중 반복문으로 leftSubTree와 rightSubtree를 나누는 로직을

이해하는데 시간이 가장 많이 들었던 것 같습니다.

 

이전에 알고있던 DP는 이전 결과를 계산식에 활용하던 문제들 뿐이었는데

이번엔 캐싱된 List 자체를 활용하는 문제라 이해가 더 어려웠습니다.

 

DP와 재귀가 합쳐지니 복잡도가 올라가 이후 문제부터는 손으로 그려보며

문제를 풀어나가야 할 것 같습니다.

 

 

오늘의 한줄평

문제뿐 아니라 알고리즘 해법도 내 머리속에 캐싱