DataStructure와 알고리즘은 어떻게 공부해야 할까..
처음접하는 것이라면 배열 -> 스택 -> 큐 -> 리스트 -> 트리 순서로 나가는 것이 좋을듯. 정렬과 해싱 이하 뒤의 꺼는 아마 이번달내로 나가기 힘들것 같은데. 트리나 그래프까지만 목표로 잡아도 성공이라고 생각함.
그리고, 자료구조 레포트 선배들이 한 것이 있으니까, 그 문제들 구현을 목표로 잡아도 좋고. (원한다면 보내줄께.) ex) 스택:스택 구현, postfix 의 구현, 계산기 구현. 큐:큐 구현. 리스트:다항식 덧,뺄셈 & 곱셈 구현 (polynomial) 트리:2진트리구현
자료구조는 일단 1. 각각의 자료구조들의 특징을 이해하고. 2. 실제의 구현법을 익히며 (뭐.요새는 collection library들을 제공하므로 직접구현할 일이 줄어들었긴 했지만. 그래도 여전히 기초가 됨) 3. 해당 문제상황에 적절한 자료구조를 선택할 수 있는 눈을 다듬어야 함. --석천
제가 생각컨데, 교육적인 목적에서는, 자료구조나 알고리즘을 처음 공부할 때는 우선은 특정 언어로 구현된 것을 보지 않는 것이 좋은 경우가 많습니다 -- 대신 pseudo-code 등으로 그 개념까지만 이해하는 것이죠. 그 아이디어를 Procedural(C, 어셈블리어)이나 Functional(LISP,Scheme,Haskel), OOP(Java,Smalltalk) 언어 등으로 직접 구현해 보는 겁니다. 이 다음에는 다른 사람(책)의 코드와 비교를 합니다. 이 경험을 애초에 박탈 당한 사람은 귀중한 배움과 깨달음의 기회를 잃은 셈입니다. 참고로 알고리즘 교재로는 10년에 한 번 나올까 말까한 CLR(Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)을 적극 추천합니다(이와 함께 혹은 이전에 Jon Bentley의 Programming Pearls도 강력 추천합니다. 전세계의 짱짱한 프로그래머/전산학자들이 함께 꼽은 "위대한 책" 리스트에서 몇 손가락 안에 드는 책입니다. 아마 우리 학교 도서관에 있을 것인데, 아직 이 책을 본 적 없는 사람은 축하드립니다. 아마 몇 주 간은 감동 속에 하루하루를 보내게 될 겁니다.). 만약 함께 스터디를 한다면, 각자 동일한 아이디어를 (같은 언어로 혹은 다른 언어로) 어떻게 다르게 표현했는지를 서로 비교해 보면 또 배우는 것이 매우 많습니다. 우리가 자료구조나 알고리즘을 공부하는 이유는, 특정 "실세계의 문제"를 어떠한 "수학적 아이디어"로 매핑을 시켜서 해결하는 것이 가능하고 또 효율적이고, 또 이를 컴퓨터에 어떻게 구현하는 것이 가능하고 효율적인지를 따지기 위해서이며, 이 과정에 있어 수학적 개념을 프로그래밍 언어로 표현해 내는 것은 아주 중요한 능력이 됩니다. 개별 알고리즘의 카탈로그를 이해, 암기하며 익히는 것도 중요하지만 더 중요한 것은 알고리즘을 생각해 낼 수 있는 능력과 이 알고리즘의 효율을 비교할 수 있는 능력, 그리고 이를 표현할 수 있는 능력입니다.
첫번째가 제대로 훈련되지 못한 사람은 알고리즘 목록의 스테레오 타입에만 길들여져 있어서 모든 문제를 자신이 가진 알고리즘 목록에 끼워맞추려고 합니다. DesignPatterns를 잘 못 공부한 사람과 비슷합니다. 이 사람들은 마치 과거 수학 정석을 수십번을 공부해서 문제를 하나 던져주기만 하면, 생각해보지도 않고 자신이 풀었던 문제들의 패턴 중 가장 비슷한 것 하나를 기계적, 무의식적으로 풀어제끼는 "문제풀이기계"와 비슷합니다. 그들에게 도중에 물어보십시오. "너 지금 무슨 문제 풀고있는거니?" 열심히 연습장에 뭔가 풀어나가고는 있지만 그들은 자신이 뭘 풀고있는지도 잘 인식하지 못하는 경우가 많습니다. 머리가 푸는 게 아니고 손이 푸는 것이죠.
두번째가 제대로 훈련되지 못한 사람은 일일이 구현을 해보고 실험을 해봐야만 알고리즘간의 비교를 할 수 있습니다. 특히 자신이 가진 카탈로그를 벗어난 알고리즘을 만나면 이 문제가 생깁니다. 이건 상당한 댓가를 치루게 합니다.
세번째가 제대로 훈련되지 못한 사람은, 문제를 보면 "아, 이건 이렇게 이렇게 해결하면 됩니다"라는 말은 곧잘 할 수 있지만 막상 컴퓨터앞에 앉혀 놓으면 아무 것도 하지 못합니다. 심지어 자신이 생각해낸 그 구체적 알고리즘을 남에게 설명해 줄 수 있기까지 하지만, 그들은 그걸 "컴퓨터에게" 설명해 주는 데에는 실패합니다. 뭔가 생각해 낼 수 있다는 것과, 그걸 컴퓨터가 이해할 수 있게 설명할 수 있다는 것은 다른 차원의 능력을 필요로 합니다.
그리고 마지막으로, 자료구조/알고리즘 공부를 할 때에는 가능하면 실질적이고 구체적인 실세계의 문제를 함께 다루는 것이 큰 도움이 됩니다. 모든 학습에 있어 이는 똑같이 적용됩니다. 인류의 지성사를 봐도, 구상(concrete) 다음에 추상(abstract)가 오고, 인간 개체 하나의 성장을 봐도 그러합니다. be 동사 더하기 to 부정사가 예정으로 해석될 수 있다는 룰만 외우는 것보다, 그러한 다양한 예문을 실제 문맥 속에서 여러번 보는 것이 훨씬 나은 것은 자명합니다. 알고리즘/자료구조 공부를 할 때 여러 친구들과 함께 연습문제(특히 실세계의 대상들과 관련이 있는 것)를 풀어보기도 하고, ACM의 ICPC 등의 프로그래밍 경진 대회의 문제 중 해당 알고리즘/자료구조가 사용되는 문제를 -- 이게 가능하려면 "이 알고리즘이 쓰이는 문제는 이거다"라는 가이드를 해줄 사람이 있으면 좋겠죠 -- 같이 풀어보는 것도 아주 좋습니다.
--김창준
알고리즘/자료구조 교육에 대한 불만
우리는 알고리즘 카탈로그를 배운다. 이미 그러한 해법이 존재하고, 그것이 최고이며, 따라서 그것을 달달 외우고 이해해야 한다. 좀 똑똑한 친구들은 종종, "이야 이거 정말 기가막힌 해법이군!"하는 감탄을 외칠지도 모른다. 대부분의 나머지 학생들은 그 해법을 이해하려고 머리를 쥐어짜고 한참을 씨름한 후에야 어렴풋이 왜 이 해법이 그 문제를 해결하는지 납득하게 된다. 그리고는 그 "증명"은 책 속에 덮어두고 까맣게 사라져버린다. 앞으로는 그냥 "사용"하면 되는 것이다. 더 많은 대다수의 학생은 이 과정이 무의미하다는 것을 알기 때문에 왜 이 해법이 이 문제를 문제없이 해결하는지의 증명은 간단히 건너뛰기를 한다.
이런 학생들이 주어진 알고리즘을 사용하는 소위 "객관식" 혹은 "문제출제자"가 존재하는 시험장 상황 하에서는 뛰어난 성적을 보일것임은 자명하다. 하지만 스스로가 문제와 해답을 모두 만들어내야 하는 상황이라면, 알고리즘을 완전히 새로 고안해내야 하는, 또는 기존 알고리즘을 변형해야 하는 대다수의 상황이라면 어떨까?
교육은 물고기를 잡는 방법을 가르쳐주어야 한다. 어떤 알고리즘을 배운다면, 그 알고리즘을 고안해 낸 사람이 어떤 사고의 과정을 거쳐서 그 해법에 도달했는지를 구경할 수 있어야 하고, 학생은 각자 스스로만의 해법을 차근 차근 "구성"(construct)할 수 있어야 한다(이를 교육철학에서 구성주의라고 하는데, 레고의 아버지이고 마빈 민스키와 함께 MIT 미디어랩의 선구자인 세이머 페퍼트 박사가 주창했다). 전문가가 하는 것을 배우지 말고, 그들이 어떻게 전문가가 되었는가를 배우고 흉내내라.
결국은 소크라테스적인 대화법이다. 해답를 가르쳐 주지 않으면서도, 초등학교 학생이 자신이 가진 지식만으로 스스로 퀵소트를 유도해 낼 수 있도록 옆에서 도와줄 수 있는가? 이것이 우리 스스로와 교사들에게 물어야 할 질문이다.
--김창준
고등학교때부터 흘러온 교육방식의 폐해가 아닐까 하네요. '무엇을, 왜' 라는 질문 이전에 '어떻게' 가 머릿속에 들어와버리는. --석천
왜 우리는 학교에서 "프로그래밍을 하는 과정"이나 "디자인 과정"을 배운 적이 없을까? 왜 해답에 이르는 과정을 가르쳐주는 사람이 없나? 우리가 보는 것은 모조리 종적 상태의 결과물로서의 프로그램 뿐이다. 교수가 어떤 알고리즘 문제의 해답을 가르칠 때, "교수님, 교수님께서는 어떤 사고의 과정을 거쳐, 그리고 어떤 디자인 과정과 프로그래밍 과정을 거쳐서 그 프로그램을 만드셨습니까?"라고 물어보자. 만약 여기에 어떤 체계적인 답변도 할 수 없는 사람이라면, 그 사람은 자신의 사고에 대해 사고해 본 적이 없거나, 문제 해결에 어떤 효율적 체계를 갖추지 못한 사람이며, 따라서 아직 남을 가르칠 준비가 되어있지 않은 사람이다. --김창준
알고리즘을 공부하면 큰 줄기들을 알아야 합니다. 개별 테크닉들도 중요하지만 "패러다임"이라고 할만한 것들을 알아야 합니다. 그래야 알고리즘을 상황에 맞게 마음대로 응용할 수 있습니다. 또, 자신만의 분류법을 만들어야 합니다. (see also HowToReadIt Build Your Own Taxonomy) 구체적인 문제들을 케이스 바이 케이스로 여럿 접하는 동안 그냥 지나쳐 버리면 개별자는 영원히 개별자로 남을 뿐입니다. 비슷한 문제들을 서로 묶어서 일반화를 해야 합니다. (see also DoItAgainToLearn)
이와 관련해서 Anany Levitin의 A NEW ROAD MAP OF ALGORITHM DESIGN TECHNIQUES(DDJ, 2000 Apr)를 권합니다. 그는 알고리즘 디자인 테크닉을 다음 네가지로 크게 나눕니다:
- brute force
- divide-and-conquer
- decrease-and-conquer
- transform-and-conquer
자료구조와 알고리즘은 프로그램을 만드는 데 있어서 중요하다고 생각합니다. 남이 만든 자료구조와 알고리즘을 이용하는데 그치지 말고 스스로 생각하여 만드는 경지에 오르면 좋겠습니다. -강희경
DeleteMe) 1학기끝나가는 마당에 후회 막급임. 모든 것들을 한번씩 구현해보고 갔어야하는데... 새로 들으시는 분들 꼭 한번씩 구현해보세요. 지금 생각해보니 정작 중요한 것을 등한시한 느낌입니다 - eternalbleu
see also HowToStudyDesignPatterns
