영상처리 전공자를 위한 추천 교양(?)과목 - 알고리즘

가만 생각해 보니 내가 영상처리(또는 다차원신호처리)에 발을 담근지 벌써 10년이 넘었다. 워낙 게으른 나머지 뭔가를 제대로 체계적으로 공부하는 습성이 붙어 있질 않아서 아직도 아는 것이 너무나 부족함을 느끼고 있다. 이런 아픈 경험을 바탕으로 해서 영상처리 전공자를 위한 교양(?)과목을 몇 가지 추천할까 하는데, 오늘은 그 첫번째로 '알고리즘과 자료구조'이다. (항상 씨리즈 예고만 하고 첫편만 쓰는 나쁜 버릇이 있는데... -.-;; )

영상처리는 주로 전자공학 쪽에서 신호처리의 일부로 간주되어 교육되어 온 경우가 역사적으로 많았다. 예나 지금이나 알고리즘과 데이터 구조는 컴퓨터공학이나 전산학에서는 핵심 코어 필수 과목으로 가르치지만, (지금은 어떠한지 잘 모르겠지만 내가 대학 다닐 때는) 전기전자공학 쪽에서는 그렇지가 않았다. 알고리즘은 프로그래밍을 가르치면서 필요한 것들을 자연스럽게(?) 습득해야 하는 종류의 지식이었을 뿐 독립된 한 과목으로 구성해서 체계적으로 가르치질 않았다.

영상처리 전공자에게 알고리즘을 체계적으로 한 번쯤 공부해 보기를 권하는 이유는 다음과 같다. 나는 알고리즘이 적어도 학부에서 각각 두 학기씩이나 배우는 회로이론이나 전자회로보다는 훨씬 쓸모가 많다고 생각한다.

1. 영상처리에서 나오는 많은 알고리즘들은 좀 더 일반적인 알고리즘 이론을 알고 있다면 더 쉽게 이해될 수 있고 새로운 알고리즘도 그에 기반해서 생각해 낼 수 있다. 예를 들면 영상처리에서 숱하게 볼 수 있는 divide-and-conquer, greedy algorithm, dynamic programming 등에 기반을 둔 기법들을 생각해 보라.
   
2. 용어를 제대로 이해 못해서 저지르는 설명상의 오류를 줄일 수 있다. 지금 가만 생각해 보니 옛날에 나는 어떤 알고리즘을 greedy algorithm의 일종이라고 설명했었는데 지금 생각해 보니 엄밀히 말하면 틀린 설명이었다.
   
3. 연구할 때 쓸데없는 데 쓰는 시간을 줄여준다. 좀 뜬금없이 들릴 수도 있는데, 특히 reduction과 P/NP관련된 내용이 해당된다. 예를 들면 어떤 문제는 NP-Complete한 문제인데도 그걸 미처 모르고서 마땅한 최적(!)의 해를 구하는 방법을 찾아 내지 못했다며 자신의 멍청함을 원망하며 시간을 낭비하는 짓을 안 할 수 있다.
   
4. 영상처리는 결국은 컴퓨터 하드웨어나 소프트웨어로 구현되어야 하는데, 그 과정에서 알고리즘과 자료구조에 대한 지식은 매우 큰 도움이 된다. 예를 들어, 영상처리에서 자주 나오는 quad-tree나 nearest-neighbor 등을 구현하는 것을 생각해 보라.
5. '생각하는 방법'과 끈기를 가르쳐 준다.
   
   

인터넷에 좋은 공개강의가 많이 올라와 있는데... 그 중 가장 내게 도움이 된 두  가장 많이 쓰이는 교재 중 하나인 CLR책과 Sedgewick책의 저자 직강이 MIT와 프린스턴 홈페이지에 올라와 있다.

• Princeton University, Dept of Computer Science, COS226 Algorithms and Data Structures, Fall 2007
  : Sedgewick의 Algorithms in Java 씨리즈를 교재로 한 저자 직강 강의다. 나는 이 책의 옛날옛적의 C++버젼을 갖고 있는데 Algorithms in Java - Google Book Search에 상당히 많은 페이지가 수록되어 있어서 매우 유용했다.
  
• MIT, Electrical Engineering and Computer Science | 6.046J Introduction to Algorithms, Fall 2005
  : CLR의 Introduction to Algorithms 를 교재로 한 저자 직강 강의다. 강의노트, 숙제 풀이는 물론 mp3와 강의동영상까지 올라와 있으니 이 강의를 직접 듣는 것과 거의 다름없는 혜택을 볼 수 있다. Introduction to Algorithms - Google Book Search에 고맙게도 책이 모두 올라와 있으니 큰 도움이 된다.
  

이 두 강의를 비교해 보자면,

1. 위의 이유 1,2와 관련하여... 알고리즘의 기본적 접근법, 즉 예를 들면 무엇이 dynamic programming이고 어떤 종류의 성질을 만족하는 문제들은 이것을 이용해서 풀 수 있는가 등에 대해서는 CLR강의가 훨씬 도움이 된다.
   
2. CLR강의가 complexity분석이나 correctness증명 등도 더 formal하게 보여준다.
   
3. 보다 다양한 문제들에 대해, 보다 다양한 해결책들을 보여주고, 보다 최신의 결과들을 보여주기에는 Sedgewick의 강의가 더 도움이 된다.
   
4. Sedgewick의 강의노트에는 정열, 검색 등에 대해 각 알고리즘의 평균,최악 complexity등이 표로 잘 정리되어 있어서 유용하다.
5. CLR의 시험문제는 좀 더 어렵고 수학적이고, Sedgewick의 시험문제는 강의내용 이해 확인 수준이다.

저 두 강의노트를 읽다 보니, 참 세상 좋아졌다는 것을 새삼 느끼게 된다. 두 권의 강의노트를 읽으면 굳이 교과서 레벨의 알고리즘 책이 필요하다는 생각이 안 들 정도이다. 좋은 자료들을 모두에게 공유해 준 두 교수에게 경의를 표한다. 설마 이 블로그에 들어와 보진 않겠지만 이들에게 감사의 말이라도 여기 남겨야겠다. Thanks a lot for sharing your amazing lecture materials with us all around the world, Dr. Sedgewick and Dr. Leiserson !!!


ps.
Sedgewick책에 있는 저자 소개은 다음과 같다.

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University. He is a director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He earned his Ph.D from Stanford University under Donald E. Knuth.

Sedgewick 자신도 엄청난 대가인데, 자신의 소개에 굳이 Knuth의 제자라고 써 놓는 걸 보니... 정말 Knuth야말로 덜덜덜할 수 밖에 없는 슈퍼 대가인 것이다.