알고리즘 논란은 알고리즘으로 치유를..

개인적으로 알고리즘 관련 논란에 민감한 이유

실무 개발자에게 알고리즘은 덜 중요할까?

알고리즘의 정체, 가치, 그리고 왜 해야 하는가?

알고리즘 논란의 마무리를 위한 에세이..

---

이 전쟁을 끝내러 왔다 - 샹크스 (1)

농담이구요. 

앞으로 글은 아래와 같이 3가지 다른 내용으로 간략히 쓰여질 것입니다. 지금 까지 추상적 대화만 있다고 생각해서 이 글을 쓰는 목적인 알고리즘 그 자체에 대한 이야기가 있습니다. 게운하게 기술이야기로 털고 가자는거죠. 따라서 3번만 필독 혹은 먼저 읽는것을 추천합니다. 이번 알고리즘 이야기의 끝은 알고리즘으로~

1. 인간,개발자
2. vollfeed 님의 토론에 나왔던 흥미로운 기술 이야기 
3. 아하~! 알고리즘 

1. 인간/개발자 

레고

레고를 만드는데 있어서, 이것 저것 직접 다양한 집과 비행기등을 만들어보며, 즐거움을 느끼는 어린이가 있습니다. 그 어린이의 동생은 집을 만들라고 하면 이것 저것 가져다 붙히다가 이내.. 집이 아닌걸 보고 울고 맙니다. 그 어린이의 친구는 만들어진 집을 보며, 이 부분은 이렇게 끼워맞추었더라면 더 빨리 만들 수 있었을 텐데라고 말합니다. 개인적으로 이것 저것 만들 수 있고 즐기는 창조적인 능력을 지닌 어린이가 더 부러우며, 효율성을 찾아내는 친구는 옆에 두고서 가끔 의견을 듣고 싶어집니다.

야구

어떤 야구 주루 코치가 있습니다. 항상 달리기를 강조합니다. 달리기는 야구의 기본이라며, 달리기 하라고 재촉합니다.달리기를 잘하면 니들의 연봉이 달라지고 대우가 달라질꺼라 말합니다. 어느날은 투수코치와 투수진들이 회의하는 곳에 가서 또 강조합니다.. " 달라기는 기본이라고 그것에 따라서 니들 계급이 달라진다고 " , 투수코치는 말합니다. "아 물론 달리기도 하고 있습니다만 , 지금 투구폼에 대해서 좀 더 집중하고 있다고.."  그리고 나서 지명 대형홈런타자들이 모인 곳에 가서 또 말합니다. "달리기를 잘해야한다고.." ....

아마 그는 진정성으로 그런말을 하는 것일 수도 있지만, 주루코치이기 때문에 자신의 밥벌이, 자신의 우물안에서 세상을 바라보기 때문일 수도 있지 않을까? 

개발자들 

대한민국에서 (다른나라는 잘모르겠고) 개발자가 되는것은 비교적 어렵지 않습니다. 따라서 다양한 능력의 사람들이 개발자라는 직업 타이틀을 공통으로 가지고 있습니다.  

의사라는 직업을 가지려면 "면허" 가 있어야하며, 검사도 마찬가지입니다. 하지만 개발자는 그런게 없지요. 그래서 그런지 계급을 나누려는 사람들이 있습니다. 자기가 좀 더 공부한것에 대한 보상심리리고 할까요? 

C 를 갓 배운 대학생은 포인터에 대해서 이해한 후에, 세상을 다 가진 느낌입니다. 그리고 자신이 포인터를 알고 있다는 것에 대해 자부심을 가지죠. 좋습니다. 근데 어느날 그 친구는 포인터가 없는 다른 언어를 하는 사람들을 발견하고는 말합니다. " 포인터가 없는 언어는 언어가 아냐" 라고 자신의 위치를 격상시키려고 노력 합니다.  이런 모습은 비단 포인터 뿐만 아니라 (C 가 가장 단골 소재지만) , 알고리즘도 마찬가지입니다. 알고리즘을 좀 더 많이 공부한 사람은 이렇게 말합니다. "문제 해결을 위해 알고리즘은 너무 중요해, 모두가 해야해" , 인텔CPU 를 공부한 학생은 이렇게 말합니다. "저레벨을 안다는것, 뿌리를 안다는 것은 너무 중요해, 모두가 여기서 파생됬기 때문이지. 모두 알아야해" 

