생각하는 프로그래밍과 알고리즘

나의 책장 한구석에서 한달에 한장정도만 읽히고 있는 아주 오래된 녀석이 있습니다.
생각하는 프로그래밍이란 책인데요, 원래 제목은 Programming pearls, 2 edition 입니다.

이 책은 좋은 알고리즘을 알려주는 좋은 책으로 잘 알려져 있습니다. 여러모로 저도 끼고만 있고 제대로 읽지 못하는 책중에 하나입니다.

각 알고리즘 문제는 정말 좋은 예제들인것 같습니다. 실력이 짧아서 제대로 풀지는 못하지만, 여러분들도 한번쯤 도전해 보면 참 좋을듯합니다.

프로그래밍 본질에 간한 15가지 칼럼을 기반으로 쓴 책입니다.

프랑스의 소설가이자 항공기 디자이너인 Antoine de Saint-Exupery는 "추가할 것이 더 이상 없을 때가 아니라 제거할 것이 없을 때, 디자이너는 완벽함에 도달했다는 것을 알게 된다."고 말했다.

10번째 칼럼에 메모리 절약에 관한 내용이 나옵니다.
지금은 메모리 관리에 대한 이슈가 예전보다 덜하지만 여전히 메모리 관리는 매우 중요한 부분입니다.

네트워크와 관련있는 프로그램의 알고리즘을 설계하고 있다면 더욱 그렇겠지요~

10번째 칼럼의 핵심은 단순함 입니다.
단순함에 대한 좋은 이야기가 나와서 함께 공유하고자 합니다.

Fred Brooks는 1950년대 중반에 어떤 공기업을 위한 급여 프로그램을 작성하면서 단순화의 위력을 알게 되었다. 그 프로그램의 병목은 Kentucky 주의 소득세 표현이었다.

그 세금은 법에서 정한 소득과 공제 항목의 개수에 대한 2차원 테이블로 되어 있었다. 이 테이블을 그냥 저장하려면 수천 워드의 메모리가 필요했고, 이는 머신의 용량을 초과하는 것이었다.

처음에는 Brooks는 세금 테이블을 어떤 수학 함수로 표현하려고 시도했지만, 테이블의 내용이 너무 들쭉 날쭉하여 이를 표현할 수 있는 간단한 함수는 없었다.

법을 만드는 사람들은 매우 복잡한 수학 함수에 소질이 없다는 것을 알았기 때문에, Brooks는 어떤 과정으로 그런 특이한 테이블이 만들어졌는는지 알아내기 위하여 Kentucky 주의 의회의 의사록을 뒤졌다.

그리고 소득세가 소득에서 연방세를 제외한 나머지에 대한 간단한 함수라는 것을 알아냈다. 따라서 그는 이미 존재하는 테이블로부터 연방세를 계산하고, 이를 소득에서 제한 나머지와 수십 워드의 메모리만 차지하는 테이블을 사용하여 Kentucky 주의 세금을 게산할 수 있었다.

Brooks는 문제가 발생한 발생한 컨텍스트를 연구하여 문제를 더 간단히 만들 수 있었다.
원래 문제는 수천 워드의 데이터 공간이 필요할 것처럼 보였지만, 문제를 간단히 만든 후에는 무시해도 좋을 만큼의 메모리만 필요했다.

단순함은 코드가 차지하는 공간도 줄일 수 있다.

이 책의 칼럼 10 중에서

이 책에서 위의 이야기를 보면서 많은 것을 느끼는 시간을 가졌습니다.

흔히 알고리즘은 복잡할 것이라고 생각합니다.
매우 복잡한 수학적인 함수를 통하여 최적의 결과를 산출하는 것이 가장 최상의 알고리즘이라고 생각하는 경향이 있습니다.

그래서 많은 분들이 수학적인 지식을 알고리즘을 잘 구현하는데 꼭 갖추어야 할 조건이라고 말하곤 합니다.
물론 필요합니다.

하지만 위의 이야기에서처럼 컨텍스트에 대한 철저한 분석이 없다만, 과연 수학적인 지식만 가지고 좋은 알고리즘을 만들어 낼 수 가 있을까요?
문제 자체에 대한 근본적인 이해가 없는 상태에서 만든 알고리즘이 과연 단순한 알고리즘보다 메모리도 더 적게 차지하면서 효과적으로 수행된다고 확신할 수 있을까요?


많은 분들이 알고리즘을 검색엔진이나 DBMS 등에 시스템 속에 사는 불을 뿜는 무시무시한 용으로 생각하는 경향이 있습니다. 이 용을 잡아서 이용하려면, 원탁의 기사나 전설속의 아더왕처럼 엄청난 고난과 역경을 이겨내고 싸워서 이겨야 한다고 생각하는 경향이 있습니다.

하지만 우리가 알고리즘을 이용하는 목적은 우리의 프로그램을 단순하게 만들기 위해서입니다. 그리고 그 단순함을 바탕으로 효과적으로 프로그램을 동작시키기 위해서입니다.

따라서 문제의 본질을 이해하지 않고 만든 복잡한 알고리즘은 우리를 더욱 복잡하게 만들 뿐입니다. 그리고 복잡한 프로그램은 언제나 문제를 일으키며, 사용자들에게도 외면을 받기 일수입니다.

하지만 많은 개발자들은 문제가 발생하는 컨텍스트를 분석하여 단순화 시키기 보다는 "자! 드디어 새로운 알고리즘 용을 잡으러 갈때다~ 와~"하고 외치며, 무시무시하게 생긴 알고리즘 용을 잡으려 갑니다.

갖은 역경과 고난을 거쳐~ 때로는 정해진 시간을 넘기면서 잡아온 알고리즘 용은 제대로 동작할지 모르지만, 조그만 요구사항 변경이나 입력값의 변경에도 견디지 못하고, 그 난폭한 성격을 드러냅니다.

그리고 다시 개발자에게 불을 뿜으며, 자 덤벼봐~ 난 이 세상에서 가장 무시 무시한 알고리즘 용이야!! 용용 죽겠지~ㅎㅎ 라고 외치면서요~ :-D

단순함은 기능성, 견고성, 속도 향상, 메모리 절약 등의 결과를 가져올 수 있다.
Dennis Ritchie와 Ken Thompson은 18비트 워드 8,192개의 메모리가 탑재된 머신에서 UNIX 운영체제를 개발하였다.

그들은 논문에서 "시스템과 소프트웨어에 대하여 항상 심각한 크기 제한이 있었다. 그럼에도 합당한 효율성과 표현력을 얻기 바랬고, 결과적으로는 크기 제한에 대한 고민으로 인해 경제성만 만족시킨 것이 아니라 디자인도 우아해졌다."

이 책의 칼럼 10 중에서

이제 알고리즘을 다시 한번 생각해 볼 때입니다. 여러분의 알고리즘은 과연 단순하신가요?
복잡한 알고리즘 용을 잡으려고 오늘도 노력하시지 않으십니까?

문제의 본질을 파악하고 해결한 UNIX의 단순함을 다시한번 생각해 볼 때입니다.

감사합니다. ;-)

PS: 어느 분이 어떻게하면 프로그램을 잘 짤 수 있을까요? 알고리즘을 잘해야 하나요? 란 질문을 받고 답변으로 이 글을 올립니다.