[코테연습] 894. All Possible Full Binary Trees

오늘은 동적계획법에 관련된 문제였다.

 

그동안 DFS / BFS 문제와 탐욕법 문제를 풀어왔는데 동적계획법은 정말 적응하기 쉽지 않은 문제이다.

 

이번에도 머리를 싸매다가 결국 답을 볼 수 밖에없었다. 뭐가 이렇게 어려운지..

 

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

 

이 문제는 n 값이 주어지고 n 값으로 만들 수 있는 이진트리 ( full binary trees ) 를 구하는 문제이다.

 

int n = 3 이라면,

 

먼저 root Node 를 만드는데 1 을 써야할 것이다.

 

그리고 나머지 2,3 이 root Node 의 child Node 가 된다.

 

int n = 4 라면,

 

root Node 를 만드는데 1을 쓴다.

 

이후 2,3,4 가 남게되는데 int n =3 이었던 것과 동일하게 2, 3 을 1의 child Node 로 만든다.

 

이후 4가 남는데 이것으로 full binary Tree 를 만들 수가 없다. 즉, 짝수 혼자 남았다면 full binary 는 성립할 수 없다.

 

int n = 5라면,

 

root Node 를 만드는데 1을 쓰고

 

이후 2,3,4,5 가 남는다. int n = 3 이었던 것과 동일하게 2,3 을 1 의 childNode 로 만든다.

 

이후 4,5 가 남는데 이것으로 2 의 childNode 로 만들거나 3의 childNode 로 만들 수 있다.

 

int n = 6 이라면, 

 

int n = 5과 동일한 과정을 거친 후에 나머지 6 이 남게되는데 이것으로 full binary 를 만들 수 없으므로 int n = 5 와 동일하다.

 

int n =7 이라면

 

n = 5 와 동일한 과정을 거친 후에 남은 6, 7 의 수를 4, 5 의 childNode 로 만들 수 있을 것이다.

 

========================================================

 

이제 int n = 7 일때, 거쳐왔던 과정을 되돌아보자. 

 

int n = 7 의 과정까지 오기위해서 경우의 수를 따져보아야한다.

 

우선 n = 1 일때 rootNode 가 만들어진 다는 것은 변함없다.

 

n = 3 일때와 마찬가지로 rootNode = 1 밑에 2, 3 존재하는 것 또한 변함 없다 ( full binary tree 가 되어야하므로 )

 

n = 4 은 full binary tree 를 만들 수 없으므로 고려하지 않는다.

 

n = 5 부터 경우의 수를 따질 수 있다. 즉 child 노드가 2 밑에 존재할 것인지 3 밑에 존재할 것인지

 

한 쪽은 완전한 biniary tree 구조를 이룰 것이고 한쪽은 childNode 가 없을 것이다.

 

해당 경우의 수를 2가지로 나눌 수 있을 것이다.

 

n = 7 일경우에는 depth 2까지 full birary tree 를 이루는 1 가지 경우와 n = 5 경우의 수와 곱한 2 * 2 = 4가지 경우의 수로 총 5가지 경우의 수가 존재한다.

 

 

 

 

이러한 패턴을 반복문으로 확인해본다면

 

i = 1 부터 2 씩 증가할 것이다. ( full binary tree 를 위해서는 홀수이어야 하므로 )

 

i 는 왼쪽 binary tree 가 child 가 없을 때 이고

오른쪽 binary tree 가 child 가 있게 하기 위해서는 n - i - 1 이 성립해야한다.

 

n = 7

i = 1 일때

i = 5 개의 Node 가 있어야하기 때문이다.

 

n = 7 일때 경우의 수를 따지면

 

i = 1 , i = 3, i = 5

i = 5, i = 3, i = 1

 

로  총 3가지로 나눌 수 있다.

 

나머지 2개는 재귀함수로 확인해야한다

 

즉 for 문에 allPosiibleFBT  함수를 적용하여 n = 5 일떄와 n = 3 일때 , n =1  일때를 반복해주어야하는 것이다.

 

이것을 코드로 구현하면 다음과 같다.

 

       for (int i = 1; i < n; i +=2) {

            List<TreeNode> left = allPossibleFBT(i);

            List<TreeNode> right = allPossibleFBT(n-i-1);

           //...

        }

 

이제  left List와 right List 에는 i = 1, 3, 5 // n-i-1 = 5, 3 , 1 일때의 경우의 수의 treeNode 를 담은 list 가 들어있게 된다.

해당 List 를 다시 for 반복문으로 풀어서 다 add 해준다.

 

for (int i = 1; i < n; i +=2) {

            List<TreeNode> left = allPossibleFBT(i);

            List<TreeNode> right = allPossibleFBT(n-i-1);

            for (TreeNode l : left) {

                for (TreeNode r : right) {

                    TreeNode root = new TreeNode(0, l, r);

                    res.add(root);

                }

            }

        }

 

=================

 

이제 동적계획법이다. 이 문제에서는 이전 i = 1, 3, 5 일때, 각 결과를 다시 구해주는 것을 막기 위해서 Map 을 사용해서 n 을 key 값으로 사용하고 List<TreeNode>를 value 로 하여 return 해준다.

 

 

Map<Integer, List<TreeNode>> memo = new HashMap<>();

    public List<TreeNode> allPossibleFBT(int n) {

        if (n%2 == 0) {

            return new ArrayList<TreeNode>();

        }

        if (n==1) {

            return Arrays.asList(new TreeNode());

        }

        if (memo.containsKey(n)) {

            return memo.get(n);

        }

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

        for (int i = 1; i < n; i +=2) {

            List<TreeNode> left = allPossibleFBT(i);

            List<TreeNode> right = allPossibleFBT(n-i-1);

            for (TreeNode l : left) {

                for (TreeNode r : right) {

                    TreeNode root = new TreeNode(0, l, r);

                    res.add(root);

                }

            }

        }

        memo.put(n, res);

        return res;

    }

 

 

memo Map 으로 HashMap 을 초기화한뒤에, n 값이 Map 에 들어있으면 해당 결과 값을 그대로 return 한다.