사실 어느정도는 이해해줄만합니다. 하지만 그것을 이용하여 자신의 신분을 상승시키고 싶은, 자신이 우월한 위치에 서고 싶은 군상들은 눈쌀을 찌푸리게 합니다.

" 포인터 없는 언어하는 니들은 B 급 단순코더, 난 개발자"
" CPU 스펙도 안읽어본 니들은 B급 단순코더, 난 개발자"
" The Art of Computer Programming","TCP/IP illustrated" 도 읽어보지 않은 니들은 단순코더"  
" 컴파일러 / 인터프리터 못만들어 본 니들은 단순코더"
" 소형 OS 못만들어본 니들은 단순코더" 
" 대형프로젝트 설계 못해본 니들은 단순코더" 
" 자료구조 라이브러리 직접 만들어 쓰지 않는 니들은 단순코더"
" 수학,영어를 못하면 단순 코더" 
..

.. 좀 더 범위를 벗어나 보면 ..

.. 더 범위를 벗어나 보면 ..

"기술들을 간파하여 창조적 비지니스모델을 만드는 CEO or (기획자) 앞에서는 딥러닝 주구장창 반복적으로 돌리던지, 좋은 라이브러리 만들고 , 최적화, OO설계 잘 한다고 해 바짜 개발자 니들은 나의 톱니바퀴중 하나"  

ㅡ.ㅡ;; 

"자신이 공부한것에 대해, 쉽게 설명해주고 공유하려는 모습" 과 "기술적 측면에서 맞고 틀림을 정확히 분간"하려는 모습에서 존경심,존중심이 생기지,  저렇게 계급화 하려는 저열한 모습에서는 말하는이, 듣는이 모두 아무것도 건질게 없습니다. 아주 찰나의 우쭐함 뿐이겠지요. 

2. vollfeed 님의 토론에 나왔던 흥미로운 기술이야기

다양한 이야기들이 있지만 개인적으로 흥미로웠던것은

 "알고리즘이 문제 해결 전략을 찾는 것에 초점을 맞춘다면, 디자인 패턴을 그 전략을 좀더 모듈화 된 구조로 만드는 것에 초점이 놓이고 있습니다. Flyweight패턴과 Dynamic Programming의 공통점은 없는지요? Back Tracking 전략과 Memento패턴 및 Chain of Responsibility는요?"

이 내용이다. 개인적으로 vollfeed 님 전체 글에서 가장 건질게 있지 않나 했던 부분이라 생각한다. 다른 급 나누는 이야기는 저열해서( 내가 심하게 받아드린다고 생각하는 분도 있음을 인정한다. 하지만 난 더 비판적이다.)  언급할 필요는 없고, "알고리즘은 기본이며, 항상 공부하고 생각해보자" 라는 취지의 주제는 공감하나 너무 당연한거라..재미가 없었다.  자 이런 반감과 공감만 가지고 알고리즘 논쟁을 끝마치기에는 너무 얻는게 없다.

따라서 이번글과 다음글에서는 알고리즘 그 자체에 대해서 좀 생각하는 시간을 갖어보자. 남는게 있어야 할게 아닌가? 

 Flyweight패턴과 Dynamic Programming의 공통점?

동적프로그래밍은 무엇인가?

먼저 동적프로그래밍은 간단히 말해서, "공간을 사용해서, 시간을 단축시키자" 이다, "반복" 되는 시간 낭비를 없애는것인데 다음 그림을 보자. 동적프로그래밍의 적용 예는 최근에 HMM (머신러닝의 한 종류로 주로 시계열 분석에 사용됨) 을 하면서 본 viterbi 알고리즘의 예로 설명한다.

