[Question] isBalancedTree?

문제: 인자로 들어오는 Binary Tree는 Balanced인가 아닌가를 구분하는 함수를 만들어라.

문제를 풀기 앞서 몇 가지 개념 정리를 해야 할 것 같다. Binary 트리라 불리는 이진트리 데이터 구조는 무엇인가? 이진 트리는 0개 혹은 1개, 2개의 자식노드를 같는 트리를 말한다. 그럼 해당 데이터 구조가 균형잡히다, 라는 것은 무슨 뜻일까? Balanced하다 하는 것은 자신의 자식노드의 깊이의 차이가 1보다 많아서는 안될 때 균평 잡힌 이진트리이다. 라고 말한다.

Screen Shot 2016-01-07 at 11.35.58 AM

위 예제는 균형잡힌 이진트리이다. 왜냐하면 모든 노드의 자식노드들의 깊이 차이가 1을 넘어 서는 것이 없기 때문이다.

Screen Shot 2016-01-07 at 11.36.09 AM

위 예제는 균형잡힌 이진트리가 아니이다. 왜냐하면 1의 자식들의 깊이의 차이가 1보다 큰 2이기 때문이다.

그렇다면 균형잡힌 이진트리를 찾기 위해서 어떻게해야 할 것인가? 고민해보자.

주먹구구식으로 먼저 생각을 해보자. 모든 노드의 자식의 차이를 구하고 그의 차이가 1 보다 큰 것이 나오면 false를 그 이외의 것들은 True를 반환하면 된다.

아래 답을 보기 전에 먼저 손수 풀어보자. 효율적인 함수를 짜기 위해서는 고민을 좀 해봐야 할 것이다. 왜냐하면 노드의 깊이도 구해야 할 것이고 Bool 값도 반환하고 싶을 것이기 때문이다.

이 문제의 팁은 -1를 통해 깊이 계산과 동시에 불균형를 표시하는 것이다.

  1. - (BOOL)isBalanced:(Node *)rootNode{
  2.     if([self getNodeDepth:rootNode] == -1){
  3.         return NO;
  4.     }
  5.     return YES;
  6. }
  7.  
  8. - (NSInteger)getNodeDepth:(Node *)node{
  9.     if(node == nil){
  10.         return 0;
  11.     }
  12.  
  13.     NSInteger leftDepth = [self getNodeDepth:node.left];
  14.     if(leftDepth == -1){
  15.         return -1;
  16.     }
  17.  
  18.     NSInteger rightDepth = [self getNodeDepth:node.right];
  19.     if(rightDepth == -1){
  20.         return -1;
  21.     }
  22.  
  23.     NSInteger depthDiff = Abs(leftDepth – rightDepth);
  24.     if(depthDiff > 1){
  25.         return -1;
  26.     }
  27.  
  28.     return Max(leftDepth, rightDepth) + 1;
  29. }

[Recursive Questions] Print all combination of Parenthesis

Combination 문제는 Permutation 문제의 응용문제라고 할 수 있다. 재귀함수 호출에 의한 문제 풀이를 한번 알아보자.

문제: 괄호의 수를 의미하는 integer 값을 입력을 받아 가능한 괄호의 조합을 프린트해주는 함수를 짜보자. 예를 들어 3을 입력으로 넣었다면, ((())), (())(), ()(()), (()()), ()()() 문자열이 프린트 되어야 한다.

#Walk through
0. 함수의 인자 값으로 다음과 같이 받을 것이다. (leftRemain, rightRemain, str)
1. [Base condition] 만약 rightRemain의 수가 0이라면, str을 프린트한다.
2. 만약 leftRemain가 0보다 큰지 확인한다.
2-1-a. 크다면, leftRemain을 하나 줄인 다음 str에 “(“를 추가해서 재귀 함수를 호출하자.
2-1-b. 만약, leftRemain가 rightRemain 보자 작은지 확인하자.
2-1-b-i. 작다면, rightRemain을 하나 줄인 다음 str에 “)”를 추가해서 재귀 함수를 호출하자.
2-2. 작다면, rightRemain을 하나 줄인 다음 str에 “)”를 추가해서 재귀 함수를 호출하자.

  1. - (void)printAllCombinationOfParenthesisWrapper:(NSInteger)numberOfPar{
  2.     [self printAllCombinationWithLeftRemain:numberOfPar
  3.                                     rightRemain:numberOfPar
  4.                                          string: @""];
  5. }
  6.  
  7. - (void)printAllCombinationWithLeftRemain:(NSInteger)leftRemain
  8.                               rightRemain:(NSInteger)rightRemain
  9.                                    string:(NSString *)str{
  10.     if (rightRemain == 0){
  11.         NSLog(@"%@", str);
  12.         return;
  13.     }
  14.  
  15.     if(leftRemain != 0){
  16.         [self printAllCombinationWithLeftRemain:leftRemain-1
  17.                                     rightRemain:rightRemain
  18.                                          string: [str appendString:@"("]];
  19.         if(leftRemain < rightRemain){
  20.             [self printAllCombinationWithLeftRemain:leftRemain
  21.                                         rightRemain:rightRemain-1
  22.                                              string: [str appendString:@")"]];
  23.         }
  24.     }
  25.     else{
  26.         [self printAllCombinationWithLeftRemain:leftRemain
  27.                                     rightRemain:rightRemain-1
  28.                                          string: [str appendString:@")"]];
  29.     }
  30. }

