DJ Lee

여름에 당차게 블로그를 잘 꾸며 보겠다고 호언장담을 했지만 역시나 오래가지 못했다...

학기가 시작되고 20학점 들으면서 일도 계속하니까 토플 공부도 못하고 있는데 블로그를 쓸 시간은 도저히 나지 않는 것이다ㅠㅠ

그러던 중 인공지능 관련 교양 과목을 하나 듣고 있는데, 인공지능 관련 보고서를 쓰는 과제가 있어서 내가 일하고 있는 분야인 Image Classification 관련 정리도 해볼 겸 주제를 'Image Classification 연구의 동향'으로 잡고 보고서를 썼다. 바빠서 보고서를 자세히는 못 쓰고 의식의 흐름대로 그냥 적어서 깊이 있게는 못 적고, 검토도 못해서 틀린 부분이 많을 수 있지만 그래도 내용을 여기에다도 올려보겠다.

Image Classification 연구의 동향

물체 인식, 음성 인식, 자연어 처리 등 최근 활용되고 있는 여러 인공 지능 응용 분야 중에서 현재까지 가장 많이 발전되고 가장 많이 다뤄지고 있는 분야는 당연 이미지 분류(Image Classification) 분야가 아닐까 생각합니다. 따라서 이번 보고서에서는 지금까지 이미지 분류 연구가 어떻게 발전되어 왔는지, 어떤 요소들이 이미지 분류 모델들을 성공적으로 발전하도록 이끌었는지 살펴보겠습니다.

 다소 정체되어 있던 이미지 분류 분야를 폭발적으로 각성시킨 모델은 Convolution을 인공지능 모델에 사용하여 ImageNet Challenge(이미지 분류 연구를 위해 제공된 14million개 이상의 학습 데이터, 1000개의 클래스를 가진 ImageNet 데이터를 사용하는 일종의 대회)에서 이전 결과들보다 훨씬 높은 정확도를 얻어낸 AlexNet(2012, https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf) 입니다. 

위와 같이 Convolution, Max Pooling, Dense 레이어를 활용한 AlexNet은 이전까지의 Top 1 Accuracy인 50.9%에서 63%, Top 5 Accuracy는 73.8%에서 84.6%으로 획기적인 발전을 이뤄냈습니다. 이후 여러 다른 모델들이 AlexNet을 발전시켜서 현재 가장 성능이 좋은 모델(FixEfficientNet-L2, 2020)가 Top 1 Accuracy는 88.5%, Top 5 Accuracy는 98.7%의 정말 좋은 퍼포먼스를 보여주게 되었습니다. 이제 AlexNet으로부터 현재까지의 Image Classification의 주요 모델들에 대하여 주요 특징과 발전 과정에 대하여 알아보겠습니다.