자 Rainy 는 비가 온날이고, Sunny 는 해가 쨍쨍한 날이다. 
비-비-비 가 온날 다음에 비가 올 확률을 계산 하고 
비-비-비 가 온날 다음에 해가 뜰 확률을 계산 할 경우
처음 부터 다시 계산 할 필요 없이 "비-비-비 같은 어차피 동일한 부분에 대한 계산 값을" 미리 저장(공간사용)해두고, 그 계산 값을 다시 계산하는 시간의 낭비를 막는 내용이다. 

즉 "반복되는 계산(시간)을 공간을 이용하여 줄이자"

그럼 Flyweight 패턴은 무엇인가? 

플라이웨이트급,웰터급 같은 복싱용어를 들어 보았는가? 그렇다 플라이웨이트급은 몸무게가 가벼운사람들의 그룹(경량급)을 말한다. 이것을 통해 이 패턴의 의도를 유추 할 수 있을 것이다.

즉 동일하거나 유사한 객체들 사이에 가능한 많은 데이터를 서로 공유하여 사용하도록 하여 메모리 사용량을 최소화(경량화)하는 Gof 디자인패턴 중 하나이다.  그림으로 쉽게 풀어 보면 (실제 패턴은 좀 더 OO 구조적이다.객체는 자신을 경량화 하기  위해 필요한 속성들을 내부에 몌모리로 가지고 있는것이 아니라 외부에서 레퍼런스로 공수한다. 기억하자 객체는 속성,멤버변수 보관자가 아니라 어떤 서비스를  제공하냐로 의미를 가진다.)

어느 소설에서 Hello 라는 글자가 나올 때마다 메모리를 할당해 줄 필요가 없다. 기존에 Hello 를 담고 있는 메모리가 있다면 Factory 에서 그 메모리를 가르키게 참조만 시켜주면 된다. 

혹여나 소설가가 그 중 한 부분을 HI 라고 고치면 그 때서야 Deep Copy 를 해서 다른 메모리를 생성해주면 된다(Copy on Write기법)  

그렇다, 보다시피 Flyweight 패턴은 간단히 말하면 "공간을 절약 시켜주는 패턴이다" , 반복되는 동일한 Value 에 대해 따로 반복적으로 만들지 말자. 따라서 결론적으로 Flyweight패턴과 Dynamic Programming은 시,공간적인 측면에서는 상관이 없으며, 다만 굳이 매칭하려고 한다면 "반복" 이라는 글짜가 눈에 들어오게 마련이다. "반복되는 계산을 줄여줌", "반복되는 할당을 없애줌" 

 Back Tracking 전략과 Memento패턴 및 Chain of Responsibility

이것은 간단히 정리하면  어떤 상태를 저장해 두는것이다. Memento 경우 현재 상태를 저장한 후에 그 상태로 되돌아가기 위한 패턴이다. 편집기에서 Undo/Redo 를 생각해보면 이해하기 쉽다. (참고로 Undo/Redo에는 커맨드패턴을 더 많이 사용한다) 이것은 갈림길에서 한쪽길을 탐색하다가, 다시 갈림길로 돌아오기 위해 갈림길이란 상태를 저장해 두는 모습을 떠오르게 한다. 또한 길을 찾을때 이 갈래의 길 저 갈래의 길을 순회하면서 찾기 때문에 , 다양한 (WAS에서) 각자 다른 책임을 지고 있는 filter 함수를 순회하는 느낌의 Chain of Responsibility 패턴과 일부분 비슷하 뉘앙스를 굳이 찾을 수 있다. 

 3. 아하~! 알고리즘 