[Algorithm 관련] Reverse singly linked list

http://cslibrary.stanford.edu/109/list.gif

http://cslibrary.stanford.edu/109/list.gif

링크드 리스트는 Singly Linked list와 Doubly Linked list 타입을 갖는 데이터 구조이다. Singly Linked list는 자신의 값과 자신의 다음의 Node의 레퍼런스를 가지는 구조이며, Doubly Linked list는 자신의 값과 자신의 전의 Node의 레퍼런스와 자신의 다음에 이어지는 Node의 레퍼런스를 가지는 구조이다. 한번의 연속된 메모리를 할당하지 않는 특성을 가졌지만, Traverse를 하기에 꽤 비싼 비용이 드는 데이터 구조임에 틀림 없다.

Singly Linked list에서 어떻게 하면 reverse를 시킬 수 있을 까? 이것이 오늘의 알고리즘의 문제이다.

Time Complexity를 O(n)으로 풀수 있는 iterative한 방법이다. 먼저, 세개의 node를 저장할 변수를 만든다. prvNode, crrNode, nextNode. crrNode가 nil 아닐 때 까지 Loop를 돈다. 그러면서 치환을 통해 리스트를 반대로 돌릴 수 있다. 다음은 Objective-C 코드이다.

  1. - (LLNode *)reverseLinkedList:(LLNode *)header
  2. {
  3.     if (header == nil) {
  4.         return nil;
  5.     }
  6.  
  7.     LLNode *prvNode = nil;
  8.     LLNode *crrNode = header;
  9.     LLNode *nextNode;
  10.  
  11.     while (crrNode != nil)
  12.     {
  13.         nextNode = crrNode.next;
  14.         [crrNode setNext:prvNode];
  15.         prvNode = crrNode;
  16.         crrNode = nextNode;
  17.     }
  18.  
  19.     return prvNode;
  20. }

[Algorithm 관련] 순열 Permutation -Recursively-

신발 끈을 묶는 방법을 글로 쓰라고 하면 써볼 수 있겠는가? 저자는 자신이 없다. 글 재주가 없어서 그럴수도 있고 혹은 손에 익은 기술을 한번도 말로 표현해보려 하지 않아서 일지도 모른다. 순열, 즉 permutation 알고리즘 문제가 저자한테는 같은 느낌이다. 종이 위에 써보라고 하면 큰 어려움 없이 써 내려 갈수 있지만 막상 pseudo 코드나 과정을 설명하는 글을 써보라고 하면 자신이 없다.

먼저 permutation가 무엇인지 알아보자. 영어로 anagram이라고 표현하는 것도 보았다. 간단한 예를 들어 설명을 하자면 ‘ABC’의 순열은 다음과 같다.

ABC, ACB, BAC, BCA, CAB, CBA

알파벳 순서를 바꾸어서 만들어 낼 수 있는 String들을 말한다. 참고로 n개의 알파벳의 permutation 수는 n! 이다. 위 예는 알파벳 수가 3개이므로 3 * 2 * 1 = 6개의 조합이 나올 수 있다. Permutation을 구하기 위한 가장 쉬운 방법은 ‘각각의 알파벳 하나씩을 시작으로 하는 permutation’의 조합을 찾으면 된다. 무슨 말인지 모르겠다면 다음를 한번 살펴보자:

for(each possible starting letter) {list all permutation that start with that letter}

for 반복문 (각가의 처음에 시작 가능한 글자들) {해당 글자로 시작하는 모든 순열 리스트}

