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

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

 

 

 

 

1.  문제 및 접근

 

DP 문제

 

894. All Possible Full Binary Trees

 

 

n이 주어지고, n개의  가진 정이진트리 반환, 0을 노드를 가진 트리

없거나 2개의 노드를 가진 완전이진트리 반환

7개의 노드가 주어지면 그에 맞는 경우의 수의 노드들을 만들어 반환

사실 상 짝수는 들어올 수가 없는데 ?..

null or 0 ?

제한 사항

 

1 =< n >= 20

 

 

2.  DP (Dynamic Programming)

 

Dynamic Programming의 줄임말이며 동적계획법이라고 불린다.

이름이 직관적이지 않아서 이해가 잘 가지 않을 수 있다..

 

DP는 복잡한 문제를 여러 개로 나눠서 푸는 방법이다.

 

두 가지 조건이 만족해야 하는데 ,

 

1. Overlapping Subproblems
2. Optimal Substructure

 

 

2-1. Overlapping Subproblems

 

 

최적 부분 구조

 

 

• 문제를 하위 문제로 나눌 수 있으며, 하위 문제의 최적 해가 상위 문제의 최적 해를 구성하는 데 사용될 수 있는 경우
• 예: 피보나치 수열, 최단 경로 문제 등

 

 

 

 

 

2-2. Optimal Substructure

 

 

중복되는 하위 문제

• 동일한 하위 문제가 반복해서 계산되는 경우
• 동적 프로그래밍은 이러한 중복 계산을 피하기 위해 하위 문제의 결과를 저장하고 재사용

 

 

 

 

위 조건이 만족한다면, 

 

기록을 통해 동일하게 반복되는 문제를 다시 계산하지 않고, 저장해 추가적 메모리를 써 시간을 줄인다고 생각하면 쉽다.

 

 

 

 

 

2-3 DP 예시

 

https://www.geeksforgeeks.org/dynamic-programming/

 

 

 

제일 적합한 예시가 피보나치 수열이다.

 

ibo(4)를 계산 하는 과정에서 반복되는 함수가 계속 호출될 때 저장해서 해결한다고 생각하자.

 

private static long fib(int n) {

    arr[0] = 0;

    arr[1] = 1;

    if (arr[n] == -1) {
        arr[n] = fib(n-1) + fib(n-2);
    }

    return arr[n];

}

 

 

0의 값을 넣어주기 위해 -1로 배열을 채웠고,

 

간단하게 보자면 arr[n]에 계산한 적이 없어 저장되어 있지 않다면

 

arr[n]에 fib(n-1) + fib(n-2)를 저장해주고, return 해준다.

 

이제 다음에 호출할 때 계산한 적이 있으면 호출하지 않고 그 수를 return해서 계산을 줄임!

 

 

 

 

2-4.  DP 풀이법

 

1. Top-Down

 

위 fibo가 재귀적으로 top-down으로 푼 예시인데,

 

 

1. 큰 문제를 작은 문제로 나눈다.

fibo(n-1), fibo(n-2)

 

2. 작은 문제를 해결하기

fibo(n-1) + fibo(n-2)

 

위 방식을 재귀적으로 호출한다.

 

 

 

 

2. Bottom-Up

 

 

 

1. 문제를 크기가 작은 문제부터 쓴다.

 

2. 문제의 크기를 계속 키우면서 문제를 해결해간다.(작은 문제를 풀며 큰 문제 답 구하기)

 

 

for문으로 구현

 

 

 

 

 

어느 것이 유리할까 ?

 

Top-down은 가독성이 좋지만 작성하기 직관적이지 않아 힘들다.

Bottom-up의 경우 풀기는 더 쉽지만, 가독성이 Top-down에 비해 좋지 않다.

 

사실 둘 다 사용가능하고, 진짜 특수한 경우 아닌 이상 어떤 방식으로 풀어도 상관없다고 한다..

 

(안 풀리는 경우가 있다고 하는데 만나보진 못해서.. 모르겠다)

 

 

 

 

 

3. 풀이

 

public class allPossibleFullBinaryTrees {

    //894. All Possible Full Binary Trees

