DJ Lee

Tree 문제를 풀다 보면, 종종 트리의 깊이를 구해야 할 때가 온다. 그 때 마다 그냥 치트키 처럼 쓸 함수이다.

  int depthHelper(TreeNode* root) {
      if(!root) return 0;
      return max(1+ depthHelper(root->left), 1+ depthHelper(root->right));
  }

컴공에서 알고리즘은 정말 필수다. 3-4학년 기준 알고리즘을 한 문제도 안 푼 학생은 한 명도 없을 거라고 장담한다.

많은 사람들이 백준, 프로그래머스 등 다양한 사이트를 이용하지만, 난 leetcode를 사용한다!

그럼 나만의 leetcode 활용법에 대해서 포스팅해보겠다!

난 알고리즘을 본격적으로 풀기 시작한게 상대적으로 조금 늦었다고 생각한다. 대충 4학년 1학기 때부터 시작했으니까?

학기 중에 자료구조와 알고리즘을 수강한 것을 제외하면 딱히 알고리즘 공부를 한 게 없었다. 언어는 파이썬, 자바, C++ 중에 뭐로 할까 고민을 했었는데, 파이썬은 학부 연구생 시절부터 인턴을 하는 지금도 계속 사용하고 있고, 자바는 3학년 1학기 때 플젝을 했고, C++는 2학년 2학기 때 플젝을 했으므로, 가장 오랫동안 사용하지 않았던 C++를 쓰기로 정했다.(다시 refresh 좀 할 겸) 그리고 주워듣기로는 C++가 컴파일 속도가 빨라서, 알고리즘 바닥에서는 가장 많이 이용되는 언어라고 한다.(정확하진 않음)

그리고 leetcode의 문제를 봤을 때, 위 그림과 같은 따봉과 역 따봉이 있는데, 나는 따봉이 역 따봉에 2배 이상 되는 문제들만 푼다! 역 따봉이 많다는 것은 그만큼 그 문제가 좋지 않을 문제일 테니까 과감히 스킵한다...어차피 풀 문제들은 많다. 그리고 문제를 풀고, accept이 되면 일단 안도의 한숨을 쉬고, discuss 항목으로 가서 역시 따봉을 많이 받은 글 순으로 정렬을 하고 다른 사람들이 제출한 답을 공부한다. 다른 사람들의 답을 리뷰를 하다 보면, 정말 똑똑하고 대단한 사람이 많다는 생각이 든다. 다른 사람들의 질 좋은 답을 review를 하는 것은 정말 중요하다!

그래서 처음에는 그냥 무작정 쉬운(Acceptance가 높은)순으로 정렬하고, 가장 쉬운 문제부터 막 풀었다. 아무래도 쉬운 문제 들이다 보니까 겁나 쉽게 풀려서 '오홍 별거 아닌데?'라고 생각했다. 그런데 점점 어려운 문제가 나올수록, 특정한 자료구조를 이용하는 문제가 나올수록 시간만 쏟아내고 문제를 보며 멍만 때리는 시간이 길어졌다. 그래서 아무래도 자료구조를 다시 공부해야 될 듯싶어서(2학년 1학기 때 너무 개판으로 공부했다), 특정 자료구조의 Easy 난이도를 다 풀기로 했다. 예를 들면 stack의 easy문제를 다 풀고(풀면서 다시 stack을 공부하고), queue로 넘어가고, linked list로 넘어가고, tree로 넘어가고... 이런 식이다. 이렇게 하루에 대충 1문제씩 풀었다고 가정했을 때, 한 3-4달을 기초 자료구조를 이용한 알고리즘 문제를 푼 것 같다. 

 이제 대충 다시 자료구조 개념이 잡혔다고 생각이 들어서, 이제 다시 쉬운 순서부터 풀기 시작했다! 확실히 자료구조 개념을 다시 refresh하고 문제를 푸니까 더 잘 풀리는 것 같다. 현재 아직도 easy 단계의 문제들만 풀고 있는데, 빨리 medium 단계로 넘어가고 싶다. 다른 것도 할게 많다 보니까 1일 1문제 정도만 하고 있는데, 속도는 중요하지 않고 꾸준하게만 하자는 생각이다. 화이팅!

저번 포스팅에서 대략적으로 Tree 문제를 크게 어떻게 풀어야 할지 두 가지 방법을 적어봤다.

그중 두 번째 방법인 Recursive 하게 풀어야 될 것 같을 때는 너무 어렵게 생각하지 말고, 머릿속으로 Tree를 타고 Leaf Node까지 내려가지 말고(머리가 핑핑 돌게 될 것이다) 쉽고 간단하게 풀면 된다고 했다.(아니 그게 뭔 개소립니까? 차라리 펀쿨섹하게 풀라하지?)

설명이 모호했던 것 같아서, 예시 문제와 함께 설명을 해보려 한다.

https://leetcode.com/problems/balanced-binary-tree/

leetcode의 110번째 문제다.(Acceptance는 44%, Easy 난이도에 속함) 참고로 나는 알고리즘 문제를 풀 때 leetcode를 이용한다! 백준 등 다른 유명한 사이트도 있긴 하지만, 뭔가 외국 사이트니까 간지 나 보이고, 여기서 문제를 풀면 알고리즘 관련된 영어 단어도 공부할 수 있으니 좋은 것 같아서 leetcode를 선택했다.(leetcode에서 문제를 풀고, Accept이 되면 내 답안 코드를 Github에 바로바로 올리는 편이다. 지금까지 푼 다른 문제가 궁금하시다면 Home에 있는 내 Github를 참조하시길!)

