[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 객체를 반환한다.

[Objective-C 문법] 블럭 (Block)

요즘 Concurrent programming을 드려보다가 자주 쓰는데 쓰려고 하면 생각이 안나는 이상한(?!) 문법하나 적어두려고 이렇게 포스팅하게 되었다.

애플에서는 C 함수와 생김새가 비슷한 블럭 객체를 NS계열의 라이브러리에 많이 사용하고 있는 것을 볼 수 있다. 개인적으로는 Delegate을 쓸까 Block을 쓸까 고민을 많이 하는 편인데, 이제는 어느정도 머리에 확립이 되었다. 재사용해야하는 경우에는 클래스 기반의 Delegate을 사용고, 한번 사용할 로직이라면 보통 블럭을 사용하고 있다.

혹시 이 글을 읽으시는 분 중에서 더 좋은 경우가 있다면 댓글을 달아주시면 고맙겠다.

암튼. 그럼 블럭인 무엇인지 살펴보자.

Block (블럭)

O’REILY에서 나온 ‘iOS 7 Programming Cookbook’의 저자는 블럭을 다음과 같이 정의했다.

“Block objects are package of code that usually appear in the form of methods in Object-C.” (블럭 객체는 보통 Objective-C에서 메서드 모습을 한 코드 패키지이다.)

만약 누군가 개인적으로 블럭을 정의하라고 한다면 나는 아마 이렇게 대답할 것이다.

“블럭은 로직을 객체화해주는 또 다른 하나의 매커니즘이다.”

물론 Objective-C 프로그래밍은 Foundation에서 지원해주는 NSInvocator라는 클래스를 제공하고 있다. 하지만 보다 간편하게 사용할 수 있기 때문에 사용 빈도가 점점 늘어나고 있다.

어떻게 생겼나?

그럼 이제부터 본격적으로 문법에 대해서 알아보자. 다음은 Objective-C 스타일의 메서드와 C 함수 스타일, 그리고 블럭 스타일의 코드를 보여주고 있다.

 

  1. //#1. Objective-C Style
  2. - (void)CanCallThisBlock:(NSString *)strVal
  3. {
  4.     NSLog(@"strVal: %@", strVal);
  5. }
  6.  
  7. //#2. C style
  8. void CanCallThisBlock(NSString *strVal)
  9. {
  10.     NSLog(@"strVal: %@", strVal);
  11. }
  12.  
  13. //#3. Block
  14. void (^CanCallThisBlock)(NSString *) = ^(NSString *strVal)
  15. {
  16.     NSLog(@"strVal: %@", strVal);
  17. };

 

그리고 자주 사용하는 문법 중 하나는 typedef를 사용하여 컴파일러에게 블럭의 시그니쳐를 알려주는 코드는 다음과 같다.

  1. typedef void(^CanCallThisBlock)(NSString *);

위 코드의 내용은 클래스 내에서 인터페이스 확장자(Interface extension: ‘@interface ViewController()’) 내에 선언된 메서드의 선언문과 동일한 역할을 한다.

특징

블럭 밖에서 선언된 변수는 블럭 안으로 들어오면 ‘__block’ 예약어가 없는 한 read_only 속성으로 copy가 된다. 다음 코드를 살펴보자.

  1. NSUInteger intVal = 10;
  2.  
  3. CopyTest block = ^
  4. {
  5.     NSLog(@"#1. intVal = %d", intVal);
  6. };
  7.  
  8. intVal = 20;
  9.  
  10. //Test Final Result
  11. block();
  12. NSLog(@"#2. intVal = %d", intVal);
  13.  
  14. //결과:
  15. //#1. intVal = 10
  16. //#2. intVal = 20

위 코드를 보는 것 같이 intVal 변수는 ‘__block’이라는 예약어 없이 선언이 되어 있다. 그렇기 때문에 값이 변경 전의 값인 10가 그대로 남아있는 것이다.

그 밖에…

iOS 7이 나오면서 Objective-C 문법 자체에도 더 강화가 되어서 업데이트가 되었다. 사실 iOS 6를 사용해서 개발할 때만 해도 블럭 안에서 self를 사용할 수가 없었다. 그렇기 때문에 사용하기 위해서는 __block으로 선언한 변수를 하나 만들어서 사용을 하던지, 블럭을 정의 할 때 파라미터로 self를 받아서 사용을 했었다. 그런데 최신 버전에는 그런 걱정 없이 정상 작동을 하고 있다.

블럭을 변수에 할당 해서 사용을 하든지 inline(인라인)으로 사용을 하든지 개인적으로 가장 중요하다고 여기는 것은 가독성(Readability)인 것 같다. 블럭을 사용하는 순간, 화면에 뭔가 모를 걸리적 거림이 있는 것은 나 혼자 뿐일지 모르겠지만, 분명 블럭을 사용함에 있어서 깔끔한 느낌을 덜 주게 되는 것은 사실이다. 적당히 알맞은 장소에서 사용을 한다면 정말 강력한 무기가 될 것이고 그렇지 않고 모든 부분에서 블럭을 사용한다면 디버깅 뿐만 아니라 코드를 유지보수하는 측면에서 어려움을 맛 볼 것으로 여겨진다.

Updated December.19.2013

TDD로 개발 중 블럭을 Unit Test하기 위해 리서치를 하다가 못보던 블럭 문법을 발견하여 업데이트 하게 되었다. 블럭은 code에 inline 되어지기 때문에 여간 테스트하기 어려운 존재였는데, 좋은 방법을 찾았다. 다음과 같이 블럭을 메서드화 시켜서 선언해 사용하도록 하자.

  1. //Header 파일에는 다음과 같이 선언한다.
  2. - (void(^)(NSString *))instanceBlock;
  3.  
  4. // .m 파일에는 다음과 같이 정의한다.
  5. - (void(^)(NSString *))instanceBlock
  6. {
  7.     return ^(NSString *str)
  8.     {
  9.         NSLog(@"Output: %@", str);
  10.     };
  11. }
  12.  
  13. //그리고 Test 파일에서 사용할 때는 다음과 같이 사용한다.
  14. [myInstance instanceBlock](@"helloBarty!");

이 기법을 배운 포스트이다. 재사용 가능할 뿐만 아니라 테스트 가능하며, 그리고 가독성도 높여주는 좋은 방법이다.

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