내가 좋아하는 수학책중에 하나인 "아하~! 물리수학" 이라는 책의 제목에서 따왔다. 그 책의 저자는 암기식으로 수학을 공부하는 모습을 비판하며, 직접 그 수식이 어떻게 활용되고, 의도가 무엇이고, 어떻게 생겨난것인지에 대해 알려주어, 독자가 감탄사가 나와서, 진정한 이해를 하게 만들려는 책인데 (사실 그래도 수학이어서인지 수식이 가득하다.) 그 제목을 패러디 하여 보았다. 

내용은 내가 연례 행사 (2) 쯤으로 매년 읽곤하는 알고리즘 책인 "생각하는 프로그래밍" 챕터8 에서 따왔다. 이 좋은 책 중에서도 가장 좋아하는 챕터이며, 아하~~~ 라는 말이 가장 어울리는 장이다.

사실 알고리즘 논쟁은 그냥 논쟁에서 그치지말고, 이런 아하~~ 경험을 통해 마무리하는게 좀 남는게 있지 않을까 하여 읽어본 사람에게는 다시 떠올리는 기회를, 안읽어본 분들(알고리즘 자체에 관심이 없었던 분들) 에게는 소개차원에서 글을 써보려한다. 

브라운대학의 Ulf Grenander 는 2차원 패턴매핑문제를 해결하려는 중에 , 2차원은 너무 복잡해서 1차원으로 축소하여 통찰을 얻고자했다. 아래 소개할 알고리즘을 1번 방식으로 해결했으나, 너무 느리다고 판단해서 즉시 알고리즘 2번을 개발하였다.이 문제를 1977년 Shamos 에게 이 문제를 설명했고, Shamos 는 하룻밤 사이에 알고리즘 3을 디자인했다. 그 후 Shamos 가 이 책의 저자(존 벤틀리:스탠포드대학교) 에게 알려주었을 때, 우리는 그 알고리즘이 가능한 최상의 알고리즘이라고 생각했으며 다른 연구원들 역시 그러하였다. 후에 카네기 멜론 세미나에서 이 문제를 여러 다른 사람들에게 설명했을때, "통계학자" 인 Jay Kadane 은 1분만에 알고리즘 4를 만들었다. 

아래 각 알고리즘의 실행시간 표를 확인해보자.

	알고리즘1	알고리즘2	알고리즘3	알고리즘4
10^3	1.3초	10ms	.4ms	.05ms
10^4	22분	1초	6ms	.5ms
10^5	15일	1.7분	78ms	5ms
10^6	41년	2.8시간	.94초	48ms

아하~~우와~~~  41년 걸리는게 있는 반면 1초도 안걸리는 알고리즘이 있다. 

앞으로 이 알고리즘을 같이 풀어 볼 것이지만, 대부분의 개발자들은 알고리즘2로 개발 할 것으로 생각되며, 사실 책에는 알고리즘 4를 어렵다고 써놓았지만, 알고리즘3보다는 훨씬 쉬울거 같다. 데이터를 진득히 오래 바라본다면 말이다. 

놓치기 쉬운 포인트는 통계학자가 풀었다고 책에 간단히 언급되어 있지만, 개인적으로 이 부분에서 아주 크게 감동받았다. 이유가 무엇이냐면, 알고리즘 3는 사실 분할정복알고리즘을 사용하였는데 기초로 공부하지 않은 이상 맨 머리로 생각해내는것은 힘들다고 본다. 그래서 알고리즘에 정통한 개발자라면 분할정복 알고리즘을 통해 해결 할 수 있으리라는 냄새를 맡고 바로 연구에 착수 했을 것이다. 그래서 결국 만들어 낸 알고리즘은 O(nlogn) 수준이다. 꽤 훌륭하다. 알고리즘 열심히 공부한 보람이 있다.  

하지만 통계학자 (즉 알고리즘을 배우지 않았다고 예상해보는) 그는 분할정복을 통해 해결하지 않고, 그 데이터를 면밀히 보았을 것이다. 여기에는 어떤 패턴이 있고, 어떻게 계산되면 쉽게 풀릴 수 있을 것인지를..그 결국 알고리즘 4 (O(n)) 라는 아주 명쾌하고 엄청난 알고리즘을 생각해 낸것이다. 알고리즘 전문가들 컴퓨터 전문가들을 제치고 말이다.