문제를 간략히 설명하면, 주어진 Binary Tree가 Balanced Binary Tree 인지를 체크하는 것인데, Balanced Binary Tree란 문제에서

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

으로 정의하고 있다.(문제의 자세한 설명과 예시 트리가 링크에 있으니 좀 더 쉬운 이해를 위해 링크를 한 번 보고 오면 좋다! 트리를 직접 그리고 싶지만 여기서 어떻게 쉽게 그려야 할지 모르겠다)

Tree의 모든 Node가 Balanced Binary Tree여야 한다. 각각 노드가 조건을 만족을 해야 하고, 각 노드에서 체크해야 할 것(Balanced Binary Tree인지 체크)이 똑같기 때문에, 나는 뭔가 Recursive 하게 풀어야겠다고 큰 그림을 그렸다.

그리고 Recursive하게 풀어야겠다고 결정한 순간! 어렵게 생각하지 않는다.

저번 포스팅에 썼던 것처럼, 

1. 현재 노드에서 해야 할 것 생각해보기

2. 바로 left, right로 넘겨버리기

의 순서로 진행한다. 이렇게 하지 않고 머릿속으로 Node를 따라 내려가다 보면, 야밤에 숲 속에서 길을 잃은 듯한 느낌을 받을 수 있다.(여기가 어느 Node인지도 모르겠고, 내가 이 Node까지 어떻게 왔는지도 모르겠고....뭔가 같은 곳을 빙빙 도는 것 같고....)

다음은 저 순서를 적용한 나의 실제 해답이다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int l_height = get_height(root->left, 0);
        int r_height = get_height(root->right, 0);
        if(abs(l_height - r_height) > 1) return false;
        bool l = isBalanced(root->left);
        bool r = isBalanced(root->right); 
        if(l&&r) return true;
        else return false;
    }
    int get_height(TreeNode* root, int depth){
        if(!root) return depth;
        int l = 0, r = 0;
        l = get_height(root->left, depth+1);
        r = get_height(root->right, depth+1);
        return max(l, r);
    }
};

설명을 하자면, get_height()는 해당 노드의 깊이(height)를 return 하는 함수이다.

본 함수인 isBalanced()에서 먼저 해당 노드에서 해야 할 것을 생각해본다.(1. 노드가 nullptr인지? 2. Balanced Binary Tree를 만족하는지?) 그 후 해당 노드의 왼쪽, 오른쪽 서브 트리의 height를 구하고 그것을 이용해서 조건을 체크한다!

그러고 나서 

bool l = isBalanced(root->left);
bool r = isBalanced(root->right);

다음과 같이 left와 right를 넘겨버린다! 그 이후 '그럼 컴퓨터가 알아서 깔끔하게 도미노처럼 촤라라락 풀어주겠지...' 하고 쉽게 생각해버린다.

그리고 return을 해줄 때 어떻게, 무엇을 해줄지만 조금 더 고민하면 문제가 잘 풀릴 것이다.

Tree 문제를 해결할 때, 문제를 대충 확인한 후

첫번째 방법: 뭔가 이건 Iterative 혹은 BFS로 풀어야 할 것 같다 -> 거의 stack이나 queue에 node를 담아서 사용

두번째 방법: 뭔가 이건 Recursive 혹은 DFS로 풀어야 할 것 같다 -> 거의 그냥 함수를 Recursive 하게 사용

(물론 전부 다 이런 접근으로만 풀 수 있는 건 아니다)

좀 더 쉽고 자세히 설명을 해보면,

첫번째 방법에서는 for(auto n : Tree) 를 사용하여 순차적으로 child node를 불러오거나 저장할 수도 있고,

인덱스를 사용하여, 직접 i번째 child node에 접근 할 수도 있다.(특히 순차적으로 child node를 읽는 것이 아닌, reverse하게 읽거나 할 때 인덱스가 유용하게 쓰이는 것 같다)

마찬가지로, 미리 Tree의 각각 nth Level의 사이즈를 구해서 int size = queue.size() size를 요긴하게 사용하는 경우가 많다.

두번째 방법에서는(특히 Binary Tree에서 많이 쓰인다)

음...그냥 너무 어렵고 복잡하게 생각하지말자. 초반에 뭔가 Recursive하게 문제를 해결 하려 할 때, 너무 복잡하게 생각해서 시간만 날리고 스트레스만 받은 적이 많다.

(그 뭔가 머리속으로 직접 Recursive 하게 node를 타고 내려가다가 야바위를 보는 것처럼 핑핑 돌아버린적이 많다.)

그냥 단순하게 생각하자. 보통 함수를 myFunc(TreeNode* root) 형식으로 작성할 경우가 많을 텐데, 우선 해당 노드에서 해야할 작업을 생각해보자. 해당 노드에서는 해당 노드의 값, 한 level 밑의 child node 말고는 딱히 할 수 있는 작업이 없을 것이다. 또한 노드가 nullptr일 경우도 생각해야한다. 그러니까 저것들만 가지고 작업한다!

그리고 나서 그냥 myFunc(node->left), myFunc(node->right)를 함수로 넘겨버린다. 끝이다.

경험상, 첫번째 방법을 사용하면 아무래도 코드가 길어지고 복잡해지는 경우가 종종 있다.

그런데 두번째 방법을 사용했는데도 본인 코드가 길어지고 복잡하다면, 뭔가 문제가 있을 가능성이 크다

(머리속으로 recursive하게 야바위를 굴렸다는 뜻)

단지 큰 그림일 뿐이니, 문제를 보고 대충 어떤 방향으로 풀지 정할 때 만 사용하자.