Simple in Complex with Simple

1. 개요

 프로그래밍 공부를 하다보면 리커젼 기법을 반드시 만나게 된다. 그리고 이 부분에서 수 많은 탈락자가 발생한다.

마치 C언어의 배열, 포인터, 그리고 파일 입출력, 자료구조의 뒤를 잇는 허들이다. 나 역시 리커젼을 아직도 완벽히

이해를 못한다. 단순히 기초만을 알 뿐이다. 하지만 이번에 내 스승님이 된 책을 읽으면서 리커젼의 기본적인 틀을

배웠다. 바로 이렇다.

 스승님이 말하셨다. 모든 리커젼을 이 틀에서 벗어나질 못한다.

 if ( 종료 조건 )

return 종료 값

 else if ( 또 다른 종료 조건 )

return 또 다른 종료 값

 else

return ( 몇 가지 작업 ) and then ( 재귀 호출 )

 정말이지 위대한 틀이다. 이 틀에 가장 적합한 부분은 합, 팩토리얼, 피보나치 수열이다. 이 세 가지 기법은 모두

기업 면접과 시험에 다 만나봤다. 그렇기 때문에 반드시 숙지해야한다. 나한테 하는 말이다. 특히 우리나라에서

가장 큰 게임 기업의 면접 코딩 문제 중 하나로 리커젼을 통한 1부터 n까지의 합을 구하는 문제가 있었고 또 다른

가장 큰 게임 기업의 필기 시험 문제에서는 피보나치 수열을 리커젼으로 풀 때 문제점과 반복문으로 바꾸는 문제

가 있었다. 물론 나는 잘 풀었다. 그래서 합격했다.

 1부터 N까지 합을 구하는 코드를 리커젼으로 작성하면 이렇다. 

 int Function ( int n ){

if ( n == 0 )

return 0;

else 

          return n+Function(n-1);

 }

 정확히 위의 표현식과 일치한다. 

 만약 내가 스승님을 좀 더 빨리 만났다면 그 면접 시간에 이 코드를 작성하지 못해 허둥대고 당황하고 식은 땀을

흘리면서 세상에서 가장 길면서도 짧았던 그 면접 시간을 안느끼고 순식간에 풀어냈겠지.

 반드시 위의 표현식을 기억하자 !!

 그리고 또 하나 반드시 익혀야 할 것! 

 모든 리커젼 기법은 반복문으로 작성할 수 있다. 이것도 연습해야 한다. 이를 해낼 수 있을 때 실력이 한층 발전한다.

2. 재귀 vs 반복

 (1) 일반적으로 반복 방식이 재귀보다 성능면에서 효율적이다. ( 재귀 방식은 함수 호출의 오버헤드가 크다. )

 (2) 그럼에도 재귀를 쓰는 이유는 몇몇 문제에서 명확한 반복 알고리즘이 존재하지 않을 수 있다. 또한

     몇몇 문제에서 반복적인 방법들 보다 재귀적인 해결책이 가장 적합할 수 있다.

 (3) 재귀 코드는 반복 코드보다 짧고 쉽다. 그러므로 메모리 공간을 써서 가독성을 높이는 결과를 만든다.

 (4) 재귀 코드는 자신을 호출할 때마다 원래 문제의 범위보다 조금씩 줄어들어야 한다. (반드시!)

 (5) 재귀 코드의 비효율적인 문제를 해결하기 위해서 동적 프로그래밍(Dynamic Programming)이 등장했다.

     이는 재귀 코드의 시간을 획기적으로 줄일 수 있다. ex) 2^n을 n^2이나 또는 n^2을 nlogn으로 풀어낸다.

 3. 결론 

  (1) 재귀와 반복이 싸우면 반복이 우세하다. 하지만 나중에 나오는 동적 프로그래밍을 위해서 재귀는 필수다.

  (2) 하지만 동적 프로그래밍은 나중에 어마어마하게 사용된다. 기업 코딩 시험에서도 안나오는 경우가 거의 없다.

  (3) 즉, 재귀 공부를 미치도록 하자! (어지간한 문제는 재귀로 다 풀린다.)

1. 코드

2. 결과

3. 해설

 하노이 타워 알고리즘은 규칙은 단 하나다. 큰 판이 작은 판보다 위로 쌓을 수 없다. 이 규칙을 준수하면서

출발지에서 목적지까지 탑을 크기에 맞게 고르게 쌓아야 한다.

 이 알고리즘은 컴퓨터공학 4년 내내 나에게 큰 어려움이었다. 왜냐하면 리커젼 기법에 대해서 아무것도

모를 때 배운 이 알고리즘은 그 당시의 내게 전혀 이해되지 않았고 그 때 느낀 막연한 두려움은 계속 내

마음을 잠식했기 때문이다. 그래서 이해하려는 노력을 해도 너무 어렵게만 느껴졌는데 하나의 아이디어를

