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