Simple in Complex with Simple

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. 코드는 레고처럼 조립 가능하게, 그리고 스위스 시계처럼 정말 정교하고 섬세하게.