보통 재귀함수를 사용할 때는 for문과 같은 반복문을 사용하지 않는다. 왜냐하면 재귀적 호출 자체가 반복하는 것이기 때문이다. 하지만 permutation 문제에서는 예외라고 할 수있다. 시작 가능한 각각의 글자를 반복 문으로 돌면서 그 속안에서는 해당 글자로 시작하는 모든 순열을 재귀적 호출로 만들어 내는 것이다.

재귀적 함수의 기본으로는 기본 조건(Base condition)이라는 것이 있다. 이것은 무한 반복이 되지 안도록 탈출구를 만들어 놓은 것인데, 해당 알고리즘에서도 for 반목문을 사용하지만 동일하게 base condition이 존재해야한다.

  1. // Pre-condition: str is a valid C String, and k is non-negative
  2. //                            and less than or equal to the length of str.
  3. // Post-condition: All of the permutations of str with the first k
  4. //                             characters fixed in their original positions
  5. //                             are printed. Namely, if n is the length of str,
  6. //                             then (n-k)! permutations are printed.
  7. void RecursivePermute(char str[], int k);
  8.  
  9. for (j=k; j&lt;strlen(str); j++) {
  10.     ExchangeCharacters(str, k, j);
  11.     RecursivePermute(str, k+1);
  12.     ExchangeCharacters(str, j, k);
  13. }

위 Pseudo 코드를 살펴 보면 k라는 non-negative 인수가 있다. 이것은 첫 번째 글자의 인덱스를 저장한 parameter이다. 반복문을 돌면서 permutation을 구할 때는 자리를 바꾸면서 구할 것이고, k 값이 str의 길이와 같으면  출력을 하고 끝낼 것이다.

  1. void RecursivePermute(char str[], int k) {
  2.  
  3.      int j;
  4.  
  5.      // Base-case: All fixed, so print str.
  6.      if (k == strlen(str))
  7.          printf("%s\n", str);
  8.  
  9.      else {
  10.  
  11.          // Try each letter in spot j.
  12.          for (j=k; j<strlen(str); j++) {
  13.  
  14.              // Place next letter in spot k.
  15.              ExchangeCharacters(str, k, j);
  16.  
  17.              // Print all with spot k fixed.
  18.              RecursivePermute(str, k+1);
  19.  
  20.              // Put the old char back.
  21.              ExchangeCharacters(str, j, k);
  22.          }
  23.      }
  24. }

위 코드는 c 코드이다.

  1. @implementation ViewController
  2.  
  3. - (void)viewDidLoad {
  4.     [super viewDidLoad];
  5.  
  6.     [self printPermutation:@"abc"];
  7. }
  8.  
  9. - (void)didReceiveMemoryWarning {
  10.     [super didReceiveMemoryWarning];
  11.     // Dispose of any resources that can be recreated.
  12. }
  13.  
  14. #pragma mark – Private methods
  15.  
  16. - (void)printPermutation:(NSString *)str
  17. {
  18.     [self permutationHelper:str index:0];
  19. }
  20.  
  21. - (void)permutationHelper:(NSString *)str index:(NSInteger)k
  22. {
  23.     if (str.length == k) {
  24.         NSLog(@"%@", str);
  25.         return;
  26.     }
  27.  
  28.     NSInteger idx;
  29.  
  30.     for (idx = k; idx < str.length; idx++)
  31.     {
  32.         NSString *swappedStr = [self swapString:str onIndex:idx withNewIndex:k];
  33.         [self permutationHelper:swappedStr index:k+1];
  34.     }
  35. }
  36.  
  37. - (NSString *)swapString:(NSString *)str onIndex:(NSInteger)idx withNewIndex:(NSInteger)k
  38. {
  39.     unichar charForIdx = [str characterAtIndex:idx];
  40.     unichar charForK = [str characterAtIndex:k];
  41.  
  42.     NSString *strForK = [NSString stringWithCharacters:&charForK length:1];
  43.     NSString *tmpStr = [str stringByReplacingCharactersInRange:NSMakeRange(idx, 1)
  44.                                                     withString:strForK];
  45.  
  46.     NSString *strForIdx = [NSString stringWithCharacters:&charForIdx length:1];
  47.     return [[tmpStr stringByReplacingCharactersInRange:NSMakeRange(k, 1)
  48.                                  withString:strForIdx] copy];
  49. }
  50.  
  51. @end

Objective-C 코드이다.

 