먼저 VGG16(2014, https://arxiv.org/pdf/1409.1556.pdf) 모델입니다. 

(사진 출처: https://neurohive.io/en/popular-networks/vgg16/)

이와 같은 구조를 가지며 71.5%의 Top 1 Accuracy, 90.1%의 Top 5 Accuracy를 자랑하는 이 모델은 AlexNet과의 구현 상 큰 차이는 없지만 단지 더 많은 layer를(13개의 Convolution layer, 2개의 Dense layer) 사용하였을 때 얼마나 더 좋은 성능을 가질 수 있는가를 보여줍니다. 최근의 어마무시하게 거대한 딥러닝 모델들에 비하면  턱없이 작은 수준이지만, 그래도 이렇게 모델의 덩치를 키우는 것 만으로도 5% 이상의 정확도의 향상을 얻을 수 있다는 것을 보여준 모델이었습니다.

다음으로 ResNet(2016, https://arxiv.org/pdf/1512.03385.pdf)에 대하여 알아보겠습니다. 여러가지의 변종된 모델들이 있지만 기본적으로 옆의 이미지와 같은 구조를 가지는 ResNet은 75.8%의 Top 1 Accuracy, 92.9%의 Top 5 Accuracy(ResNet 50 기준)을 가집니다. 기본적으로 기존의 VGG16 모델보다 더 많은 layer를 사용하고 있고, 중요하게 이 모델에서는 기존의 모델들과는 다른, Residual Connection이라는 새로운 방법이 사용되었습니다. 그리고 이 Residual Connection은 추후의 여러 모델들도 대부분 사용할만큼 또 다른 획기적인 방법이라고 할 수 있습니다. 이 Residual Connection 방법에 대하여 간단히 설명하면, 한 Convolution Block(convolution layer를 2개 이상 사용하는 일종의 단위)의 인풋을 그 Block의 아웃풋에 더하여 다음 Convolution Block의 인풋으로 사용하는 것입니다. 어찌보면 그냥 단순히 기존의 아웃풋에 인풋을 더한 것일 뿐인데 어떻게 이 방법이 딥러닝 모델들을 획기적으로 발전시킬 수 있었는지 설명하겠습니다. AlexNet의 등장으로부터 모델들은 점점 layer를 늘리는 방향으로 발전이 되었고, 이런 방법이 어느 정도 성능을 향상시켜주었습니다. 하지만 계속 layer를 늘렸을 때 어느 순간 성능이 향상되지 않는 현상을 사람들은 발견했습니다. 그 이유는 역전파를 사용하여 layer들을 학습시킬 때, 모델이 깊어지면 깊어질수록 모델의 끝부분(prediction layer와 가까운 부분) 모델의 처음부분(input layer와 가까운 layer)들로 가면서 점점 기울기가 사라지는(0에 가까워지는) gradient vanishing 현상이 심해졌기 때문입니다. 따라서 모델 초반부의 layer들은 제대로 학습이 되지 않았고, 이 현상은 모델이 깊어질 수록 심해졌습니다. 하지만 이렇게 Residual Connection을 통해 블록의 인풋을 아웃풋에 더해주면, 계속해서 이전 블록의 정보를 다음 블록에도 포함시키는 것이므로 역전파를 이용하여 학습 시 모델 초반부로 gradient가 전해질 때 사라지지 않는 장점을 지니게 됩니다. 따라서 이 Residual Connection은 Convolution 이후의 또 다른 획기적인 방법이라고 생각합니다.

 다음으로 Inception(2014,  https://arxiv.org/pdf/1409.4842.pdf)모델에 대하여 알아보겠습니다. 78%의 Top 1 Accuracy, 94.1%의

Top 3 Accuary(Inception V3 기준)을 가지는 이 모델은, 일단 이전의 모델들보다 덩치는 더 커져서 모델의 구조 사진이 너무 커서 전체 이미지를 첨부하지는 못하지만 옆 사진과 같은 Convolution Block을 가지고 있습니다. 모델의 크기가 점점 커질수록 사람들의 고민이 생겼습니다. 파라미터가 너무 많아져서 훈련 시간이 너무 길어진다는 것이었습니다. 따라서 제안한 구조가 Inception V3의 옆의 이미지와 같은 구조인데요, 1x1 컨볼루션, 즉 파라미터의 개수가가 매우 작은 convolution을 이용하여 컨볼루션을 해준 뒤, 블록 내의 레이어들을 각각 다른 방법으로(3x3 convolution, 5x5 convolution, max-pooling 등)으로 따로 작업한뒤 element-wise 하게 더해줌으로써 하나의 아웃풋 레이어를 만드는 것입니다. 이를 통해 어찌보면 모델이 확장되고 커지고 다른 종류의 filter 크기를 사용하여 학습을 하여 보다 다양한 feature들을 뽑아 낼 수 있는 장점도 지녔고, 1x1 convolution으로 인하여 파라미터 개수도 줄이는 방법을 고안하게 됩니다. 마찬가지로 이런 구조도 추후의 모델에서 자주 사용되는 구조입니다.

마지막으로 Xception(2017, https://arxiv.org/abs/1610.02357) 모델에 대하여 알아보겠습니다. 79%의 Top 1 Accuracy, 94.5%의 Top 5 Accuracy를 가지는 이 모델은, 마찬가지로 구조가 너무 커서 전체 이미지를 첨부하지는 못하지만 옆의 이미지와 같은 블록이 사용되었습니다. 가장 큰 차이는 Separable Convolution(Depthwise Convolution + 1x1 Point wise Convolution)을 사용하였다는 것 입니다. 마찬가지로 이 방법은 블록의 크기는 유지시키면서 훨씬 적은 수의 파라미터를 사용하였다는 것에 의미를 가질 수 있습니다. 일반적인 Convolution이 아닌 Separable Convolution을 사용할 때의 장점은, 밑의 이미지에서 보이는 것 처럼 인풋 채널의 수만큼의 커널이 각각 채널을 convolution 한다는 것입니다. 

일반적인 convolution을 실행하면 아웃풋 레이어의 채널(예를들어 100개라고 하겠습니다)의 수만큼의 커널이 인풋 레이어의 채널(예를들어 10개라고 하겠습니다)수를 각각 돌면서 convolution을 하지만, (이 예에서는 100*10) Depthwise는 단지 10개의 채널만큼만 convolution을 하기에 계산양을 월등히 줄일 수 있습니다. 마찬가지로 이후에 1x1 컨볼루션을 사용하여 채널수만 늘려주면, 적은 파라미터를 사용하면서도 일반 convolution을 사용했을 때와 똑같은 output shape을 가질 수 있습니다.

 지금까지 AlexNet을 포함하여 5개의 유명한 ImageNet Classification 모델에 대하여 간단히 알아봤습니다. 각각 독특한 특성과 구조를 가진 모델들이지만 전체적으로 공통된 발전 방향을 추구하고 있다고 생각합니다. 첫번째는 어찌됐든 모델의 덩치는 커져야 한다는 것이고, 동시에 그것으로 인한 단점들(많은 파라미터, 길어지는 학습시간)을 줄이기 위해 노력하고 있다는 것입니다. 그리고 오버피팅을 줄이기 위한 Dropout, Batchnormalization 등의 방법, 그것들을 Convolution, Activation 등과 어떤 순서, 조합으로 사용해야 하는가의 등의 연구들도 진행되고 있다는 것을 알 수 있습니다. 

 또한 모델을 학습시키기 위한 Residual Connection과 같은 창의적이고 혁신적인 새로운 아이디어들도 필요하다는 것을 알 수 있습니다. AlexNet의 Convolution으로 인해 이미지 분류 딥러닝 모델들이 폭발적으로 발전되었지만, 한 단계 더 Up하기 위해서는 단순히 모델의 크기를 늘리고 그에 따른 사소한 아이디어들을 더하는 것보다는 Convolution 처럼 엄청나게 획기적인 아이디어가, 그것이 Activation에 적용되던, 규제 레이어에 사용되던 상관없고, 모델안의 어느 곳에서든 또 나타난다면 좋지 않을까 생각을 해봅니다. 단순히 파라미터 조절하고 train image를 augmentaion 하고 그런 것들 보다는, 다시 한 번 Convolution을 능가하는 엄청난 아이디어가 나와서 이미지 분류 모델들을 획기적으로 발전시켜주면 좋겠다는 생각을 해봅니다. 

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문제 정도만 하고 있는데, 속도는 중요하지 않고 꾸준하게만 하자는 생각이다. 화이팅!

어릴 때부터 자연스럽게 윈도우, 갤럭시만 접해온 나는 평생 애플 제품을 안 쓸 줄 알았다.

뭔가 애플 제품은 사용하기 어려울 것 같은 생각이 있었다. 또한 디자인이 워낙 이쁘고 세련되다 보니 기능적인 면은 별로 좋지 않고 뭔가

감성갬성?적인 면만 좋을 것 같다는 선입견이 있었다.

하지만 작년에 아이패드 6세대를 수업 필기용으로 샀는데, 엄청나게 반해버렸다. 기능적인 면도 너무 좋고, 가성비도 갤럭시탭보다 좋을 것 같다는 생각이 들었다!(갤탭을 사용해보진 않았지만 가격이 아이패드에 비해 너무 비싸다...) 이로써 애플에 대한 내 안 좋은 선입견이 많이 사라졌다.

그 후 실리콘밸리에서 AI 인턴 업무를 할 때에, 감사하게도 쿠퍼티노 애플 본사에 다니시는 같은 과 선배님을 뵐 수 있었다. 그 때 선배님께서 

'내가 핸드폰은 갤럭시, 아이폰 다 써봤는데 각각 장단점이 있어서 뭐가 더 좋다라고 말 못 하겠는데, 확실히 노트북이나 데스크탑은 맥북이 윈도우보다 훨씬 더 좋아! 이건 내가 정말 보장해. 맥북은 오랫동안 전원 안꺼도 안 느려져'

라고 말씀을 해주셨다. 그 말씀을 듣고 '오홍 나도 다음에는 맥북을 써봐야 겠다'라는 생각이 들면서도 '맥북은 윈도우랑 너무 달라서 어려울 것 같은데...? 한국에서 윈도우 없이 살 수가 있나...?' 하는 걱정도 들었다.

이후 나는 맥북 프로 2020 13인치 기본형으로 갈아탔다! 몇 일정도 사용을 해봤는데, 지금까지는 정말 대대대대대대만족이다. 난 앞으로 맥북만 사용할 것 같다.

사실 단축키나 키보드 같은 것들이 윈도우와 달라서 처음에 3-4일 정도는 헤매긴 했다. 하지만 적응하고 나니, 정말 맥북이 최고라는 생각이 든다!

일단 간단히 os(operating system)을 비교해보겠다(지극히 주관적인 생각입니당)

난 축구를 좋아하니까 축구팀으로 비유를 해보자면,

윈도우는 무리뉴 시절의 맨유(맹구) , 맥은 클롭의 리버풀(황버풀) 이라고 할 수 있다(진짜 완벽한 비유인듯?)

윈도우가 무겁고 둔탁하고 느리다면, 맥은 가볍고 부드럽고 빠르다.

또한 개발자에게도 맥 os가 훨씬 friendly 한 것 같다. 아무래도 맥 os는 unix 계열에 base를 하고 있다 보니까, 터미널 이용도 윈도우에 비해 훨씬 쉽고 개발 환경을 세팅하는 것도 더 쉽다.

또한 fan 속도 조절이라든지 여러 세팅과 환경을 유저가 customizing 하기에도 맥이 훨씬 좋다! 기본 설정에서 많은 걸 내 마음대로 바꿀 수 있고, 앱 스토어에 여러 개발자분들이 올려주신 좋은 앱들이 많아서 그것들을 이용하기 좋다.

그리고 전원을 끄지 않고 며칠, 몇 주 동안 사용해도 전혀 느려지고 그런 게 없다. 부팅할 때도 정말 빠르다.

진짜 어떻게 이렇게 잘 운영체제를 설계한 걸까 생각이 든다.(개발자들은 힘들었겠지?.... 내 미래인가?)

다음으로 트랙패드로 넘어가겠다. 예전에 영화 '서치'를 볼 때, 아버지가 트랙패드를 쉭쉭 하면서 화면을 요리조리 바꾸시는 것을 보고 '아 저렇게 복잡하고 어려운걸 어떻게 사용하는 거 쥐?' 생각을 했었다. 하지만 직접 사용을 해보니, 이보다 더 쉽고 좋은 건 없다. 정말 마우스가 전혀 필요 없을 정도이다.(오히려 마우스를 쓴다면 더 비효율 적이고 불편할 것 같다) 처음에는 익숙하지 않다 보니까 트랙패드 이용에 애를 먹었는데, 며칠 쓰다 보니까 완벽 적응할 수 있었다. 정말 효율적이고, 마우스를 이동하고 딸깍딸깍 하는데 걸렸던 무수한 시간들을 아낄 수 있어서 너무 좋다.

화면도 13인치지만 dock 내리고 사용하니까 딱히 작다고 느껴지지 않는다. 그리고 난 아이패드가 있어서 맥에서 제공하는 sidecar를 이용해서 아이패드를 듀얼 모니터 형식으로 쉽게 사용하고 있다. 또한 베젤이 얇아서 좋다. 내 예전 lg 노트북은 15인치이기도 하지만 베젤이 너무 넓어서.. 너무 크게 느껴졌었는데 맥북은 얄쌍하다. 하지만 나중에 14인치 정도가 나온다면 사고 싶어 지긴 할 것 같다!

디자인이야 뭐... 아무리 나처럼 디자인 같은 비실용적인 면들은 등한시하는 사람한테도 정말 이쁘고 고결하고 우아하다... 혹시라도 기스 날까 봐 케이스도 살포시 끼웠다.

공인인증서나 정부 홈페이지는 아직 사용해보지 않아서 호환성이 어떻게 될지 잘 모르겠다.(이때는 윈도우를 쓰기로 하겠다) 

정말 아직까지는 단점을 딱히 못 찾겠는 정도이다. 액세서리 비용이 조금 비싼 정도..?

그램이나 삼성의 노트북들도 그렇다고 가격이 엄청 저렴한 건 아닌 것 같다(대충 거의 150만원 +-던데?)

따라서 150마넌(맥북 air는 110만원) 정도의 노트북을 생각하고 있다면, 정말 정말 맥북을 추천한다!

convolution layer을 포함하는 model을 직접 만들 때, convolution 후의 output shape을 이용하여 다음 레이어에 넘겨줘야 하는 경우가 있다. 내 기억에는 좀 더 간단하게 모델을 만들 수 있는 Keras 같은 경우에는 우리가 output shape을 계산해야 할 필요는 없지만(그냥 convolution layer을 계속 쌓으면 알아서 output shape을 계산해서 넘겨주는 것 같다), 더 deep 한 level을 건들 수 있는 tensorflow를 이용하여 model을 만들 때는, Convolution후의 shape을 코드를 짜는 사람이 직접 다음 레이어와 맞춰줘야 하는 경우가 많다.

그래서 convolution 후의 shape을 구하는 공식을 알아보려고 한다. 물론, convolution이 어떻게 계산되는지 잘 모르는 경우에는 직접 작은 예제(ex, 10x10 image, 2x2 filter, stride=1, padding =(1,1,1,1))등으로 한 번 output shape을 계산해 보는 것을 정말 추천한다! 필자는 직접 해봐서 공식을 유도해봤는데, 예전 수능 수학 공부하던 시절이 떠올라서 잠시나마 추억에 젖었었다. 하지만 매번 공식을 유도해서 output shape을 계산할 순 없으니! 공식을 알아보자. 이전에는 계속 까먹어서 매번 구글링을 해서 사용을 했지만(구글링 하면 쉽게 바로 나온다), 블로그도 시작한 겸 여기다가 구글링 해서 찾은 것을 그래도 적어보자 한다.

you can use this formula [(W−K+2P)/S]+1.

• W is the input volume - in your case 128
• K is the Kernel size - in your case 5
• P is the padding - in your case 0 i believe
• S is the stride - which you have not provided.

So, we input into the formula:

Output_Shape = (128-5+0)/1+1 Output_Shape = (124,124,40)

NOTE: Stride defaults to 1 if not provided and the 40 in (124, 124, 40) is the number of filters provided by the user.

[reference: https://stackoverflow.com/questions/53580088/calculate-the-output-size-in-convolution-layer]

한 번 더 정리해보자면, W는 image size다. image의 height, width가 다른 경우(정사각형이 아닌 경우) height과 width를 각각 W에 적용해서 구하면 된다. K는 kernel(filter라고 불리기도 한다) 사이즈이다. P는 얼마큼 패딩을 하는지를 의미한다. S는 스트라이드(필터를 몇 칸 씩 건너뛸 것인지)를 의미한다. 이 공식을 이용하여 output shape을 쉽게 구할 수 있다!

참고로, kernel을 움직이다가 rightmost, bottommost 쪽에 자투리가 남을 수도 있을 것이다. 그때는 padding='same' or padding='valid'(tf & keras 기준) 둘 중 어떤 방식을 사용했는지 체크하고 자투리에 적용하면 된다!(same과 valid가 어떻게 다른지 궁금하다면 구글링을 해보자! 나중에 시간이 나면 저 둘의 차이에 대해 포스팅을 해보겠다)

저번 포스팅에서 대략적으로 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을 해줄 때 어떻게, 무엇을 해줄지만 조금 더 고민하면 문제가 잘 풀릴 것이다.