    //n이 주어지고, n개의 노드를 가진 정이진트리 반환, 0을 노드를 가진 트리
    // 없거나 2개의 노드를 가진 완전이진트리 반환
    // 7개의 노드가 주어지면 그에 맞는 경우의 수의 노드들을 만들어 반환
    // 사실 상 짝수는 들어올 수가 없는데 ?..
    //경우의 수가 계속 0개이거나 2개인 경우를 호출해서 저장된 dp 반환하면 될듯 ?
    //dp의 리스트형태로 호출하고, 저장하고 treenode형태로 저장이 직관적이지 않다
    private static Map<Integer, List<TreeNode>> memo = new HashMap<>();

    // 제한 1~20

//    private static Integer[] dp = new Integer[21];


    public static void main(String[] args) {

    }
    public List<TreeNode> allPossibleFBT(int n) {

        //짝수는 올 수 없다
        if (n % 2 == 0) return new ArrayList<>();

        // 이미 계산된 값이 있으면 반환
        // dp 의 핵심
        if (memo.containsKey(n)) return memo.get(n);

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

        // n이 1이면 하나의 노드만 있는 트리 반환
        if (n == 1) {
            result.add(new TreeNode(0));
        } else {
            // 모든 가능한 좌우 서브트리의 조합을 생성
            for (int leftNodes = 1; leftNodes < n; leftNodes += 2) {
                int rightNodes = n - 1 - leftNodes;
                List<TreeNode> leftTrees = allPossibleFBT(leftNodes);
                // 재귀적으로 leftnode를 호출
                List<TreeNode> rightTrees = allPossibleFBT(rightNodes);
                // 재귀적으로 rightnode를 호출

                for (TreeNode left : leftTrees) {
                    // 트리 노드 만들어주기 (이 부분이 어렵다)
                    for (TreeNode right : rightTrees) {
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        result.add(root);
                    }
                }
            }
        }

        // 결과를 메모이제이션에 저장
        memo.put(n, result);
        //마지막 result 리턴
        return result;
    }

 

 

전체 풀이

 

사실 TreeNode로 구현해서 반환하는 방법에서 애를 크게 먹었다.. 전체적으로 GPT 형님이 도와주셔서 내가 풀었다고 말 못하겠다..

 

 

 

 

3-1. 예외 경우

 

 

 

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

 

 

먼저 저장하기 위해 map 선언 ! memo를 활용하는 DP

 

 

 

 

 

먼저 짝수는 2개의 or 0개의 노드를 가질 수 없어서 (root까지 포함이기에)

바로 빈 ArrayList를 반환하고,

 

제일 핵심인 부분은

 

계산 과정에서

 

if (memo.containsKey(n)) return memo.get(n);

 

 

저장된 부분이 있으면 중복 계산을 하지 않고 반환!

 

 

 

 

3-2. 핵심로직

 

 

 

n이 1개라면 root 하나만 반환하면 되고,

 

아닐 경우 가능한 서브트리들을 for문을 돌면서 계속 재귀적으로 호출하며 저장한다.

 

left와 right는 주어진 배열의 input으로 자리가 매겨짐으로 트리에서의 위치를 확인할 수 있어 저렇게 저장

 

 

 

 

3-3. TreeNode

 

 

 

 

주어진 트리 노드로 만들어주고, result에 저장해주고

 

또 핵심인 memo.put으로 저장해준다.

 

 

 

 

 

4. 마무리

 

 

이번 문제는 복합적으로 막혀서 눈물날 뻔 했다.

 

사실 DP는 계속 꾸준히 풀고 있는데, 자꾸 안 떠올라서 힘들다..

널리 알려진 팁이라고 하면 dp[0] 일때, dp[1], dp[2] , ... 를 하나 씩 적다보면 아주 희박한 확률로 규칙성을 파악할 수 있는데,

그걸로 점화식을 세워 핵심로직을 돌파하는 느낌이다..

 

점화식만 간단하게 정리가 가능하면 쉽게 풀리는데 DP는 난이도가 있는 문제라서 힘들긴 해..

 

점화식 세우는데 한 세월~