[Algorithm-2] Depth First Search Algorithm

DFS는 그래프 데디터 구조에서 작동하는 검색 알고리즘이다. Tree traversal 알고리즘으로 Breadth First Search 알고리즘과 함께 가장 넓리 알려진 알고리즘이 아닐까 싶다.

그래프(Graph)와 트리(Tree)에 대한 차이점에 대해서 헷갈려하는 사람들이 많다. 트리의 정의를 다음과 같이 해보았다.

“A tree is just a restricted form of a graph. Trees have direction(parent/children) and don’t contain cycle. So trees are ‘Directed Acyclic Graph’ (aka DAG) with the restriction that a child can only have one parent.”

“트리는 표현 방식이 제한된 그래프이다. 트리는 방향이 있지만, 사이클이 없다. 그래서 트리는 자식이 오직 하나의 부모만을 가진 ‘방향성을 가진 비순환적인 그래프(DAG)’이다.”

하지만 DFS와 BFS는 트리 뿐만이 아니라 그래프 자료 구조형에서 작동하는 알고리즘이다. 그렇다면 DFS가 어떤 알고리즘인지 알아보도록 하자.

Depth First Search

먼저 해당 알고리즘은 평균적으로 그리고 최악에 경우 O(|E|)만큼 걸리는 Linear적인 알고리즘이다. (쉽게 말해 Edge의 갯수가 곧 성능이라는 것이다.) 동작 방식은 이름에서 알수 있듯이 트리의 루트 노드로 부터 시작해서 자식 노드가 없을 때 까지 반복해서 visiting하는 알고리즘이다. 만약 재귀적으로 implement하지 않고 iteration으로 코들 작성했다면, 이때 Stack 데이터 자료를 사용하여 자식 노드(Leaf Node)가 나올 때까지 Stack에 push한다. 그리고 더 이상 visit할 수 있는 노드(자식 노드)가 없으면, Stack에서 Pop을 하고 다시 맨 위에 올라와 있는 노드에 unvisited한 노드를 방분하여 다시 (Leaf node)가 나올 때 까지 visit한다. 아래 그림은 wiki에서 캡쳐해 온 이미지이다. 노드 안에 숫자는 visit한 순서를 뜻한다.

Screen Shot 2013-12-23 at 11.09.15 AM

 

 

Objective-C Code

다음은 오브젝티브-C로 작성한 DFS이다. 아래 코드는 재귀적으로 작성한 코드이다.

 

  1. - (BOOL)depthFirstSearch:(NSNumber *)num fromNode:(Node *)node
  2. {
  3.     //#1.
  4.     if (!node)
  5.         return NO;
  6.  
  7.     //#2.
  8.     node.isVisited = YES;
  9.  
  10.     //#3.
  11.     BOOL isFound = NO;
  12.     for (Node *n in node.linkedNodesSet)
  13.     {
  14.         //#4.
  15.         if ([n.value isEqualToNumber:num])
  16.             return YES;
  17.  
  18.         //#5.
  19.         if (!n.isVisited)
  20.             isFound = [self depthFirstSearch:num fromNode:n];
  21.  
  22.         //#6.
  23.         if (isFound)
  24.             return YES;
  25.     }
  26.  
  27.     //#7.
  28.     return isFound;
  29. }

 

코드 설명

  1. 전달된 Input 데이터가 없으면 NO로 반환한다.
  2. 노드의 ‘visited’ 변수를 YES로 설정해주고, 다음에 동일한 노드에 visited 했을 때 사용한다.
  3. 전달 받은 노드의 자식 노드들을 구한다.
  4. 찾고자 하는 Num 변수와 비교한다.
  5. 만약 n 변수가 한번도 visited 한적이 없으면 다시 찾고 있는 변수와 함께 재귀적으로 반복해서 작업한다.
  6. 찾고자 하는 값을 찾았으면 YES 값으로 반환한다.
  7. iSFound 객체를 반환한다.

[Algorithm] Merge Sort

정렬 알고리즘은 CS 수업을 듣게 되면 꼭 한번씩은 접하게 되는 알고리즘일 것이다. CS 학생이 기본을 탄탄히 하기 위해서 꼭 들어야 할 과목을 뽑는다면, Data Structure과 Algorithm을 개인적으로 뽑을 것이다. 하지 아이러니한 것은 실무에 들어가면 High-End 언어들의 편리성으로 크게 고려하지 않거나 고민하지 않은체 개발하는 개발자들이 상당히 많다는 것이다. 하지만 시간이 점점 지날수록 소프트웨어 개발에 경력을 쌓다보면 절대 중요한 과목이며, 기본기가 아닐까 싶다. 그런 의미에서 본인도 알고리즘과 자료구조에 대해 다시 상기하는 마음으로 공부하기 시작했다.

