Application_developing/C 2007/08/03 13:58
알고리즘·자료구조 학습에서의 문제
우리는 알고리즘 카탈로그를 배웁니다. 이미 그러한 해법이 존재하고, 그것이 최고이며, 따라서 그것을 달달 외우고 이해해야 합니다. 좀 똑똑한 친구들은 종종 "이야 이거 정말 기가 막힌 해법이군!"하고 감탄할지도 모릅니다. 대부분의 나머지 학생들은 그 해법을 이해하려고 머리를 쥐어짜고 한참을 씨름한 후에야 어렴풋이 왜 이 해법이 그 문제를 해결하는지 납득하게 됩니다.
그리고는 그 '증명'은 책 속에 덮어두고 까맣게 사라져버립니다. 앞으로는 그냥 '사용'하면 되는 것입니다. 더 많은 대다수의 학생은 이 과정이 무의미하다는 것을 알기 때문에 왜 이 해법이 이 문제를 문제없이 해결하는지의 증명은 간단히 건너뜁니다.
이런 학생들은 이미 주어진 알고리즘을 사용하는 일종의 객관식 혹은 문제 출제자가 존재하는 시험장 상황에서는 뛰어난 성적을 보일 것임은 자명합니다. 하지만 스스로가 문제와 해답을 모두 만들어내야 하는 상황이라면, 또는 해답이 존재하지 않을 가능성이 있는 상황이라면, 혹은 최적해를 구하는 것이 불가능에 가깝다면, 혹은 알고리즘을 완전히 새로 고안해내야 하거나 기존 알고리즘을 변형해야 하는 상황이라면 어떨까요?
교육은 물고기를 잡는 방법을 가르쳐야 합니다. 어떤 알고리즘을 배운다면 그 알고리즘을 고안해낸 사람이 어떤 사고 과정을 거쳐 그 해법에 도달했는지를 구경할 수 있어야 하고, 학생은 각자 스스로만의 해법을 차근차근 '구성'(construct)할 수 있어야 합니다(이를 교육철학에서 구성주의라고 합니다. 교육철학자 삐아제(Jean Piaget)의 제자이자, 마빈 민스키와 함께 MIT 미디어랩의 선구자인 세이머 페퍼트 박사가 주창했습니다). 전문가가 하는 것을 배우지 말고, 그들이 어떻게 전문가가 되었는지를 배우고 흉내 내야 합니다.
결국은 소크라테스적인 대화법입니다. 해답을 가르쳐 주지 않으면서도 초등학교 학생이 자신이 가진 지식만으로 스스로 퀵소트를 유도할 수 있도록 옆에서 도와줄 수 있습니까? 이것이 우리 스스로와 교사들에게 물어야 할 질문입니다.
왜 우리는 학교에서 '프로그래밍을 하는 과정'이나 '디자인 과정'(소프트웨어 공학에서 말하는 개발 프로세스가 아니라 몇 시간이나 몇 십 분 단위의, 개인적인 차원의 사고 과정 등을 일컫습니다)을 명시적으로 배운 적이 없을까요? 왜 해답에 이르는 과정을 가르쳐주는 사람이 없나요? 우리가 보는 것은 모조리 이미 훌륭히 완성된, 종적 상태의 결과물로서의 프로그램뿐입니다. 어느 날 문득 하늘에서 완성된 프로그램이 뚝 떨어지는 경우는 없는데 말입니다.
교수가 어떤 알고리즘 문제의 해답을 가르칠 때, "교수님, 교수님께서는 어떤 사고 과정을 거쳐, 그리고 어떤 디자인 과정과 프로그래밍 과정을 거쳐서 그 프로그램을 만드셨습니까?"하고 물어봅시다. 만약 여기에 어떤 체계적인 답변도 할 수 없는 분이라면 그 분은 자신의 사고에 대해 '사고'해 본 적이 없거나 문제 해결에 어떤 효율적 체계를 갖추지 못한 분이며, 따라서 아직 남을 가르칠 준비가 되어있지 않은 분일 것입니다. 만약 정말 그렇다면 우리는 어떻게 해야 할까요?
자료구조와 알고리즘 공부
제가 생각건대, 교육적인 목적에서는 자료구조나 알고리즘을 처음 공부할 때 우선은 특정 언어로 구현된 것을 보지 않는 것이 좋을 때가 많습니다. 대신 말로 된 설명이나 의사코드(pseudo-code) 등으로 그 개념까지만 이해하는 것이죠. 그 아이디어를 절차형(C, 어셈블리어)이나 함수형(LISP, Scheme, Haskell), 객체지향(자바, 스몰토크) 언어 등으로 직접 구현해 보는 겁니다. 그 다음에는 다른 사람이나 다른 책의 코드와 비교합니다. 이 경험을 애초에 박탈당한 사람은 귀중한 배움과 깨달음의 기회를 잃은 셈입니다.
만약 여러 사람이 함께 공부한다면 각자 동일한 아이디어를 같은 언어로 혹은 다른 언어로 어떻게 다르게 표현했는지를 서로 비교해 보면 배우는 것이 무척 많습니다.
우리가 자료구조나 알고리즘을 공부하는 이유는, 특정 '실세계의 문제'를 어떠한 '수학적 아이디어'로 매핑시켜 해결할 수 있는지, 그것이 효율적인지, 또 이를 컴퓨터에 어떻게 효율적으로 구현할 수 있는지 따지고, 그것을 실제로 구현하기 위해서입니다. 따라서 이 과정에 있어 실세계의 문제를 수학 문제로, 그리고 수학적 개념을 프로그래밍 언어로 효율적으로 표현해내는 것은 아주 중요한 능력이 됩니다.
알고리즘 공부에서 중요한 것
개별 알고리즘의 목록을 이해, 암기하며 익히는 것도 중요하지만 더 중요한 것은 다음 네 가지입니다.
①알고리즘을 스스로 생각해낼 수 있는 능력
②다른 알고리즘과 효율을 비교할 수 있는 능력
③알고리즘을 컴퓨터와 다른 사람이 이해할 수 있는 언어로 표현해낼 수 있는 능력
④이것의 정상작동(correctness) 여부를 검증해 내는 능력
첫 번째가 제대로 훈련되지 못한 사람은 알고리즘 목록의 스테레오 타입에만 길들여져 있어서 모든 문제를 자신이 아는 알고리즘 목록에 끼워 맞추려고 합니다. 디자인패턴을 잘못 공부한 사람과 비슷합니다. 이런 사람들은 마치 과거에 수학 정석만 수십 번 공부해 문제를 하나 던져주기만 하면, 생각해보지도 않고 자신이 풀었던 문제들의 패턴 중 가장 비슷한 것 하나를 기계적·무의식적으로 풀어제끼는 문제풀이기계와 비슷합니다. 그들에게 도중에 물어보십시오. "너 지금 무슨 문제 풀고 있는 거니?" 열심히 연습장에 뭔가 풀어나가고는 있지만 그들은 자신이 뭘 풀고 있는지도 제대로 인식하지 못 하는 경우가 많습니다.
머리가 푸는 게 아니고 손이 푸는 것이죠. 이렇게 되면 도구에 종속되는 '망치의 오류'에 빠지기 쉽습니다. 새로운 알고리즘을 고안해야 하는 상황에서도 기존 알고리즘에 계속 매달릴 뿐입니다. 알고리즘을 새로 고안해 내건 혹은 기존의 것을 조합하건 스스로 생각해 내는 훈련이 필요합니다.
두 번째가 제대로 훈련되지 못한 사람은 일일이 구현해 보고 실험해 봐야만 알고리즘 간의 효율을 비교할 수 있습니다. 특히 자신이 가진 카탈로그를 벗어난 알고리즘을 만나면 이 문제가 생깁니다. 이건 상당한 대가를 치르게 합니다.
세 번째가 제대로 훈련되지 못한 사람은, 문제를 보면 "아, 이건 이렇게 저렇게 해결하면 됩니다"하는 말은 곧잘 할 수 있지만 막상 컴퓨터 앞에 앉혀 놓으면 아무 것도 하지 못합니다. 심지어 자신이 생각해낸 그 구체적 알고리즘을 남에게 설명해 줄 수는 있지만, 그걸 '컴퓨터에게' 설명하는 데는 실패합니다. 뭔가 생각해낼 수 있다는 것과 그걸 컴퓨터가 이해할 수 있게 설명할 수 있다는 것은 다른 차원의 능력을 필요로 합니다.
네 번째가 제대로 훈련되지 못한 사람은, 알고리즘을 특정 언어로 구현해도, 그것이 옳다는 확신을 할 수 없습니다. 임시변통(ad hoc)의 아슬아슬한 코드가 되거나 이것저것 덧붙인 누더기 코드가 되기 쉽습니다. 이걸 피하려면 두 가지 훈련이 필요합니다.
하나는 수학적·논리학적 증명의 훈련이고, 다른 하나는 테스트 훈련입니다. 전자가 이론적이라면 후자는 실용적인 면이 강합니다. 양자는 상보적인 관계입니다. 특수한 경우들을 개별적으로 테스트해서는 검증해야 할 것이 너무 많고, 또 모든 경우에 대해 확신할 수 없습니다. 테스트가 버그의 부재를 보장할 수는 없습니다. 하지만 수학적 증명을 통하면 그것이 가능합니다. 또, 어떤 경우에는 수학적 증명을 굳이 할 필요 없이 단순히 테스트 케이스 몇 개만으로도 충분히 안정성이 보장되는 경우가 있습니다. 이럴 때는 그냥 테스트만으로 만족할 수 있습니다.
실질적이고 구체적인 문제를 함께 다루라
자료구조와 알고리즘 공부를 할 때에는 가능하면 실질적이고 구체적인 실세계의 문제를 함께 다루는 것이 큰 도움이 됩니다. 모든 학습에 있어 이는 똑같이 적용됩니다. 인류의 지성사를 봐도, 구상(concrete) 다음에 추상(abstract)이 옵니다. 인간 개체 하나의 성장을 봐도 그러합니다. 'be-동사 더하기 to-부정사'가 예정으로 해석될 수 있다는 룰만 외우는 것보다 다양한 예문을 실제 문맥 속에서 여러 번 보는 것이 훨씬 나을 것은 자명합니다. 알고리즘과 자료구조를 공부할 때 여러 친구들과 함께 연습문제(특히 우리가 경험하는 실세계의 대상들과 관련이 있는 것)를 풀어보기도 하고, ACM의 ICPC(International Collegiate Programming Contest: 세계 대학생 프로그래밍 경진 대회) 등의 프로그래밍 경진 대회 문제 중 해당 알고리즘·자료구조가 사용될 수 있는 문제를 같이 풀어보는 것도 아주 좋습니다. 이게 가능하려면 "이 알고리즘이 쓰이는 문제는 이거다"하고 가이드를 해줄 사람이 있으면 좋겠죠. 이것은 그 구체적 알고리즘·자료구조를 훈련하는 것이고, 이와 동시에 어떤 알고리즘을 써야할지 선택, 조합하는 것과 새로운 알고리즘을 만들어내는 훈련도 무척 중요합니다.
알고리즘 디자인 과정의 중요성
알고리즘을 좀더 수월하게, 또 잘 만들려면 알고리즘 디자인 과정에 대해 생각해 봐야 합니다. 그냥 밑도 끝도 없이 문제를 쳐다본다고 해서 알고리즘이 튀어나오진 않습니다. 체계적이고 효율적인 접근법을 사용해야 합니다. 대표적인 것으로 다익스트라(E. W. Dijkstra)와 워스(N. Wirth)의 '조금씩 개선하기'(Stepwise Refinement)가 있습니다. 워스의 「Program Development by Stepwise Refinement」(1971, CACM 14.4, http://www.acm.org/classics/dec95)를 꼭 읽어보길 바랍니다. 여기 소개된 조금씩 개선하기는 구조적 프로그래밍에서 핵심적 역할을 했습니다(구조적 프로그래밍을 'goto 문 제거' 정도로 생각하면 안 됩니다). 다익스트라의 「Stepwise Program Construction」(Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982, http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD227.PDF)도 추천합니다.
알고리즘 검증은 알고리즘 디자인과 함께 갑니다. 새로운 알고리즘을 고안할 때 검증해 가면서 디자인하기 때문입니다. 물론 가장 큰 역할은 고안이 끝났을 때의 검증입니다. 알고리즘 검증에는 루프 불변식(loop invariant) 같은 것이 아주 유용합니다. 아주 막강한 무기입니다. 익혀 두면 두고두고 가치를 발휘할 것입니다. 맨버(Udi Manber)의 알고리즘 서적(『Introduction to Algorithms: A Creative Approach』)이 알고리즘 검증과 디자인이 함께 진행해 가는 예로 자주 추천됩니다. 많은 계발을 얻을 것입니다. 고전으로는 다익스트라의 『A Discipline of Programming』과 그라이스(Gries)의 『The Science of Programming』이 있습니다. 특히 전자를 추천합니다. 프로그래밍에 대한 관을 뒤흔들어 놓을 것입니다.
알고리즘과 패러다임
알고리즘을 공부하면 큰 줄기들을 알아야 합니다. 개별 테크닉도 중요하지만 '패러다임'이라고 할만한 것들을 알아야 합니다. 이것에 대해서는 튜링상을 수상한 로버트 플로이드(Robert Floyd)의 튜링상 수상 강연(The Paradigms of Programming, 1978)을 추천합니다. 패러다임을 알아야 알고리즘을 상황에 맞게 마음대로 변통할 수 있습니다. 그리고 자신만의 분류법을 만들어야 합니다. 구체적인 문제들을 케이스 바이 케이스로 여럿 접하는 동안 그냥 지나쳐 버리면 개별자는 영원히 개별자로 남을 뿐입니다. 비슷한 문제들을 서로 묶어서 일반화해야 합니다.
이런 패러다임을 발견하려면 '다시 하기'가 아주 좋습니다. 다른 것들과 마찬가지로, 이 다시 하기는 알고리즘에서만이 아니고 모든 공부에 적용할 수 있습니다. 같은 것을 다시 해보는 것에서 우리는 얼마나 많은 것을 배울 수 있을까요. 대단히 많습니다. 왜 동일한 문제를 여러 번 풀고, 왜 같은 내용의 세미나에 또 다시 참석하고, 같은 프로그램을 거듭 작성할까요? 훨씬 더 많이 배울 수 있기 때문입니다. 화술 교육에서는 같은 주제에 대해 한 번 말해본 연사와 두 번 말해본 연사는 천지 차이가 있다고 말합니다. 같은 일에 대해 두 번의 기회가 주어지면 두 번째에는 첫 번째보다 잘 할 기회가 있습니다. 게다가 첫 번째 경험했던 것을 '터널을 벗어나서' 다소 객관적으로 볼 수 있게 됩니다. 왜 자신이 저번에 이걸 잘 못 했고, 저걸 잘 했는지 알게 되고, 어떻게 하면 그걸 더 잘할 수 있을는지 깨닫게 됩니다. 저는 똑같은 문제를 여러 번 풀더라도 매번 조금씩 다른 해답을 얻습니다. 그러면서 정말 엄청나게 많은 것을 배웁니다. '비슷한 문제'를 모두 풀 능력이 생깁니다.
제가 개인적으로 존경하는 전산학자 로버트 플로이드(Robert W. Floyd)는 1978년도 튜링상 강연에서 다음과 같은 말을 합니다.
제가 어려운 알고리즘을 디자인하는 경험을 생각해 볼 때, 제 능력을 넓히는 데 가장 도움이 되는 특정한 테크닉이 있습니다. 어려운 문제를 푼 후에, 저는 그것을 처음부터 완전히 새로 풉니다. 좀 전에 얻은 해법의 통찰(insight)만을 유지하면서 말이죠. 해법이 제가 희망하는 만큼 명료하고 직접적인 것이 될 때까지 반복합니다. 그런 다음, 비슷한 문제들을 공략할 어떤 일반적인 룰을 찾습니다. 아까 주어진 문제를 아예 처음부터 최고로 효율적인 방향에서 접근하도록 이끌어줬을 그런 룰을 찾는 거죠. 많은 경우에 그런 룰은 불변의 가치가 있습니다. … 포트란의 룰은 몇 시간 내에 배울 수 있습니다. 하지만 관련 패러다임은 훨씬 더 많은 시간이 걸립니다. 배우거나(learn) 배운 것을 잊거나(unlearn) 하는 데 모두.
수학자와 프로그래머를 포함한 모든 문제 해결자들의 고전이 된 죠지 폴리야(George Polya)의 『How to Solve it』에는 이런 말이 있습니다:
심지어는 꽤나 훌륭한 학생들도, 문제의 해법을 얻고 논증을 깨끗하게 적은 다음에는 책을 덮어버리고 뭔가 다른 것을 찾는다. 그렇게 하는 동안 그들은 그 노력의 중요하고도 교육적인 측면을 잃어버리게 된다. … 훌륭한 선생은 어떠한 문제이건 간에 완전히 바닥이 드러나는 경우는 없다는 관점을 스스로 이해하고 또 학생들에게 명심시켜야 한다.
저는 ACM의 ICPC 문제 중에 어떤 문제를 이제까지 열 번도 넘게 풀었습니다. 대부분 짝 프로그래밍이나 세미나를 통해 프로그래밍 시연을 했던 것인데, 제 세미나에 여러 번 참석한 분이 농담조로 웃으며 물었습니다. "신기해요. 창준 씨는 그 문제를 풀 때마다 다른 프로그램을 짜는 것 같아요. 설마 준비를 안 해 와서 그냥 내키는 대로 하는 건 아니죠?" 저는 카오스 시스템과 비슷하게 초기치 민감도가 프로그래밍에도 작용하는 것 같다고 대답했습니다. 저 스스로 다른 해법을 시도하고 싶은 마음이 있으면 출발이 조금 다르고, 또 거기서 나오는 진행 방향도 다르게 됩니다. 그런데 중요한 것은 이렇게 같은 문제를 매번 다르게 풀면서 배우는 것이 엄청나게 많다는 점입니다. 저는 매번, 전보다 개선할 것을 찾아내게 되고, 또 새로운 것을 배웁니다. 마치 마르지 않는 샘물처럼 계속 생각할 거리를 준다는 점이 참 놀랍습니다.
알고리즘 개론 교재로는 CLR(Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)을 추천합니다. 이와 함께 혹은 이 책을 읽기 전에 존 벤틀리(Jon Bentley)의 『Programming Pearls』도 강력 추천합니다. 세계적인 짱짱한 프로그래머와 전산학자들이 함께 꼽은 위대한 책 목록에서 몇 손가락 안에 드는 책입니다. 아직 이 책을 본 적이 없는 사람은 축하합니다. 아마 몇 주간은 감동 속에 하루하루를 보내게 될 겁니다.
리팩토링 학습에서의 문제
먼저, 본지 2001년 11월호에 제가 썼던 마틴 파울러의 책을 추천하는 글을 인용하겠습니다.
OOP를 하건 안 하건 프로그래밍이란 업을 하는 사람이라면 이 책은 자신의 공력을 서너 단계 레벨업시켜줄 수 있다. 자질구레한 술기를 익히는 것이 아니고 기감과 내공을 증강하는 것이다.
혹자는 DP 이전에 RF를 봐야 한다고도 한다. 이 말이 어느 정도 일리가 있는 것이, 효과적인 학습은 문제의식이 선행해야 하기 때문이다. DP는 거시적 차원에서 해결안을 모아놓은 것이다. RF를 보고 나쁜 냄새(Bad Smell)를 맡을 수 있는 후각을 발달시켜야 한다. RF의 목록을 모두 외우는 것은 큰 의미가 없다. 그것보다 냄새나는 코드를 느낄 수 있는 감수성을 키우는 것이 더 중요하다. 필자는 일주일에 한 가지씩 나쁜 냄새를 정해놓고 그 기간 동안에는 자신이 접하는 모든 코드에서 그 냄새만이라도 확실히 맡도록 집중하는 방법을 권한다. 일명 일취집중후각법. 패턴 개념을 만든 건축가 크리스토퍼 알렉산더나 GoF의 랄프 존슨은 좋은 디자인이란 나쁜 것이 없는 상태라고 한다. 무색 무미 무취의 무위(無爲)적 자연(自然) 코드가 되는 그 날을 위해 오늘도 우리는 리팩토링이라는 유위(有爲)를 익힌다.
주변에서 리팩토링을 잘못 공부하는 경우를 종종 접합니다. 어떤 의미에서 잘못 공부한다고 할까요? '실체화'가 문제입니다. 리팩토링은 도구이고 방편일 뿐인데, 그것에 매달리는 것은 달은 보지 않고 손을 보는 것과 같습니다. 저는 리팩토링 책이 또 하나의 (이미 그 병폐가 많이 드러난) GoF 책이 되는 현상이 매우 걱정됩니다.
리팩토링 공부
사람들이 일반적으로 생각하는 바와는 달리 리팩토링 학습에 있어 어떤 리팩토링이 있는지, 구체적으로 무엇인지 등의 리팩토링 목록에 대한 지식과 각각에 대한 메카닉스(Mechanics: 해당 리팩토링을 해나가는 구체적 단계)는 오히려 덜 중요할 수 있습니다. 더 기본적이고 유용한 것은 코드 냄새(Code Smell)와 짧은 테스트-코드 싸이클입니다. 이것만 제대로 되면 리팩토링 책의 모든 리팩토링을 스스로 구성해낼 수 있으며, 다른 종류의 리팩토링까지 직접 발견해낼 수 있습니다.
그 책에서는 테스트의 중요성이 충분히 강조되지 않았습니다. 하지만 테스트 코드 없는 리팩토링은 안전벨트 없는 자동차 경주와 같습니다. 그리고 테스트 코드가 리팩토링의 방향을 결정하기도 합니다. 양자는 음과 양처럼 서로 엮여 있습니다. 이런 의미에서 리팩토링은 TDD(Test Driven Development)와 함께 수련하는 것이 좋습니다. 훨씬 더 빨리, 훨씬 더 많은 것을 배울 수 있을 겁니다.
리팩토링을 공부할 때는 우선 코드 냄새의 종류를 알고, 왜 그것이 나쁜 냄새가 될 수 있는지 이해하고(그게 불가하다면 리팩토링 공부를 미뤄야 합니다) 거기에 동의할 수 있어야 합니다. 그런 다음, 대충 어떤 종류의 리팩토링이 가능한지 죽 훑어봅니다. 그 중 몇 개는 메카닉스를 따라가면서 실험해 봅니다. 이제는 책을 덮습니다. 그리고 실제 코드를 접하고, 만약 거기에서 냄새를 맡는다면 이 냄새를 없애기 위해 어떻게 해야 할지 스스로 고민합니다. 리팩토링 책의 목록은 일단 무시하십시오. 그 냄새를 없애는 것이 목표이지, 어떤 리팩토링을 여기에 '써먹는 것'이 목표가 되어선 안 됩니다. 이 때, 반드시 테스트 코드가 있어야 합니다. 그래야 '좋은' 리팩토링을 할 수 있습니다. 책을 떠나 있으면서도 책에서 떠나지 않는 방법입니다.
리팩토링을 하기 전에 초록색 불(테스트가 모두 통과)이 들어온 시점에서 코드를 일부 고치면 빨간 불(테스트가 하나라도 실패)로 바뀔 겁니다. 이게 다시 초록색 불이 될 때까지 최소한도의 시간이 걸리도록 하십시오. 현 초록색에서 다음 초록색까지 최소한의 시간을 소비하도록 하면서 코드와 테스팅을 오가게 되면 자기도 모르는 사이에 훌륭한 리팩토링이 자발공으로 터져 나옵니다. 여기서 목적지는 우선은 OAOO(Once And Only Once: 모든 것은 오로지 한 번만 말해야 한다)를 지키는 쪽으로 합니다. 그러면 OAOO와 짧은 테스트-코드 싸이클을 지키는 사이 어느새 탁월한 디자인이 튀어나옵니다. 참고로 저는 '모래시계 프로그래밍'이란 걸 가끔 합니다. 모래시계나 알람 프로그램으로 테스트-코드 사이클의 시간을 재는 것입니다. 그래서 가급적이면 한 사이클이 3분 이내(대부분의 모래시계는 단위가 3분입니다)에 끝나도록 노력합니다. 여기서 성공을 하건 실패를 하건 많은 걸 얻습니다.
리팩토링 수련법
제가 고안, 사용한 몇 가지 리팩토링 수련법을 알려드립니다.
①일취집중후각법: 앞에 소개한 본지 2001년 11월호에서 인용된 글 참조
②주석 최소화: 주석을 최소화하되 코드의 가독성이 떨어지지 않도록(혹은 오히려 올라가도록) 노력합니다. 이렇게 하면 자동으로 리팩토링이 이뤄지는 경우가 많습니다.
③OAOO 따르기: OAOO 법칙을 가능하면 최대한, 엄격하게 따르려고 합니다. 역시 자동으로 좋은 리팩토링이 이뤄집니다. 여기서 디자인패턴이 창발하기도 합니다. GoF 책을 한번도 보지 못한 사람이 디자인패턴을 자유자재로 부리는 경우를 보게 됩니다.
④디미터 법칙(Law of Demeter) 따르기: 디미터 법칙을 가능하면 지키려고 합니다. 어떤 리팩토링이 저절로 이뤄지거나 혹은 필요 없어지는가요?
⑤짝(Pair) 리팩토링: 함께 리팩토링합니다. 혼자 하는 것보다 더 빨리, 더 많은 걸 배우게 됩니다. 특히, 각자 작성했던 코드를 함께 리팩토링하고, 제3자의 코드를 함께 리팩토링해 봅니다. 사람이 많다면 다른 짝이 리팩토링한 것과 서로 비교하고 토론합니다.
⑥'무엇'과 '어떻게'를 분리: 어떻게에서 무엇을 분리해 내도록 합니다. 어떤 리팩토링이 창발합니까?
여기서 번, 짝 리팩토링은 아주 효과적인 방법입니다. 저는 이것을 협동적 학습(Collaborative Learning)이라고 부릅니다. 상대가 나보다 더 많이 아는 경우만이 아니고, 서로 아는 것이 비슷해도 많은 양의 학습이 발생합니다. 특히, 전문가와 함께 짝 프로그래밍을 하면 무서울 만큼 빠른 학습을 경험할 수 있습니다. 저와 짝 프로그래밍을 한 사람이 학습하는 속도에서 경이감을 느낀 적이 한두 번이 아닙니다. 문화는 사회적으로 학습되는 것입니다. 우리가 지식이라고 하는 것의 상당 부분은 문화처럼 암묵적인 지식(Tacit Knowledge)입니다. 전문가가 문제가 생겼을 때 어떻게 사고하고, 어떤 과정을 거쳐 접근하며, 어떻게 디버깅하고, 키보드를 어떤 식으로 누르는지, 사고 도구로 무엇을 사용하는지, 일 계획과 관리를 어떻게 하는지, 동료와 어떻게 대화하는지 등은 성문화되어 있지 않습니다. 그러나 이런 것들은 아주 중요합니다. 프로페셔널의 하루 일과의 대부분을 이루고 있기 때문입니다. 이런 것들은 전문가 바로 옆에서 조금씩 일을 도와주면서 배워야 합니다. 도제 살이(Apprenticeship)입니다. 진정한 전문가는 모든 동작이 우아합니다. 마치 춤을 추는 것 같습니다. 이 모습을 바로 곁에서 지켜보게 되면, 주니어는 한마디로 엄청난 충격을 받습니다. 그리고 스펀지처럼 빨아들이게 됩니다. 도대체 이 경험을 책이나 공장화한 학교가 어떻게 대신하겠습니까. 이와 관련해서는 레이브와 웽거(Jean Lave, Etienne Wenger)의 『Situated Learning : Legitimate Peripheral Participation』을 강력 추천합니다. 이 글을 보는 모든 교육 종사자들이 꼭 읽어봤으면 합니다. 이 협동적 학습은 두 사람만이 아니고 그룹 단위로도 가능합니다. 스터디에 이용하면 재미와 유익함 일석이조를 얻습니다.
이 외에, 특히(어쩌면 가장) 중요한 것은 일취집중후각법 등을 이용해 자신의 코드 후각의 민감도를 높이는 것입니다. 코드 후각의 메타포 말고도 유사한 메타포가 몇 가지 더 있습니다. 켄트 벡은 코드의 소리를 들으라고 하고, 저는 코드를 향해 대화하라고 합니다. 코드의 소리를 듣는 것은 코드가 원하는 것에 귀를 기울이는 것을 말합니다. 코드는 단순해지려는 욕망이 있습니다. 그걸 이뤄주는 것이 프로그래머입니다. 그리고 짝 프로그래밍을 할 때 두 사람의 대화를 코드에 남기도록 합니다. 주석이 아닙니다.
우리 프로그래머들은 항상 공부해야 합니다. 우리는 지식을 중요하게 여깁니다. 하지만 지식에 대한 지식, 즉 내가 그 지식을 얻은 과정이나 방법 같은 것은 소홀히 여기기 쉽습니다. 따라서 지식의 축적과 공유는 있어도 방법론의 축적과 공유는 매우 드문 편입니다. 저는 평소에 이런 생각에서 학교 후배들을 위해 제 자신의 공부 경험을 짬짬이 글로 옮겨놓았고, 이번 기회에 그 글들을 취합, 정리하게 되었습니다. 그 결실이 바로 이 글입니다
이 글은 공부하는 방법과 과정에 관한 글입니다. 이 글은 제가 공부한 성공/실패 경험을 기본 토대로 했고, 지난 몇 년간 주변에서 저보다 먼저 공부한 사람들의 경험을 관찰, 분석한 것에 제가 다시 직접 실험한 것과 그밖에 오랫동안 꾸준히 모아온 자료들을 더했습니다. '만약 다시 공부한다면' 저는 이렇게 공부할 것입니다.
부디 독자 제현께서 이 글을 씨앗으로 삼아 자신만의 나무를 키우고 거기서 열매를 얻고, 또 그 열매의 씨앗이 다시 누군가에게 전해질 수 있다면 더 이상 바랄 것이 없겠습니다.
이 글은 특정 주제들의 학습/교수법에 대한 문제점과 제가 경험한 좋은 공부법을 소개하는 식으로 구성됐습니다. 여기에 선택된 과목은 리팩토링, 알고리즘·자료구조, 디자인패턴, 익스트림 프로그래밍(Extreme Programming 혹은 XP) 네 가지입니다.
이 네 가지가 선택된 이유는 필자가 관심있게 공부했던 것이기 때문만은 아니고, 모든 프로그래머에게 어떻게든 널리 도움이 될만한 교양과목이라 생각하여 선택한 것입니다. 그런데 이 네 가지의 순서가 겉보기와는 달리 어떤 단계적 발전을 함의하는 것은 아닙니다. 수신(修身)이 끝나면 더 이상 수신은 하지 않고 제가(齊家)를 한다는 것이 어불성설인 것과 같습니다.
원래는 글 후미에 일반론으로서의 공부 패턴들을 쓰려고 했습니다. 하지만 지면의 제약도 있고, 독자 스스로 이 글에서 그런 패턴을 추출하는 것도 의미가 있을 것이기에 생략했습니다. 그런 일반론이 여기 저기 숨어있기 때문에 알고리즘 공부에 나온 방법 대부분이 리팩토링 공부에도 적용할 수 있고, 적용되어야 한다는 점을 꼭 기억해 주셨으면 합니다. 다음에 기회가 닿는다면 제가 평소 사용하는 (컴퓨터) 공부패턴들을 소개하겠습니다
복잡도(complexity)의 개념
알고리즘의 성능분석에 있어서의 복잡도(complexity)의 개념에 대해 살펴
보고 공간복잡도(space complexity)와 시간복잡도(time complexity)에 대해
알아본다.
4.1 알고리즘의 성능분석과 복잡도(complexity)
4.2 공간 복잡도(space complexity)
4.3 시간 복잡도(time complexity)
4.1 알고리즘의 성능분석과 복잡도(complexity)
앞 장에서도 언급했듯이 알고리즘은 유한한 횟수의 명령어들을 정해진
순서에 의하여 수행한 다음 언젠가는 반드시 종료되어야 한다.(유한성) 따
라서 알고리즘은 일단 시작된 다음 종료될 때까지의 실행시간이 이치에
맞지 않게 너무 길어서는 안된다. 장기 혹은 바둑과 같은 게임에 대한 알고
리즘을 예를 들어 생각해 볼 수 있다. 이와 같은 게임의 알고리즘을 개발할
때, 게임중 발생할 수 있는 모든 경우를 조사하여 알고리즘을 구성할 수 있
다. 그러나 이러한 방법으로는 알고리즘의 개발 조차도 불가능할 것이며,
그런 방법에 의한 알고리즘의 실행시 얼마만의 시간 안에 계산을 종료할
지도 추측할 수 없게 된다.
따라서, 일반적인 알고리즘은 상식적인 시간 안에 실행을 종료할 수 있어
야 하며, 가능한 한 빠른 시간내에 실행을 종료할 수 있어야 한다. 이러한
관점에서 알고리즘의 성능을 분석하기 위해 시간 복잡도(time complexity)
라는 개념을 사용하게 된다.
알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간 복잡도(time
complexity) 외에 공간 복잡도(space complexity)도 있다. 시간 복잡도가 알
고리즘의 실행시간을 의미한다면 공간 복잡도는 알고리즘을 수행시키기
위해 필요한 기억장치(memory)의 크기를 의미한다.
[정의4.1] 복잡도(complexity)
시간 복잡도(time complexity): 알고리즘을 실행하여 종료할때까지 필요한
시간
공간 복잡도(space complexity): 알고리즘을 실행하여 종료할때까지 필요
한 기억장치의 크기
4.2 공간 복잡도(space complexity)
주어진 알고리즘을 실행시키기 위해 필요한 기억장치(space)는 다음과
같이 두 가지로 분류해 볼 수 있다.
알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램
코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로
하는 공간 등이 이에 포함된다.
알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으
로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장
하기 위한 공간이나 순환 프로그램일 경우 순환 스택(recursion stack) 등이
이에 포함된다.
일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번
째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시
필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한
다.
다음은 공간 복잡도를 구하는 예이다.
[예제4.1] 공간 복잡도의 계산 1
float abc(float a, float b, float c)
{
return(a + b + b*c + (a + b - c)/(a + b) + 4.0);
}
공간 복잡도 = 0
위의 프로그램에서 공간복잡도를 구하기 위해서 살펴볼 것은 변수 a, b,
c 이다. 따라서, float형의 변수가 한 워드(word)를 차지한다고 가정하면,
공간복잡도는 '3워드'라고 생각할 수 있다. 그러나 변수 a, b, c 는 전달되
는 인자(parameter)로서 함수 abc내에서 해결하고자 하는 문제와는 무관하
다고 볼 수 있으므로 공간 복잡도는 0이다.
[예제4.2] 공간 복잡도 계산 2
float Sum(float a[], int n)
{
float s = 0.0;
for(int i = 1; i < = n; i++)
s += a[i];
return s;
}
공간 복잡도 = n + 3
위의 프로그램에서 사용되는 변수는 a[], n, s, i 이다. 이번 예에서도 a[]
와 n은 인자로 전달 됨을 볼 수 있다. 그러나 [예제4.1]과는 다르게 변수
a[]는 합을 구하기 위하여 반복문 내에서 n개의 원소가 모두 참조되고 있
음을 볼 수 있다. 또한, n은 for-문을 벗어나기 위한 한계값으로 사용된다.
따라서 a[]와 n은 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있
다고 볼 수 있다. 그러므로 프로그램의 복잡도는 (a[]를 저장하기 위한 공
간) + (변수 n, s, I를 위한 공간) = n + 3 이 된다.
[예제4.3] 공간 복잡도 계산 3
float RSum(float a[], int n)
{
if(n <= 0)
return (0.0);
else
return (RSum(a, n-1) + a[n]);
}
공간 복잡도 = 3(n + 1)
위의 프로그램은 순환기법(resursion)으로 작성된 것이다. 위의 경우 살펴
볼 변수는 a[], n이다. 우선 변수 n은 if-문 내에서 순환의 한계값으로 사용
되고 있음을 볼 수 있다. 또한, 변수 a[]는 합을 구하기 위하여 사용되고
있으며 a[]의 원소 중에서 n번째의 원소만 필요로 한다. 따라서 변수 a[]
와 n이 모두 알고리즘과 밀접한 관계가 있으므로, 프로그램이 필요로 하는
공간은 (a[]의 n번째 원소를 의한 공간) + (n을 위한 공간) = 1 + 1 으로 볼
수 있다. 그러나 위의 프로그램은 순환기법에 의해 작성되었음을 고려해
야 한다. 즉, 프로그램이 순환적으로 실행될 것을 고려해서 몇번의 순환후
에 실행이 종료되는지(the depth of recursion)를 계산해야 하며, 또한 순환
을 위해서 필요한 복귀 주소(return address)를 저장할 공간도 계산해야 한
다. 그러므로 프로그램의 공간 복잡도는 (depth of recursion)×(a[n], n, 복
귀 주소를 위한 공간) = (n+1)×3 이 된다.
4.3 시간 복잡도(time complexity)
시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는
지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을
곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹
은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의
일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행
횟수만을 고려하게 된다.
이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리
즘의 시간 복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이
라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간
복잡도를 통해서 이루어진다. 따라서 이번 강좌를 통해서 소개되는 알고
리즘들의 분석은 대부분 시간 복잡도를 이용할 것이며 특별한 언급이 없
는 한 '복잡도'는 '시간 복잡도'를 의미하게 된다.
다음은 시간 복잡도를 구하는 예이다.
[예제4.4] 시간 복잡도 계산 1 알고리즘
실행횟수
float Sum(float a[], int n)
{
float s = 0.0; 1
for(int i = 1; i <= n; I++) n+1
s += a[i]; n
return s; 1
}
명령어 총 실행횟수 = 2n + 3, 시간 복잡도 = O(n)
위 알고리즘의 총 실행 횟수는 2n+3 이 되므로 시간 복잡도는 2n+3이다.
또한 복잡도는 일반적으로 'big oh'표기법을 통해서 평균 실행시간을 표현
하게 되는데 위의 알고리즘의 경우는 'big oh' 표기법으로 O(n)이 된다. 복
잡도의 표기 방법에 대해서는 다음절에서 보다 자세히 살펴보도록 하겠다.
순환 알고리즘의 경우, 시간 복잡도를 구하기 위하여 명령어의 실행 횟수
를 세는 것은 위의 [예제4.4]와 같은 방법으로는 어렵다. 따라서 일반적으
로 순환 알고리즘의 시간 복잡도를 구하기 위해서는 순환식(recursive
formula)을 이용하게 된다. [예제4.3]에서 소개된 알고리즘을 예로 들면 다
음과 같다.
[예제4.5] 시간 복잡도 계산 2 알고리즘
실행횟수
float RSum(float a[], int n)
{
if(n <= 0) 1
return (0.0); 1
else
return (RSum(a, n-1) + a[n]); 1 + T(RSum(n-1))
}
명령어 총 실행횟수 = 2n + 1, 시간 복잡도 = O(n)
위의 알고리즘에서 사용된 순환식을 이용하면 명령어의 실행횟수는 다
음과 같음을 알 수 있다.
T(RSum(n)) = 2 ,if n = 0
= 2 + T(RSum(n-1) ,if n > 0
이와 같은 순환식은 또한 순환관계(recurrence relation)라고도 말하는데,
이러한 순환관계로부터 총 명령어 실행횟수를 구하는 방법은 다음과 같다.
T(RSum(n)) = 2 + T(RSum(n-1))
= 2 + ( 2 + T(RSum((n-2)) )
= 2 + ( 2 + ( 2 + T(RSum((n-3)) ) )
......
= 2×n + T(RSum(0))
= 2n + 2
따라서, 명령어 실행횟수의 총 합은 2n+2이고 시간 복잡도는 O(n)이다.
1. 알고리즘의 성능을 측정하기 위한 수단으로서 복잡도(complexity)를 사
용하며, 복잡도에는 알고리즘의 수행에 필요한 시간을 의미하는 시간 복
잡도(time complexity)와 필요한 기억장치(memory)의 크기를 의미하는 공
간 복잡도(space complexity)가 있다.
2. 공간 복잡도는 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있는
부분 즉, 변수를 저장하기 위한 공간, 순환 프로그램일 경우 순환
스택(recursion stack)등을 모두 합한 값으로 나타낸다.
3. 시간 복잡도는 알고리즘을 구성하는 명령어들의 실행횟수를 모두 합한
값으로 나타내며, 일반적인 알고리즘 분석은 시간 복잡도를 통하여 이루
어진다.
우리는 알고리즘 카탈로그를 배웁니다. 이미 그러한 해법이 존재하고, 그것이 최고이며, 따라서 그것을 달달 외우고 이해해야 합니다. 좀 똑똑한 친구들은 종종 "이야 이거 정말 기가 막힌 해법이군!"하고 감탄할지도 모릅니다. 대부분의 나머지 학생들은 그 해법을 이해하려고 머리를 쥐어짜고 한참을 씨름한 후에야 어렴풋이 왜 이 해법이 그 문제를 해결하는지 납득하게 됩니다.
그리고는 그 '증명'은 책 속에 덮어두고 까맣게 사라져버립니다. 앞으로는 그냥 '사용'하면 되는 것입니다. 더 많은 대다수의 학생은 이 과정이 무의미하다는 것을 알기 때문에 왜 이 해법이 이 문제를 문제없이 해결하는지의 증명은 간단히 건너뜁니다.
이런 학생들은 이미 주어진 알고리즘을 사용하는 일종의 객관식 혹은 문제 출제자가 존재하는 시험장 상황에서는 뛰어난 성적을 보일 것임은 자명합니다. 하지만 스스로가 문제와 해답을 모두 만들어내야 하는 상황이라면, 또는 해답이 존재하지 않을 가능성이 있는 상황이라면, 혹은 최적해를 구하는 것이 불가능에 가깝다면, 혹은 알고리즘을 완전히 새로 고안해내야 하거나 기존 알고리즘을 변형해야 하는 상황이라면 어떨까요?
교육은 물고기를 잡는 방법을 가르쳐야 합니다. 어떤 알고리즘을 배운다면 그 알고리즘을 고안해낸 사람이 어떤 사고 과정을 거쳐 그 해법에 도달했는지를 구경할 수 있어야 하고, 학생은 각자 스스로만의 해법을 차근차근 '구성'(construct)할 수 있어야 합니다(이를 교육철학에서 구성주의라고 합니다. 교육철학자 삐아제(Jean Piaget)의 제자이자, 마빈 민스키와 함께 MIT 미디어랩의 선구자인 세이머 페퍼트 박사가 주창했습니다). 전문가가 하는 것을 배우지 말고, 그들이 어떻게 전문가가 되었는지를 배우고 흉내 내야 합니다.
결국은 소크라테스적인 대화법입니다. 해답을 가르쳐 주지 않으면서도 초등학교 학생이 자신이 가진 지식만으로 스스로 퀵소트를 유도할 수 있도록 옆에서 도와줄 수 있습니까? 이것이 우리 스스로와 교사들에게 물어야 할 질문입니다.
왜 우리는 학교에서 '프로그래밍을 하는 과정'이나 '디자인 과정'(소프트웨어 공학에서 말하는 개발 프로세스가 아니라 몇 시간이나 몇 십 분 단위의, 개인적인 차원의 사고 과정 등을 일컫습니다)을 명시적으로 배운 적이 없을까요? 왜 해답에 이르는 과정을 가르쳐주는 사람이 없나요? 우리가 보는 것은 모조리 이미 훌륭히 완성된, 종적 상태의 결과물로서의 프로그램뿐입니다. 어느 날 문득 하늘에서 완성된 프로그램이 뚝 떨어지는 경우는 없는데 말입니다.
교수가 어떤 알고리즘 문제의 해답을 가르칠 때, "교수님, 교수님께서는 어떤 사고 과정을 거쳐, 그리고 어떤 디자인 과정과 프로그래밍 과정을 거쳐서 그 프로그램을 만드셨습니까?"하고 물어봅시다. 만약 여기에 어떤 체계적인 답변도 할 수 없는 분이라면 그 분은 자신의 사고에 대해 '사고'해 본 적이 없거나 문제 해결에 어떤 효율적 체계를 갖추지 못한 분이며, 따라서 아직 남을 가르칠 준비가 되어있지 않은 분일 것입니다. 만약 정말 그렇다면 우리는 어떻게 해야 할까요?
자료구조와 알고리즘 공부
제가 생각건대, 교육적인 목적에서는 자료구조나 알고리즘을 처음 공부할 때 우선은 특정 언어로 구현된 것을 보지 않는 것이 좋을 때가 많습니다. 대신 말로 된 설명이나 의사코드(pseudo-code) 등으로 그 개념까지만 이해하는 것이죠. 그 아이디어를 절차형(C, 어셈블리어)이나 함수형(LISP, Scheme, Haskell), 객체지향(자바, 스몰토크) 언어 등으로 직접 구현해 보는 겁니다. 그 다음에는 다른 사람이나 다른 책의 코드와 비교합니다. 이 경험을 애초에 박탈당한 사람은 귀중한 배움과 깨달음의 기회를 잃은 셈입니다.
만약 여러 사람이 함께 공부한다면 각자 동일한 아이디어를 같은 언어로 혹은 다른 언어로 어떻게 다르게 표현했는지를 서로 비교해 보면 배우는 것이 무척 많습니다.
우리가 자료구조나 알고리즘을 공부하는 이유는, 특정 '실세계의 문제'를 어떠한 '수학적 아이디어'로 매핑시켜 해결할 수 있는지, 그것이 효율적인지, 또 이를 컴퓨터에 어떻게 효율적으로 구현할 수 있는지 따지고, 그것을 실제로 구현하기 위해서입니다. 따라서 이 과정에 있어 실세계의 문제를 수학 문제로, 그리고 수학적 개념을 프로그래밍 언어로 효율적으로 표현해내는 것은 아주 중요한 능력이 됩니다.
알고리즘 공부에서 중요한 것
개별 알고리즘의 목록을 이해, 암기하며 익히는 것도 중요하지만 더 중요한 것은 다음 네 가지입니다.
①알고리즘을 스스로 생각해낼 수 있는 능력
②다른 알고리즘과 효율을 비교할 수 있는 능력
③알고리즘을 컴퓨터와 다른 사람이 이해할 수 있는 언어로 표현해낼 수 있는 능력
④이것의 정상작동(correctness) 여부를 검증해 내는 능력
첫 번째가 제대로 훈련되지 못한 사람은 알고리즘 목록의 스테레오 타입에만 길들여져 있어서 모든 문제를 자신이 아는 알고리즘 목록에 끼워 맞추려고 합니다. 디자인패턴을 잘못 공부한 사람과 비슷합니다. 이런 사람들은 마치 과거에 수학 정석만 수십 번 공부해 문제를 하나 던져주기만 하면, 생각해보지도 않고 자신이 풀었던 문제들의 패턴 중 가장 비슷한 것 하나를 기계적·무의식적으로 풀어제끼는 문제풀이기계와 비슷합니다. 그들에게 도중에 물어보십시오. "너 지금 무슨 문제 풀고 있는 거니?" 열심히 연습장에 뭔가 풀어나가고는 있지만 그들은 자신이 뭘 풀고 있는지도 제대로 인식하지 못 하는 경우가 많습니다.
머리가 푸는 게 아니고 손이 푸는 것이죠. 이렇게 되면 도구에 종속되는 '망치의 오류'에 빠지기 쉽습니다. 새로운 알고리즘을 고안해야 하는 상황에서도 기존 알고리즘에 계속 매달릴 뿐입니다. 알고리즘을 새로 고안해 내건 혹은 기존의 것을 조합하건 스스로 생각해 내는 훈련이 필요합니다.
두 번째가 제대로 훈련되지 못한 사람은 일일이 구현해 보고 실험해 봐야만 알고리즘 간의 효율을 비교할 수 있습니다. 특히 자신이 가진 카탈로그를 벗어난 알고리즘을 만나면 이 문제가 생깁니다. 이건 상당한 대가를 치르게 합니다.
세 번째가 제대로 훈련되지 못한 사람은, 문제를 보면 "아, 이건 이렇게 저렇게 해결하면 됩니다"하는 말은 곧잘 할 수 있지만 막상 컴퓨터 앞에 앉혀 놓으면 아무 것도 하지 못합니다. 심지어 자신이 생각해낸 그 구체적 알고리즘을 남에게 설명해 줄 수는 있지만, 그걸 '컴퓨터에게' 설명하는 데는 실패합니다. 뭔가 생각해낼 수 있다는 것과 그걸 컴퓨터가 이해할 수 있게 설명할 수 있다는 것은 다른 차원의 능력을 필요로 합니다.
네 번째가 제대로 훈련되지 못한 사람은, 알고리즘을 특정 언어로 구현해도, 그것이 옳다는 확신을 할 수 없습니다. 임시변통(ad hoc)의 아슬아슬한 코드가 되거나 이것저것 덧붙인 누더기 코드가 되기 쉽습니다. 이걸 피하려면 두 가지 훈련이 필요합니다.
하나는 수학적·논리학적 증명의 훈련이고, 다른 하나는 테스트 훈련입니다. 전자가 이론적이라면 후자는 실용적인 면이 강합니다. 양자는 상보적인 관계입니다. 특수한 경우들을 개별적으로 테스트해서는 검증해야 할 것이 너무 많고, 또 모든 경우에 대해 확신할 수 없습니다. 테스트가 버그의 부재를 보장할 수는 없습니다. 하지만 수학적 증명을 통하면 그것이 가능합니다. 또, 어떤 경우에는 수학적 증명을 굳이 할 필요 없이 단순히 테스트 케이스 몇 개만으로도 충분히 안정성이 보장되는 경우가 있습니다. 이럴 때는 그냥 테스트만으로 만족할 수 있습니다.
실질적이고 구체적인 문제를 함께 다루라
자료구조와 알고리즘 공부를 할 때에는 가능하면 실질적이고 구체적인 실세계의 문제를 함께 다루는 것이 큰 도움이 됩니다. 모든 학습에 있어 이는 똑같이 적용됩니다. 인류의 지성사를 봐도, 구상(concrete) 다음에 추상(abstract)이 옵니다. 인간 개체 하나의 성장을 봐도 그러합니다. 'be-동사 더하기 to-부정사'가 예정으로 해석될 수 있다는 룰만 외우는 것보다 다양한 예문을 실제 문맥 속에서 여러 번 보는 것이 훨씬 나을 것은 자명합니다. 알고리즘과 자료구조를 공부할 때 여러 친구들과 함께 연습문제(특히 우리가 경험하는 실세계의 대상들과 관련이 있는 것)를 풀어보기도 하고, ACM의 ICPC(International Collegiate Programming Contest: 세계 대학생 프로그래밍 경진 대회) 등의 프로그래밍 경진 대회 문제 중 해당 알고리즘·자료구조가 사용될 수 있는 문제를 같이 풀어보는 것도 아주 좋습니다. 이게 가능하려면 "이 알고리즘이 쓰이는 문제는 이거다"하고 가이드를 해줄 사람이 있으면 좋겠죠. 이것은 그 구체적 알고리즘·자료구조를 훈련하는 것이고, 이와 동시에 어떤 알고리즘을 써야할지 선택, 조합하는 것과 새로운 알고리즘을 만들어내는 훈련도 무척 중요합니다.
알고리즘 디자인 과정의 중요성
알고리즘을 좀더 수월하게, 또 잘 만들려면 알고리즘 디자인 과정에 대해 생각해 봐야 합니다. 그냥 밑도 끝도 없이 문제를 쳐다본다고 해서 알고리즘이 튀어나오진 않습니다. 체계적이고 효율적인 접근법을 사용해야 합니다. 대표적인 것으로 다익스트라(E. W. Dijkstra)와 워스(N. Wirth)의 '조금씩 개선하기'(Stepwise Refinement)가 있습니다. 워스의 「Program Development by Stepwise Refinement」(1971, CACM 14.4, http://www.acm.org/classics/dec95)를 꼭 읽어보길 바랍니다. 여기 소개된 조금씩 개선하기는 구조적 프로그래밍에서 핵심적 역할을 했습니다(구조적 프로그래밍을 'goto 문 제거' 정도로 생각하면 안 됩니다). 다익스트라의 「Stepwise Program Construction」(Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982, http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD227.PDF)도 추천합니다.
알고리즘 검증은 알고리즘 디자인과 함께 갑니다. 새로운 알고리즘을 고안할 때 검증해 가면서 디자인하기 때문입니다. 물론 가장 큰 역할은 고안이 끝났을 때의 검증입니다. 알고리즘 검증에는 루프 불변식(loop invariant) 같은 것이 아주 유용합니다. 아주 막강한 무기입니다. 익혀 두면 두고두고 가치를 발휘할 것입니다. 맨버(Udi Manber)의 알고리즘 서적(『Introduction to Algorithms: A Creative Approach』)이 알고리즘 검증과 디자인이 함께 진행해 가는 예로 자주 추천됩니다. 많은 계발을 얻을 것입니다. 고전으로는 다익스트라의 『A Discipline of Programming』과 그라이스(Gries)의 『The Science of Programming』이 있습니다. 특히 전자를 추천합니다. 프로그래밍에 대한 관을 뒤흔들어 놓을 것입니다.
알고리즘과 패러다임
알고리즘을 공부하면 큰 줄기들을 알아야 합니다. 개별 테크닉도 중요하지만 '패러다임'이라고 할만한 것들을 알아야 합니다. 이것에 대해서는 튜링상을 수상한 로버트 플로이드(Robert Floyd)의 튜링상 수상 강연(The Paradigms of Programming, 1978)을 추천합니다. 패러다임을 알아야 알고리즘을 상황에 맞게 마음대로 변통할 수 있습니다. 그리고 자신만의 분류법을 만들어야 합니다. 구체적인 문제들을 케이스 바이 케이스로 여럿 접하는 동안 그냥 지나쳐 버리면 개별자는 영원히 개별자로 남을 뿐입니다. 비슷한 문제들을 서로 묶어서 일반화해야 합니다.
이런 패러다임을 발견하려면 '다시 하기'가 아주 좋습니다. 다른 것들과 마찬가지로, 이 다시 하기는 알고리즘에서만이 아니고 모든 공부에 적용할 수 있습니다. 같은 것을 다시 해보는 것에서 우리는 얼마나 많은 것을 배울 수 있을까요. 대단히 많습니다. 왜 동일한 문제를 여러 번 풀고, 왜 같은 내용의 세미나에 또 다시 참석하고, 같은 프로그램을 거듭 작성할까요? 훨씬 더 많이 배울 수 있기 때문입니다. 화술 교육에서는 같은 주제에 대해 한 번 말해본 연사와 두 번 말해본 연사는 천지 차이가 있다고 말합니다. 같은 일에 대해 두 번의 기회가 주어지면 두 번째에는 첫 번째보다 잘 할 기회가 있습니다. 게다가 첫 번째 경험했던 것을 '터널을 벗어나서' 다소 객관적으로 볼 수 있게 됩니다. 왜 자신이 저번에 이걸 잘 못 했고, 저걸 잘 했는지 알게 되고, 어떻게 하면 그걸 더 잘할 수 있을는지 깨닫게 됩니다. 저는 똑같은 문제를 여러 번 풀더라도 매번 조금씩 다른 해답을 얻습니다. 그러면서 정말 엄청나게 많은 것을 배웁니다. '비슷한 문제'를 모두 풀 능력이 생깁니다.
제가 개인적으로 존경하는 전산학자 로버트 플로이드(Robert W. Floyd)는 1978년도 튜링상 강연에서 다음과 같은 말을 합니다.
제가 어려운 알고리즘을 디자인하는 경험을 생각해 볼 때, 제 능력을 넓히는 데 가장 도움이 되는 특정한 테크닉이 있습니다. 어려운 문제를 푼 후에, 저는 그것을 처음부터 완전히 새로 풉니다. 좀 전에 얻은 해법의 통찰(insight)만을 유지하면서 말이죠. 해법이 제가 희망하는 만큼 명료하고 직접적인 것이 될 때까지 반복합니다. 그런 다음, 비슷한 문제들을 공략할 어떤 일반적인 룰을 찾습니다. 아까 주어진 문제를 아예 처음부터 최고로 효율적인 방향에서 접근하도록 이끌어줬을 그런 룰을 찾는 거죠. 많은 경우에 그런 룰은 불변의 가치가 있습니다. … 포트란의 룰은 몇 시간 내에 배울 수 있습니다. 하지만 관련 패러다임은 훨씬 더 많은 시간이 걸립니다. 배우거나(learn) 배운 것을 잊거나(unlearn) 하는 데 모두.
수학자와 프로그래머를 포함한 모든 문제 해결자들의 고전이 된 죠지 폴리야(George Polya)의 『How to Solve it』에는 이런 말이 있습니다:
심지어는 꽤나 훌륭한 학생들도, 문제의 해법을 얻고 논증을 깨끗하게 적은 다음에는 책을 덮어버리고 뭔가 다른 것을 찾는다. 그렇게 하는 동안 그들은 그 노력의 중요하고도 교육적인 측면을 잃어버리게 된다. … 훌륭한 선생은 어떠한 문제이건 간에 완전히 바닥이 드러나는 경우는 없다는 관점을 스스로 이해하고 또 학생들에게 명심시켜야 한다.
저는 ACM의 ICPC 문제 중에 어떤 문제를 이제까지 열 번도 넘게 풀었습니다. 대부분 짝 프로그래밍이나 세미나를 통해 프로그래밍 시연을 했던 것인데, 제 세미나에 여러 번 참석한 분이 농담조로 웃으며 물었습니다. "신기해요. 창준 씨는 그 문제를 풀 때마다 다른 프로그램을 짜는 것 같아요. 설마 준비를 안 해 와서 그냥 내키는 대로 하는 건 아니죠?" 저는 카오스 시스템과 비슷하게 초기치 민감도가 프로그래밍에도 작용하는 것 같다고 대답했습니다. 저 스스로 다른 해법을 시도하고 싶은 마음이 있으면 출발이 조금 다르고, 또 거기서 나오는 진행 방향도 다르게 됩니다. 그런데 중요한 것은 이렇게 같은 문제를 매번 다르게 풀면서 배우는 것이 엄청나게 많다는 점입니다. 저는 매번, 전보다 개선할 것을 찾아내게 되고, 또 새로운 것을 배웁니다. 마치 마르지 않는 샘물처럼 계속 생각할 거리를 준다는 점이 참 놀랍습니다.
알고리즘 개론 교재로는 CLR(Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)을 추천합니다. 이와 함께 혹은 이 책을 읽기 전에 존 벤틀리(Jon Bentley)의 『Programming Pearls』도 강력 추천합니다. 세계적인 짱짱한 프로그래머와 전산학자들이 함께 꼽은 위대한 책 목록에서 몇 손가락 안에 드는 책입니다. 아직 이 책을 본 적이 없는 사람은 축하합니다. 아마 몇 주간은 감동 속에 하루하루를 보내게 될 겁니다.
리팩토링 학습에서의 문제
먼저, 본지 2001년 11월호에 제가 썼던 마틴 파울러의 책을 추천하는 글을 인용하겠습니다.
OOP를 하건 안 하건 프로그래밍이란 업을 하는 사람이라면 이 책은 자신의 공력을 서너 단계 레벨업시켜줄 수 있다. 자질구레한 술기를 익히는 것이 아니고 기감과 내공을 증강하는 것이다.
혹자는 DP 이전에 RF를 봐야 한다고도 한다. 이 말이 어느 정도 일리가 있는 것이, 효과적인 학습은 문제의식이 선행해야 하기 때문이다. DP는 거시적 차원에서 해결안을 모아놓은 것이다. RF를 보고 나쁜 냄새(Bad Smell)를 맡을 수 있는 후각을 발달시켜야 한다. RF의 목록을 모두 외우는 것은 큰 의미가 없다. 그것보다 냄새나는 코드를 느낄 수 있는 감수성을 키우는 것이 더 중요하다. 필자는 일주일에 한 가지씩 나쁜 냄새를 정해놓고 그 기간 동안에는 자신이 접하는 모든 코드에서 그 냄새만이라도 확실히 맡도록 집중하는 방법을 권한다. 일명 일취집중후각법. 패턴 개념을 만든 건축가 크리스토퍼 알렉산더나 GoF의 랄프 존슨은 좋은 디자인이란 나쁜 것이 없는 상태라고 한다. 무색 무미 무취의 무위(無爲)적 자연(自然) 코드가 되는 그 날을 위해 오늘도 우리는 리팩토링이라는 유위(有爲)를 익힌다.
주변에서 리팩토링을 잘못 공부하는 경우를 종종 접합니다. 어떤 의미에서 잘못 공부한다고 할까요? '실체화'가 문제입니다. 리팩토링은 도구이고 방편일 뿐인데, 그것에 매달리는 것은 달은 보지 않고 손을 보는 것과 같습니다. 저는 리팩토링 책이 또 하나의 (이미 그 병폐가 많이 드러난) GoF 책이 되는 현상이 매우 걱정됩니다.
리팩토링 공부
사람들이 일반적으로 생각하는 바와는 달리 리팩토링 학습에 있어 어떤 리팩토링이 있는지, 구체적으로 무엇인지 등의 리팩토링 목록에 대한 지식과 각각에 대한 메카닉스(Mechanics: 해당 리팩토링을 해나가는 구체적 단계)는 오히려 덜 중요할 수 있습니다. 더 기본적이고 유용한 것은 코드 냄새(Code Smell)와 짧은 테스트-코드 싸이클입니다. 이것만 제대로 되면 리팩토링 책의 모든 리팩토링을 스스로 구성해낼 수 있으며, 다른 종류의 리팩토링까지 직접 발견해낼 수 있습니다.
그 책에서는 테스트의 중요성이 충분히 강조되지 않았습니다. 하지만 테스트 코드 없는 리팩토링은 안전벨트 없는 자동차 경주와 같습니다. 그리고 테스트 코드가 리팩토링의 방향을 결정하기도 합니다. 양자는 음과 양처럼 서로 엮여 있습니다. 이런 의미에서 리팩토링은 TDD(Test Driven Development)와 함께 수련하는 것이 좋습니다. 훨씬 더 빨리, 훨씬 더 많은 것을 배울 수 있을 겁니다.
리팩토링을 공부할 때는 우선 코드 냄새의 종류를 알고, 왜 그것이 나쁜 냄새가 될 수 있는지 이해하고(그게 불가하다면 리팩토링 공부를 미뤄야 합니다) 거기에 동의할 수 있어야 합니다. 그런 다음, 대충 어떤 종류의 리팩토링이 가능한지 죽 훑어봅니다. 그 중 몇 개는 메카닉스를 따라가면서 실험해 봅니다. 이제는 책을 덮습니다. 그리고 실제 코드를 접하고, 만약 거기에서 냄새를 맡는다면 이 냄새를 없애기 위해 어떻게 해야 할지 스스로 고민합니다. 리팩토링 책의 목록은 일단 무시하십시오. 그 냄새를 없애는 것이 목표이지, 어떤 리팩토링을 여기에 '써먹는 것'이 목표가 되어선 안 됩니다. 이 때, 반드시 테스트 코드가 있어야 합니다. 그래야 '좋은' 리팩토링을 할 수 있습니다. 책을 떠나 있으면서도 책에서 떠나지 않는 방법입니다.
리팩토링을 하기 전에 초록색 불(테스트가 모두 통과)이 들어온 시점에서 코드를 일부 고치면 빨간 불(테스트가 하나라도 실패)로 바뀔 겁니다. 이게 다시 초록색 불이 될 때까지 최소한도의 시간이 걸리도록 하십시오. 현 초록색에서 다음 초록색까지 최소한의 시간을 소비하도록 하면서 코드와 테스팅을 오가게 되면 자기도 모르는 사이에 훌륭한 리팩토링이 자발공으로 터져 나옵니다. 여기서 목적지는 우선은 OAOO(Once And Only Once: 모든 것은 오로지 한 번만 말해야 한다)를 지키는 쪽으로 합니다. 그러면 OAOO와 짧은 테스트-코드 싸이클을 지키는 사이 어느새 탁월한 디자인이 튀어나옵니다. 참고로 저는 '모래시계 프로그래밍'이란 걸 가끔 합니다. 모래시계나 알람 프로그램으로 테스트-코드 사이클의 시간을 재는 것입니다. 그래서 가급적이면 한 사이클이 3분 이내(대부분의 모래시계는 단위가 3분입니다)에 끝나도록 노력합니다. 여기서 성공을 하건 실패를 하건 많은 걸 얻습니다.
리팩토링 수련법
제가 고안, 사용한 몇 가지 리팩토링 수련법을 알려드립니다.
①일취집중후각법: 앞에 소개한 본지 2001년 11월호에서 인용된 글 참조
②주석 최소화: 주석을 최소화하되 코드의 가독성이 떨어지지 않도록(혹은 오히려 올라가도록) 노력합니다. 이렇게 하면 자동으로 리팩토링이 이뤄지는 경우가 많습니다.
③OAOO 따르기: OAOO 법칙을 가능하면 최대한, 엄격하게 따르려고 합니다. 역시 자동으로 좋은 리팩토링이 이뤄집니다. 여기서 디자인패턴이 창발하기도 합니다. GoF 책을 한번도 보지 못한 사람이 디자인패턴을 자유자재로 부리는 경우를 보게 됩니다.
④디미터 법칙(Law of Demeter) 따르기: 디미터 법칙을 가능하면 지키려고 합니다. 어떤 리팩토링이 저절로 이뤄지거나 혹은 필요 없어지는가요?
⑤짝(Pair) 리팩토링: 함께 리팩토링합니다. 혼자 하는 것보다 더 빨리, 더 많은 걸 배우게 됩니다. 특히, 각자 작성했던 코드를 함께 리팩토링하고, 제3자의 코드를 함께 리팩토링해 봅니다. 사람이 많다면 다른 짝이 리팩토링한 것과 서로 비교하고 토론합니다.
⑥'무엇'과 '어떻게'를 분리: 어떻게에서 무엇을 분리해 내도록 합니다. 어떤 리팩토링이 창발합니까?
여기서 번, 짝 리팩토링은 아주 효과적인 방법입니다. 저는 이것을 협동적 학습(Collaborative Learning)이라고 부릅니다. 상대가 나보다 더 많이 아는 경우만이 아니고, 서로 아는 것이 비슷해도 많은 양의 학습이 발생합니다. 특히, 전문가와 함께 짝 프로그래밍을 하면 무서울 만큼 빠른 학습을 경험할 수 있습니다. 저와 짝 프로그래밍을 한 사람이 학습하는 속도에서 경이감을 느낀 적이 한두 번이 아닙니다. 문화는 사회적으로 학습되는 것입니다. 우리가 지식이라고 하는 것의 상당 부분은 문화처럼 암묵적인 지식(Tacit Knowledge)입니다. 전문가가 문제가 생겼을 때 어떻게 사고하고, 어떤 과정을 거쳐 접근하며, 어떻게 디버깅하고, 키보드를 어떤 식으로 누르는지, 사고 도구로 무엇을 사용하는지, 일 계획과 관리를 어떻게 하는지, 동료와 어떻게 대화하는지 등은 성문화되어 있지 않습니다. 그러나 이런 것들은 아주 중요합니다. 프로페셔널의 하루 일과의 대부분을 이루고 있기 때문입니다. 이런 것들은 전문가 바로 옆에서 조금씩 일을 도와주면서 배워야 합니다. 도제 살이(Apprenticeship)입니다. 진정한 전문가는 모든 동작이 우아합니다. 마치 춤을 추는 것 같습니다. 이 모습을 바로 곁에서 지켜보게 되면, 주니어는 한마디로 엄청난 충격을 받습니다. 그리고 스펀지처럼 빨아들이게 됩니다. 도대체 이 경험을 책이나 공장화한 학교가 어떻게 대신하겠습니까. 이와 관련해서는 레이브와 웽거(Jean Lave, Etienne Wenger)의 『Situated Learning : Legitimate Peripheral Participation』을 강력 추천합니다. 이 글을 보는 모든 교육 종사자들이 꼭 읽어봤으면 합니다. 이 협동적 학습은 두 사람만이 아니고 그룹 단위로도 가능합니다. 스터디에 이용하면 재미와 유익함 일석이조를 얻습니다.
이 외에, 특히(어쩌면 가장) 중요한 것은 일취집중후각법 등을 이용해 자신의 코드 후각의 민감도를 높이는 것입니다. 코드 후각의 메타포 말고도 유사한 메타포가 몇 가지 더 있습니다. 켄트 벡은 코드의 소리를 들으라고 하고, 저는 코드를 향해 대화하라고 합니다. 코드의 소리를 듣는 것은 코드가 원하는 것에 귀를 기울이는 것을 말합니다. 코드는 단순해지려는 욕망이 있습니다. 그걸 이뤄주는 것이 프로그래머입니다. 그리고 짝 프로그래밍을 할 때 두 사람의 대화를 코드에 남기도록 합니다. 주석이 아닙니다.
우리 프로그래머들은 항상 공부해야 합니다. 우리는 지식을 중요하게 여깁니다. 하지만 지식에 대한 지식, 즉 내가 그 지식을 얻은 과정이나 방법 같은 것은 소홀히 여기기 쉽습니다. 따라서 지식의 축적과 공유는 있어도 방법론의 축적과 공유는 매우 드문 편입니다. 저는 평소에 이런 생각에서 학교 후배들을 위해 제 자신의 공부 경험을 짬짬이 글로 옮겨놓았고, 이번 기회에 그 글들을 취합, 정리하게 되었습니다. 그 결실이 바로 이 글입니다
이 글은 공부하는 방법과 과정에 관한 글입니다. 이 글은 제가 공부한 성공/실패 경험을 기본 토대로 했고, 지난 몇 년간 주변에서 저보다 먼저 공부한 사람들의 경험을 관찰, 분석한 것에 제가 다시 직접 실험한 것과 그밖에 오랫동안 꾸준히 모아온 자료들을 더했습니다. '만약 다시 공부한다면' 저는 이렇게 공부할 것입니다.
부디 독자 제현께서 이 글을 씨앗으로 삼아 자신만의 나무를 키우고 거기서 열매를 얻고, 또 그 열매의 씨앗이 다시 누군가에게 전해질 수 있다면 더 이상 바랄 것이 없겠습니다.
이 글은 특정 주제들의 학습/교수법에 대한 문제점과 제가 경험한 좋은 공부법을 소개하는 식으로 구성됐습니다. 여기에 선택된 과목은 리팩토링, 알고리즘·자료구조, 디자인패턴, 익스트림 프로그래밍(Extreme Programming 혹은 XP) 네 가지입니다.
이 네 가지가 선택된 이유는 필자가 관심있게 공부했던 것이기 때문만은 아니고, 모든 프로그래머에게 어떻게든 널리 도움이 될만한 교양과목이라 생각하여 선택한 것입니다. 그런데 이 네 가지의 순서가 겉보기와는 달리 어떤 단계적 발전을 함의하는 것은 아닙니다. 수신(修身)이 끝나면 더 이상 수신은 하지 않고 제가(齊家)를 한다는 것이 어불성설인 것과 같습니다.
원래는 글 후미에 일반론으로서의 공부 패턴들을 쓰려고 했습니다. 하지만 지면의 제약도 있고, 독자 스스로 이 글에서 그런 패턴을 추출하는 것도 의미가 있을 것이기에 생략했습니다. 그런 일반론이 여기 저기 숨어있기 때문에 알고리즘 공부에 나온 방법 대부분이 리팩토링 공부에도 적용할 수 있고, 적용되어야 한다는 점을 꼭 기억해 주셨으면 합니다. 다음에 기회가 닿는다면 제가 평소 사용하는 (컴퓨터) 공부패턴들을 소개하겠습니다
복잡도(complexity)의 개념
알고리즘의 성능분석에 있어서의 복잡도(complexity)의 개념에 대해 살펴
보고 공간복잡도(space complexity)와 시간복잡도(time complexity)에 대해
알아본다.
4.1 알고리즘의 성능분석과 복잡도(complexity)
4.2 공간 복잡도(space complexity)
4.3 시간 복잡도(time complexity)
4.1 알고리즘의 성능분석과 복잡도(complexity)
앞 장에서도 언급했듯이 알고리즘은 유한한 횟수의 명령어들을 정해진
순서에 의하여 수행한 다음 언젠가는 반드시 종료되어야 한다.(유한성) 따
라서 알고리즘은 일단 시작된 다음 종료될 때까지의 실행시간이 이치에
맞지 않게 너무 길어서는 안된다. 장기 혹은 바둑과 같은 게임에 대한 알고
리즘을 예를 들어 생각해 볼 수 있다. 이와 같은 게임의 알고리즘을 개발할
때, 게임중 발생할 수 있는 모든 경우를 조사하여 알고리즘을 구성할 수 있
다. 그러나 이러한 방법으로는 알고리즘의 개발 조차도 불가능할 것이며,
그런 방법에 의한 알고리즘의 실행시 얼마만의 시간 안에 계산을 종료할
지도 추측할 수 없게 된다.
따라서, 일반적인 알고리즘은 상식적인 시간 안에 실행을 종료할 수 있어
야 하며, 가능한 한 빠른 시간내에 실행을 종료할 수 있어야 한다. 이러한
관점에서 알고리즘의 성능을 분석하기 위해 시간 복잡도(time complexity)
라는 개념을 사용하게 된다.
알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간 복잡도(time
complexity) 외에 공간 복잡도(space complexity)도 있다. 시간 복잡도가 알
고리즘의 실행시간을 의미한다면 공간 복잡도는 알고리즘을 수행시키기
위해 필요한 기억장치(memory)의 크기를 의미한다.
[정의4.1] 복잡도(complexity)
시간 복잡도(time complexity): 알고리즘을 실행하여 종료할때까지 필요한
시간
공간 복잡도(space complexity): 알고리즘을 실행하여 종료할때까지 필요
한 기억장치의 크기
4.2 공간 복잡도(space complexity)
주어진 알고리즘을 실행시키기 위해 필요한 기억장치(space)는 다음과
같이 두 가지로 분류해 볼 수 있다.
알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램
코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로
하는 공간 등이 이에 포함된다.
알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으
로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장
하기 위한 공간이나 순환 프로그램일 경우 순환 스택(recursion stack) 등이
이에 포함된다.
일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번
째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시
필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한
다.
다음은 공간 복잡도를 구하는 예이다.
[예제4.1] 공간 복잡도의 계산 1
float abc(float a, float b, float c)
{
return(a + b + b*c + (a + b - c)/(a + b) + 4.0);
}
공간 복잡도 = 0
위의 프로그램에서 공간복잡도를 구하기 위해서 살펴볼 것은 변수 a, b,
c 이다. 따라서, float형의 변수가 한 워드(word)를 차지한다고 가정하면,
공간복잡도는 '3워드'라고 생각할 수 있다. 그러나 변수 a, b, c 는 전달되
는 인자(parameter)로서 함수 abc내에서 해결하고자 하는 문제와는 무관하
다고 볼 수 있으므로 공간 복잡도는 0이다.
[예제4.2] 공간 복잡도 계산 2
float Sum(float a[], int n)
{
float s = 0.0;
for(int i = 1; i < = n; i++)
s += a[i];
return s;
}
공간 복잡도 = n + 3
위의 프로그램에서 사용되는 변수는 a[], n, s, i 이다. 이번 예에서도 a[]
와 n은 인자로 전달 됨을 볼 수 있다. 그러나 [예제4.1]과는 다르게 변수
a[]는 합을 구하기 위하여 반복문 내에서 n개의 원소가 모두 참조되고 있
음을 볼 수 있다. 또한, n은 for-문을 벗어나기 위한 한계값으로 사용된다.
따라서 a[]와 n은 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있
다고 볼 수 있다. 그러므로 프로그램의 복잡도는 (a[]를 저장하기 위한 공
간) + (변수 n, s, I를 위한 공간) = n + 3 이 된다.
[예제4.3] 공간 복잡도 계산 3
float RSum(float a[], int n)
{
if(n <= 0)
return (0.0);
else
return (RSum(a, n-1) + a[n]);
}
공간 복잡도 = 3(n + 1)
위의 프로그램은 순환기법(resursion)으로 작성된 것이다. 위의 경우 살펴
볼 변수는 a[], n이다. 우선 변수 n은 if-문 내에서 순환의 한계값으로 사용
되고 있음을 볼 수 있다. 또한, 변수 a[]는 합을 구하기 위하여 사용되고
있으며 a[]의 원소 중에서 n번째의 원소만 필요로 한다. 따라서 변수 a[]
와 n이 모두 알고리즘과 밀접한 관계가 있으므로, 프로그램이 필요로 하는
공간은 (a[]의 n번째 원소를 의한 공간) + (n을 위한 공간) = 1 + 1 으로 볼
수 있다. 그러나 위의 프로그램은 순환기법에 의해 작성되었음을 고려해
야 한다. 즉, 프로그램이 순환적으로 실행될 것을 고려해서 몇번의 순환후
에 실행이 종료되는지(the depth of recursion)를 계산해야 하며, 또한 순환
을 위해서 필요한 복귀 주소(return address)를 저장할 공간도 계산해야 한
다. 그러므로 프로그램의 공간 복잡도는 (depth of recursion)×(a[n], n, 복
귀 주소를 위한 공간) = (n+1)×3 이 된다.
4.3 시간 복잡도(time complexity)
시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는
지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을
곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹
은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의
일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행
횟수만을 고려하게 된다.
이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리
즘의 시간 복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이
라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간
복잡도를 통해서 이루어진다. 따라서 이번 강좌를 통해서 소개되는 알고
리즘들의 분석은 대부분 시간 복잡도를 이용할 것이며 특별한 언급이 없
는 한 '복잡도'는 '시간 복잡도'를 의미하게 된다.
다음은 시간 복잡도를 구하는 예이다.
[예제4.4] 시간 복잡도 계산 1 알고리즘
실행횟수
float Sum(float a[], int n)
{
float s = 0.0; 1
for(int i = 1; i <= n; I++) n+1
s += a[i]; n
return s; 1
}
명령어 총 실행횟수 = 2n + 3, 시간 복잡도 = O(n)
위 알고리즘의 총 실행 횟수는 2n+3 이 되므로 시간 복잡도는 2n+3이다.
또한 복잡도는 일반적으로 'big oh'표기법을 통해서 평균 실행시간을 표현
하게 되는데 위의 알고리즘의 경우는 'big oh' 표기법으로 O(n)이 된다. 복
잡도의 표기 방법에 대해서는 다음절에서 보다 자세히 살펴보도록 하겠다.
순환 알고리즘의 경우, 시간 복잡도를 구하기 위하여 명령어의 실행 횟수
를 세는 것은 위의 [예제4.4]와 같은 방법으로는 어렵다. 따라서 일반적으
로 순환 알고리즘의 시간 복잡도를 구하기 위해서는 순환식(recursive
formula)을 이용하게 된다. [예제4.3]에서 소개된 알고리즘을 예로 들면 다
음과 같다.
[예제4.5] 시간 복잡도 계산 2 알고리즘
실행횟수
float RSum(float a[], int n)
{
if(n <= 0) 1
return (0.0); 1
else
return (RSum(a, n-1) + a[n]); 1 + T(RSum(n-1))
}
명령어 총 실행횟수 = 2n + 1, 시간 복잡도 = O(n)
위의 알고리즘에서 사용된 순환식을 이용하면 명령어의 실행횟수는 다
음과 같음을 알 수 있다.
T(RSum(n)) = 2 ,if n = 0
= 2 + T(RSum(n-1) ,if n > 0
이와 같은 순환식은 또한 순환관계(recurrence relation)라고도 말하는데,
이러한 순환관계로부터 총 명령어 실행횟수를 구하는 방법은 다음과 같다.
T(RSum(n)) = 2 + T(RSum(n-1))
= 2 + ( 2 + T(RSum((n-2)) )
= 2 + ( 2 + ( 2 + T(RSum((n-3)) ) )
......
= 2×n + T(RSum(0))
= 2n + 2
따라서, 명령어 실행횟수의 총 합은 2n+2이고 시간 복잡도는 O(n)이다.
1. 알고리즘의 성능을 측정하기 위한 수단으로서 복잡도(complexity)를 사
용하며, 복잡도에는 알고리즘의 수행에 필요한 시간을 의미하는 시간 복
잡도(time complexity)와 필요한 기억장치(memory)의 크기를 의미하는 공
간 복잡도(space complexity)가 있다.
2. 공간 복잡도는 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있는
부분 즉, 변수를 저장하기 위한 공간, 순환 프로그램일 경우 순환
스택(recursion stack)등을 모두 합한 값으로 나타낸다.
3. 시간 복잡도는 알고리즘을 구성하는 명령어들의 실행횟수를 모두 합한
값으로 나타내며, 일반적인 알고리즘 분석은 시간 복잡도를 통하여 이루
어진다.
이 글에는 트랙백을 보낼 수 없습니다
0