기억하고싶은것들

• Backtracking에 대한 정의
• DFS와 비교 

백트래킹은 '조합 알고리즘 문제'에 대해 모든 가능한 해를 나열하는 것이다.

모든 조합의 수를 살펴보는 것인데 단 조건이 만족하는 경우에만 해당된다.

즉 주어진 조합을 탐색 시 답이 될만한지 판단하고 그렇지 않으면 해당 조건은 탐색을 멈추고 가지치기를 하는 것이다.

완전 탐색에서 좀 더 효율적으로 유망성을 판단하고 가지치기를 수행한다.

완전 탐색 : 여러 개의 solution을 가진 문제에서, 모든 solution을 탐색하는 전략

DFS와 비교 

대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색)가 있다.

DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출 또는 Stack을 이용해서 계속 이동한다. 

하지만 DFS는 모든 노드를 방문하기 때문에 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 탐색을 수행할 수도 있다.

백트래킹은 DFS에 가지치기 (Pruning)를 통해 불 필요한 탐색을 제한하는 완전 탐색 기법이다.

가지치기를 얼마나 잘하느냐에 따라서 효율이 극대화될 수 있는 방법이다.

정리하자면, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.

• dynamic programming에 대한 개념 설명
• dynamic programming을 적용하기 위한 조건 
• dynamic programming의 특징
• dynamic programming의 접근법

Dynamic Programming은 보통 DP라고 줄여 쓰는것을 볼 수 있다.

이름만 봤을때는 뭔가 엄청나게 대단하고 복잡한 알고리즘일것 같은데, 실제 해당 내역을 공부하면 이름이랑 뭔가 맞지 않는다는게 느껴진다.

보통 인터넷을 찾아봤을때, Dynamic Programming의 정의는 아래와 같다.

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 

개념은 그렇게 어렵지 않고, 받아들일수 있다.

그러면, 이러한 DP를 어떠한 상황에 적용할 수 있는지 알아보자.

가장 대표적인 예시로는 피보나치 수열이 있다. 

간단하게 피보나치 수열에 대한 정의를 보면 아래와 같다.

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 이다.
처음 여섯 항은 각각 (0), 1, 1, 2, 3, 5, 8이다.
편의상 0번째 항을 0으로 두기도 한다.

DP라는 개념이 등장하기 전에는 대부분 해당 문제를 재귀적으로 해결하였다. 

아래는 예시 코드이다.

int fibonacci(int n) {
    if (n<=2)
      return 1;
    else
      return fibonacci(n-1) + fibonacci(n-2);
}

하지만 해당 방법으로 문제를 풀게 된다면, 반복되는 값들을 반복적으로 구한다는 문제가 있다. 

아래의 그림에서 트리에서 반복적으로 fib(5) 이하의 노드들을 계산하게 된다. 

한번만 계산해 놓고 해당 값을 다시 만나면 이전에 계산해 놓은 값을 가져다가 쓰기만 하면 계산 시간을 효율적으로 줄일 수 있게된다.

이러한 점을 반영하여서 DP의 적용 조건과 특징을 살펴보자.

DP의 적용 조건

• 부분문제 반복 ( Overlapping Subproblem )
  • 피보나치 수열과 같이  f(n) = f(n-1) + f(n-2) 와 같이 
    어떠한 문제가 여러개의 부분 문제로 쪼개 질 수 있고, 해당 부분 문제가 또 다시  재귀적으로 부분 문제로 쪼개질 수 있는 것
• 최적 부분구조 ( Optimal Substructure )
  • 피보나치 수열과 같이 f(n) = f(n-1) + f(n-2)와 같이
    작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있는 것

( 해당 조건은 뭔가 전문적인 단어들이 들어가서 어렵게 표현된 것처럼 보이는데, DP의 핵심은 "복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 것" 이다. 이 핵심을 풀어서 전문적으로 설명해 놓은게 조건이라고 생각하자.)

DP의 특징으로는 Memorization이다.

반복적으로 등장하는 계산을 기억해 두었다가, 해당 계산이 다시 등장할때, 재계산을 하지 않고 기억해 두었던 값을 가져다 사용하는 것이다. 

위의 피보나치 수열 그래프에서 반복적으로 등장하는 fibo(5), fibo(4) ... 값들을 기억하고 사용하면 된다. 

접근법

이제 개념적인 부분과 특징을 알아 보았으니 실제로 문제를 만났을때 어떻게 접근해야하는지에 대해서 알아보도록 하자.

크게 2가지 방법이 있다. 

• Top-Down
  • 재귀로 해결 하는 대부분의 방식
  • 큰 문제를 해결 하기 위해 작은 문제로 나누고, 해당 값이 아직 계산되지 않은 경우 더 작은 값으로 나누며 값을 찾아가는 방식
  • ( 예시는 위의 fibonacci 코드 )
• Botton-up
  • 작은 문제에서 부터 하나씩, 하나씩 값을 찾아가는 방식
  • ( 예시는 아리의 코드 )

int fibonacci (int n) {
  fibodata[0] = 0;
  fiboData[1] = 1;
  for (int i=2; i<=n; i++) {
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  }
  return fiboData[n];
}

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

BST의 root 노드가 주어지고, 이 노드를 Greater Tree로 변환하여라.

BST의 모든 key값은 -> 초기값 + 해당 노드보다 큰 key값을 가진 노드의 합으로 변경된다. 

아래는 BST가 만족하는 제약사항들이다.

• 왼쪽 하위 트리는 해당 노드의 key값보다 작은 노드들로만 구성된다.
• 오른쪽 하위 트리는 해당 노드의 key값보다 큰 노드들로만 구성된다.
• 오른쪽, 왼쪽의 모든 하위 트리는 BST이다. 

DFS를 이용해서 해당 문제의 답을 구해보자.

자기 자신보다 큰 값을 가지고 있는 노드들의 합을 구해야 하므로 가장 큰 값을 가지고 있는 노드부터 자기 자신의 값을 더해가면서 그 합들을 구해가면 된다. 

BST의 특성상 가장 큰 값은 트리의 오른쪽 노드들만 타고 가면 나오고

가장 끝의 도달한 순간 부터는 해당 노드의 value를 total sum과 더해가면서 노드의 value값을 변환하면 된다. 

    private void dfs(TreeNode node) {
        if (node.right != null) {
            dfs (node.right);
        }
        int temp = node.val;
        node.val = sum + temp;
        sum = node.val;

        if (node.left != null) {
            dfs(node.left);
        }
    }

오른쪽 subTree를 모두 순회한 후에 왼쪽 서브 트리를 같은 방식으로 순회하면 된다.

(왼쪽의 subTree의 경우에도 가장 큰 값은 오른쪽 끝에 존재) 

이제 해당 메서드를 호출하는 메서드를 보자.

누적 sum을 나타내는 값은 전역변수로 선언하였다.

    int sum = 0;
    public TreeNode bstToGst1(TreeNode root) {
        
        if (root != null) {
            dfs(root);
        }

        return root;
    }

문제 출처

leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Given the root of a binary tree, return the sum of values of its deepest leaves.

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

dfs를 이용해서 답을 구해 보자. 

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

        if (level  > maxLevel) {
            sum = 0;
            maxLevel = level;
        }

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

해당 메서드를 호출하는 내역을 보자

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

문제 출처 

leetcode.com/problems/deepest-leaves-sum/