본 포스트는 개인 스터디의 결과물로써 기록하고자 하는 목적과 동시에 가능하다면 많은 사람과 함께 지식 교류를 해보고자 하는 목적으로 블로그에 작성하기 되었다. 내용면에서 부족한 부분이나 틀린 부분이 있다면 주저말고 댓글을 달아주길 바란다.

 

Algorithm이 란?

본격적으로 Merge Sort 알리즘에 대해서 알아보기 전에 간단한 배경 지식을 언급하고 지나가야 할 것 같다. 알고리즘이란, ‘The Algorithm Design Manual’이라는 책을 보면 다음과 같이 정의하고 있다.

“An algorithm is a procedure to accomplish a specific task.”

“알고리즘이란 특정 Task를 완수하기 위한 과정이다.”

사실 소프트웨어 개발 뿐만이 아니라 실생활에서도 많은 일을 처리하기 위해서 여러 과정을 걸쳐 처리를 하고 있다. 하지만 왜 소프트웨어 개발 산업에서 알고리즘을 중요하게 여기는 이유는 한정적인 자원에서 (CPU 성능, 메모리 공간) 효율적으로 더 많은 일을 빠르게 처리하기 위함일 것이다. 같은 결과를 내는 코드를 짜더라도 어떤 방식(알고리즘)으로 짰느냐에 따라 성능과 사용자에게 주는 제품의 인상은 천지 차이이다. 하드웨어의 눈부신 발전으로 많은 개발자들은 크게 고민하지 않고 이득을 보았을지 모르지만, Big-Data 시대에 더 많은 데이터를 더욱 안정적이며 신속하게 전달하기 위해서는 올바른 알고리즘 선택의 중요성을 더욱 실감할 수 있을 것이다.

 

Merge Sort

이제 본격적으로 본 포스트에서 다루고자 하는 Merge Sort에 대해서 설명해보겠다. 위에서 살펴보았지만 정렬 알고리즘 중에서 성능이 좋은 알고리즘 중에 하나로 뽑히는 Merge Sort는 평균과 최악의 경우 O(n log(n)) 만큼 런타임이 걸린다. 이 알고리즘은 배열을 반으로 쪼개고 쪼개어 각각의 절반을 비교하며 합병하면서 정렬하는 방식이다.