만나고 이 알고리즘에 대해서 정확히 이해할 수 있었다.

 아이디어는 이렇다. 

 1. 맨 마지막 판을 제외한 나머지 판을 중간 경유지로 옮긴다.

 2. 맨 마지막 판을 목적지로 옮긴다.

 3. 중간 경유지에 있는 나머지 판들을 목적지로 옮긴다.

 뭔가 과정이 굉장히 생략되어 있는 느낌이다. 하지만 리커젼은 단순하게 따져보면 반복의 틀이다. 즉, 

위의 아이디어를 계속 반복한다. 전체 판이 3개라면 나머지 2개를 경유지로 옮기고 마지막 하나를 옮긴다.

그리고 다시 중간 경유지의 2개 판이 이 알고리즘의 시작이되어 그 때의 기준으로 다시 1개 판을 중간 

경유지로 옮기고 나머지 하나를 목적지로 옮긴다. 

 이 아이디어를 쉽게 이해할려면 출발지, 중간 경유지, 목적지가 하나의 리커젼을 돌 때마다 상대적으로

변한다는 것을 이해해야 한다. 고정된 틀인 파라미터와 그 안의 내용을 뜻하는 알규먼트의 차이와 같다.

 결론적으로 이 식을 간략화 하면 2개의 리커젼 함수에 길이가 하나씩 줄게되므로 감산 정복 마스터정리다.

 F(n) = 2F(n-1) + C

 이를 마스터 정리에 대입하면 n*2^(n/1) 이므로 최종적으로 O(2^n)이 된다.

1. 코드

2. 결과

3. 해설

 이 알고리즘은 각 진법의 모든 문자열을 출력하는 알고리즘이다. 리커젼 기법을 사용해서 출력한다.

 리커젼 기법의 시간 복잡도를 알아내는 기법으로 마스터 정리가 있다.

 리커젼에 대한 마스터 정리는 2개가 있는데 먼저 분할 정복 마스터 정리와 감산 정복 마스터 정리가 있다.

 분할 정복 마스터 정리의 수식은 보통 F(n) = F(n/k) + C 이고, 

 감산 정복 마스터 정리의 수식은 보통 F(n) = F(n-k) + C 이다.

 위 코드를 마스터 정리에 대입하면 수식은 F(n,m) = m*F(n-1) + C 이므로 계산하면 

 앞의 계수가 2진법일 경우에는 O(n*m^(n-1)) 이다. 즉, 2진법을 구하는 경우에는 O(2^n) 시간이 걸린다.

 (흔히 시간이 2^n일 경우에는 사용할 수 없는 알고리즘이지만 이 경우에는 이것이 최선이다.)

 최종적으로 이 코드의 시간은 O(k^n) 시간이 걸린다.

 왜냐하면 보통 이런 식으로 추출하는 스트링의 길이는 길지 않기 때문이다. 8의 길이로는 2^8이므로 충분히 계산 할 만하다.

하지만 길이가 길어지면 너무나 오랜 시간이 걸리기 때문에 쓰지 못한다.

3가지 필수

1. 코딩전에 분석하고 설계해라!

 코딩은 건물을 짓는 일이다. 건축에서 중간에 설계가 변하면 모든 것을 다 바꿔야 하듯( 안 바꾸면 그게 부실공사다. ) 코딩도 중간에 설계가 변하면 

부실 코딩이 된다. 이는 나중에 어마어마한 대가를 불러오게 된다. 그러니 코딩전에(짓기전에) 설계하자!

2. 모르면 검색해라! 단, 구글에서 영어로 검색해라.

 정말 구글이 개발자들에게 왜 신이라고 불리는지 알고싶다면 영어를 사용해라. (부모님께서 왜 그렇게 영어를 공부하라고 하셨는지 알았다.) 

영어울렁증을 하루 빨리 탈출하고 문제가 생기면 최선을 다해서 그리고 빠르게 해결하고 넘어가자.

3. 명확해라!

 코드 전체의 흐름, 주석의 내용, 함수의 이름, 변수의 이름 모든 것을 명확하게 지어라! (각, 명칭을 짓는 팁이나 기법은 아래에서)

스스로에게의 팁

1. 변수의 이름은 8~20자 또는 10~16자가 적당하다. ex) newNumOfPlayer (O), np (X), nNoP(X)

2. 함수의 이름은 맨 앞에 명확한 행동을 의미하는 동사부터 시작해라. ex) Calc~, Check~, Is~, 

3. 주석 제외하고 한 기능에 코드 50줄이 넘어가면 그건 기능을 더 최소 단위로 분할할 수 있다는 것.

4. 분명 내가 짠 코드보다 더 좋은 코드가 구글에 존재한다는 걸 알자.

5. 코드는 레고처럼 조립 가능하게, 그리고 스위스 시계처럼 정말 정교하고 섬세하게.