이 부분은 요즘 데이터분석을 하고 있는 나에게 큰 영감을 주었다. 이 책을 처음 산 아주 옛날에는 미쳐 생각하지 못했던 "통계학자" 라는 단어가 최근에 박힌것이다. "통계학자" 보다는 사실 "데이터를 진지하게 관찰하는 사람" 으로 말이다.

물론 정상적인 독자님들 경우" 통계학자가 컴퓨터과학자보다 더 낫다" 라고 주장하는게 아니란 것 쯤은 잘 아실듯하다.이제 변죽을 울려 놓았으니, 그 알고리즘을 풀어보자.

문제

위와 같은 1차원 배열이 있다고 할때, 어디서 부터 시작해서 어디까지 끝나는 경우 그 구간을 합 할때 가장 큰 값을 갖을까? 위의 예에서는 59에서 시작해서 97에 끝나는 경우가 가장 큰 값을 갖는다.

알고리즘1 

maxsofar = 0
for i = [0, n)
    for j = [i, n)
        sum = 0
        for k = [i, j]
            sum += x[k]
        /* sum is sum of x[i..j] */
        maxsofar = max(maxsofar, sum)

즉 처음 0부터 시작해서 0~1, 0~2 이런식으로 계산되고, 그 후에 하나 증가해서 1~2, 1~3  이렇게도 순회한다.
i 가 한바퀴 돌고 (n) 
j 가 한바퀴 돌고 (n)
후에 k 가 또 한 바퀴 돌아서 (n)

O(n^3) 의 알고리즘이 되었다. 이렇게 모든 경우를 다 탐색해서 문제를 풀 수 있었다. 
하지만 너무 오래걸린다. 너무너무~~

알고리즘2

maxsofar = 0
for i = [0, n)
    sum = 0
    for j = [i, n)
        sum += x[j]
        /* sum is sum of x[i..j] */
        maxsofar = max(maxsofar, sum)

알고리즘1에서의 문제는 대부분의 개발자라면 쉽게 무엇이 병목이 었는지 확인 할 수 있을 것이다. 즉 페인트공 문제로써, 기존에 계산해 놓았던 값을 사용안하고, 계속 처음부터 다시 계산한것이 실수 였던 것이다.1,2,3,4,5,6 에 대한 더하기를 할 때 

1+2+3 =6 이 이미 계산되어 나왔는데 1+2+3+4 = 10 을 계산 할 때 첨부터 계산한 것이다. 

그냥 6 + 4 하면 되는데 말이다. 위의 코드는 이런 방식으로 해결 한 코드이다.

즉 저장공간을 할당하여, 반복 계산을 막은것이다. 굉장히 이해가 쉽게 되며, 대부분의 개발자들이 이렇게 해결 했을거 같은 해결책이다.

알고리즘3 

float maxsum3(l, u)
    if (l > u) /* zero elements */
        return 0
        
    if (l == u) /* one element */
        return max(0, x[l])
    
    m = (l + u) / 2
    /* find max crossing to left */
    lmax = sum = 0
    for (i = m; i >= l; i--)
        sum += x[i]
        lmax = max(lmax, sum)
    
    /* find max crossing to right */
    rmax = sum = 0
    for i = (m, u]
        sum += x[i]
        rmax = max(rmax, sum)

    return max(lmax+rmax,
                maxsum3(l, m),
                maxsum3(m+1, u));

이제 O(nlogn) 알고리즘을 보도록하자. 사실 이 알고리즘을 생각 해 내는것은 너무 어렵긴하다.
분활정복의 냄새를 맡는것은 누구나 떠 올릴 법하지만, 실제 문제풀이 말이다. 

즉 어차피 이렇게 a 와 b 로 나누어도, 각각을 알고리즘2 처럼 계산하면 같은 시간이 나오는거 아냐? 어떻게 분할정복이 엄청난 힘들 발휘하지? 라고 말이다.