그럼 콘셉트를 백번 설명하는 것 보다 코드를 한번 보면서 설명하는 것이 이해를 돕는 것이 헐씬 쉬울 것으로 예상이 된다. 다름은 Objective-C로 짠 Merge sort 알고리즘이다.

  1. - (NSArray *)mergeSort:(NSArray *)unsortedArr
  2. {
  3.     NSInteger numOfItems = unsortedArr.count;
  4.  
  5.     //#1.
  6.     if (numOfItems < 2)
  7.         return unsortedArr;
  8.  
  9.     //#2.
  10.     NSInteger middle = numOfItems / 2;
  11.     NSRange left = NSMakeRange(0, middle);
  12.     NSRange right = NSMakeRange(middle, numOfItems – middle);
  13.  
  14.     //#3.
  15.     NSArray *leftArr = [unsortedArr subarrayWithRange:left];
  16.     NSArray *rightArr = [unsortedArr subarrayWithRange:right];
  17.  
  18.     //#4.
  19.     return [self merge:[self mergeSort:leftArr]
  20.               andRight:[self mergeSort:rightArr]];
  21. }
  22.  
  23. - (NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
  24. {
  25.     //#5.
  26.     NSInteger resultArrCapa = leftArr.count + rightArr.count;
  27.     NSMutableArray *resultArr = [[NSMutableArray alloc]
  28.                                  initWithCapacity:resultArrCapa];
  29.     //#6.
  30.     NSInteger left = 0;
  31.     NSInteger right = 0;
  32.  
  33.     //#7.
  34.     while (left < leftArr.count && right < rightArr.count)
  35.     {
  36.         //#8.
  37.         NSComparisonResult compareResutl = [leftArr[left]
  38.                                             compare:rightArr[right]];
  39.  
  40.         //#9.
  41.         if (compareResutl == NSOrderedAscending)
  42.             [resultArr addObject:leftArr[left++]];
  43.         else
  44.             [resultArr addObject:rightArr[right++]];
  45.     }
  46.  
  47.     //#10.
  48.     NSRange leftRange = NSMakeRange(left, leftArr.count – left);
  49.     NSRange rightRange = NSMakeRange(right, rightArr.count – right);
  50.     NSArray *newLetfArr = [leftArr subarrayWithRange:leftRange];
  51.     NSArray *newRightArr = [rightArr subarrayWithRange:rightRange];
  52.  
  53.     [resultArr addObjectsFromArray:newLetfArr];
  54.     [resultArr addObjectsFromArray:newRightArr];
  55.  
  56.     //#11.
  57.     return resultArr;
  58. }

 

코드 설명

먼저 크게 두 개의 메소드로 나누어 보았다. 첫 번째 ‘mergeSort:’는 배열을 반으로 쪼개주는 역할을 한다. 두 번째 ‘merge:andRight:’ 메서드는 두 개의 배열에 있는 각 요소들을 비교하여 정렬하여 합병해주는 메서드이다. 코드 한줄 한줄을 따라가며 설명하기 전에 알아둬야 할 점은 ‘mergeSort:’ 메서드는 배열에 속한 요소의 갯수가 하나가 될 때까지 재귀적으로 돌아간다는 점을 알면 어떻게 동작하는지 쉽게 알 수 있을 것이다.

  1. 배열의 요소의 갯수가 하나이면 반환을 해준다. 그러므로써 재귀적으로 반복의 종료를 한다.
  2. 인수로 들어 온 배열을 반으로 쪼개기 위해서 다음과 같은 변수를 만들어 준다.
  3. NSRange 객체를 통해 원본 배열을 두 개의 Sub-Array 쪼갠다.
  4. ‘mergeSort:’메서드에서 가장 눈여겨 봐야하는 부분이다. 쪼갠 왼쪽, 오른쪽 배열을 다시 쪼갤 수 있을 만큼 쪼개며, 각각의 반환된 배열을 ‘merge:andRight:’로 넘겨준다.
  5. 합병하여 반환할 배열을 왼쪽 배열과 오른쪽 배열의 요소 갯수를 더한 만큼의 배열을 만들어준다.
  6. 왼쪽 배열과 오른쪽 배열의 요소들을 비교하기 위해서 사용할 인덱스 변수를 초기화 한다.
  7. 두 인덱스가 왼쪽 배열과 오른쪽 배열의 요소 갯수가 안넘는 선 안에서 while문으로 반복이 된다.
  8. 왼쪽 배열의 왼쪽 인덱스에 있는 값과 오른쪽 배열의 오른쪽 인덱스에 있는 값을 비교하여 NSComparisonResult 이넘 형 변수에 대입한다.
  9. 비교 결과 값 변수가 오름 차순이면 왼쪽 배열의 왼쪽 인덱스에 있는 값을 반환 배열에 넣어주고, 내림 차순이면 오른쪽 배열의 오른쪽 인덱스에 있는 값을 넣어준다.
  10. 왼쪽 배열과 오른쪽 배열을 비교하면서 합병을 했지만 한쪽 배열이 반환 배열에 다 들어가게 되면 분명 비교 되지 못한체 아직 기다리고 있는 요소들이 있을 것이다. 그 나머지 요소를 위해 다음과 같은 NSRange를 만들어서 남어지 요소를 반환 배열에 넣어준다.
  11. 정렬된 반환 배열을 전환해주면 메서드는 종료를 한다.

Merge Sort 알고리즘은 뛰어난 성능으로 정렬 알고리즘에서 유명한 알고리즘이다. 물론 실무에서 사용할 일이 정말 있을까 싶지만, 알고리즘을 이론으로만 알고있고, 구현해 본 경험이 없었다면 한번 시도해보길 권유한다. 좋은 알고리즘을 구현해보는 것은 생각보다 만만치 않은 일이지만, 실무하는데 있어서 얼마나 지금까지 생각을 깊게 하지 않고 편한데로만 짰었는지, 자신을 돌아보는 시간이 되지 않을까 싶다. 대학 시절 정말 싫어했던 알고리즘을 경력을 쌓고 다시 보니 지난 세월을 돌아보게하는 좋은 경험인 것 같다. 앞으로는 코드 하나를 짜더라도 한번 더 생각해보고 짜야겠다는 마음을 가져본다.