위의 코드를 보면, a 와 b 를 분할 한뒤에 알고리즘 2 방식을 따른게 아니라, 그냥 다시 또 쪼갰다, 끝까지 쪼개어서 알고리즘2 처럼 O(n^2) 이 아니라, O(n) 을 만들었다. 분활정복하면 O(n) 이 될 것이라고 냄새를 맡았다는게 훌륭하다. 결국 O(n) 에 쪼갠만큼(logN)을 곱하면 이 알고리즘의 성능이 된다. 즉 O(nlogn)이 된것이다.

알고리즘4

대망의 알고리즘4 이다. O(n) 알고리즘, 즉 오직 데이터의 갯수만큼만 시간이 필요한 알고리즘이다. 끝판왕이다.

int maxContiguousSubsequence(int[] a){
  int maxSoFar = 0;
  int maxEndingHere = 0;
  for(int i = 0; i < a.length; i++){
    maxEndingHere = Math.max(maxEndingHere + A[i], 0);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return maxSoFar;
}

for 문이 하나이다. 즉  데이터의 싸이즈 만큼만 순회하고 끝!! 따라서 그냥 n 만큼만 계산하는것이다.
이제 저 알고리즘을 이해해보자. 아래와 같은 데이터가 있다.

문제를 풀기 전에 데이터를 계속 뚜러지게 바라보자. 패턴인식에서는 데이터를 많이 보면 볼 수록 해답을 얻을 수 있다.  자~~ 어디서 부터 어디까지 더해야지 가장 큰 값이 나올것인가..~~ 어느 중간지점을 살펴보기도 할 테지만 힌트를 주면 중간지점부터 볼 필요가 전혀 없다. 이것은 그냥 앞에서 부터 계산하면 답이 나오는 문제이다.

1. 54 와 -64를 더한다. 
2. -10이네? 0 보다 작으면 무시하자. 
3. 6부터 시작한다.
4. 6과 24를 더한다. 30이 나온다. (저장) 
5. 30과 -91을 더한다. -61이네? 0보다 작으니깐 무시하자.
6. 74부터 시작. 어랏 74가 끝이네?

답은 74 

정말 명쾌하고 간단하다. -.-;;  저걸 누군가가, 분할정복알고리즘으로 짜놓았다면  성능은 for 문 2번 돌린것보다는 좋아졌지만 정말 이해하기 어려운 코드였을 것이다.(3) 

이상으로 아하~ 알고리즘을 살펴보았습니다.

이 예를 통하여 얻었으면 하는것은 분활정복 알고리즘도 아니고, 공간을 낭비해서 시간을 벌자라는 것도 아니고,아하~~ 입니다. 몇십년 계산이 걸리는것이 1초도 안되서 해결되는 구나 하는 놀라움과 재미일 뿐이죠. 놀라움과 재미를 느끼면 그 이후의 것들은 알아서 하게 될 것으로 생각합니다. "공부를 하라는 훈계질, 급을 나누는 저열한 짓" 은 필요 없죠...

마지막으로

독자님들 소프트워어 개발을 하는데 있어서 아하!! 상황을 많이 만나서  더 짜릿한 개발자의 삶이 되길 바랍니다.^^

---

1) 나는 원피스를 한번도 읽어보지 않았지만, 캐릭터들은 알고있다. 매력적인 캐릭터 매력의 힘이란 대단하다.

2) 내가 매년 연례행사로 읽는 책이 2권이 있다. 첫째 . 생각하는 프로그래밍  둘째. 홀럽의 실용주의 디지인패턴

3) 글의 의도와 관련하여 몇몇 제외된 코드가 있습니다. 전부 마이너스인 경우도 그런 경우로 이에 대비해서 가장 큰 수를 구하는 로직이 추가되도 O (n)에서 벗어나진 않을거 같습니다. 다른 정보를 위해서는 Programming Perls (번역서: 생각하는 프로그래밍) 을 참고하십시요.