강좌 전 태오의 잡담>

김민오님의 알고리즘 강좌가 올라오기 시작하고 있습니다. 프로그래밍에서 알고리즘은 상당히 중요한 부분임은 다들 아실 겁니다. 언어는 바뀌어도 알고리즘은 영원하다... .NET 정품출시를 앞두고 알고리즘에 시간을 좀 더 투자하는 것은 어떨까요? 이상 버지니아에서 임시 특파원 태오였씀다.. 요거이 왔땀다.
아아.. 이 강좌의 분류는.. ASP 팁 쪽으로 일단 정했으니 착오없으시기 바랍니다.

강좌 시작 >

1) 알고리즘의 정의 

안녕하세요 taeyo 님 싸이트에서 처음 강좌를 맡게 된 caelin 이라고 합니다. ^^*    앞으로 읽어주시는 분이 많다면 계속 강좌를 올릴생각이구요..인기 없으면 퇴출당하는거죠 ..히히..    일단 제가 알고리즘에 대해서 강좌를 하게 된 배경은 이 글을 읽는 대부분의 프로그래머들은  아마 웹프로그래머 라는 직업을 가지고 계시는 분들일것입니다. (그중에서도 asp 겠죠?)  저역시 한때 웹프로그램을 하였었고 처음시작을 웹프로그램부터 시작했었습니다. 지금도 마찬가지지만 그당시 저한테 taeyo 님의 책은 한줄기 빛같은 것이였죠..굉장히 쉽게 설명을 해주셨기에 프로그램의 개념을 잡을수 있었고 재미도 붙일수 있었습니다... 

그러던중 어느때부턴가 제머리속에서 떠나지 않는 고민거리가 하나 찾아 왔습니다..  과연 taeyo 님이 게시판 만드는 법을 가르쳐 주지 않았다면 내가 내힘으로 게시판을 만들수 있었을까 하는 고민이죠.. 단순히 database 에 접속해서 recordset 를 가져 오는것만으로 저는 게시판을 만들수 있었을까요? 여러분은 어떤가요 ?? 

Database 를 이용하는 방법에 대한 책은 시중에 무수히 많습니다..  하지만 그책을 보고 우리는 답변형 게시판을 만들수 있었을까요 ? 아마도 힘들었으리라 생각됩니다..우리는 태요님이 생각해 내신 답변형 게시판 알로리즘이 있었기에 힘들이지 않고 답변형 게시판을 만들수 있었던 것입니다..  하지만..여러분이 taeyo 님의 책이 나오기전에 답변형 게시판을 만들어야 했다면..? 여러분은 아마 엄청난 고생을 하셨을것입니다. 하지만 그이후 의 내공은 실로 엄청나게 높아졌음을 여러분 스스로 느끼게 될것이고 그것은 여러분의 재산이 될것입니다.  그런 알고리즘을 하나 생각해 내는것만으로도 여러분은 유명한사람이 될수도 있다는거죠..  결국 프로 그래머는 어떤 프로그램을 할줄 아느냐보다. 어떤 알고리즘을 만들줄 아느냐에 밥줄이 달렸다해도 과언이 아닙니다..

우리에게는 asp 와 IIS 라는 망치와 못이 있고 MS-SQl 이라는 나무가 있습니다. 하지만 이것만으로 우리는 멋진 집을 지을수 있을까요 ?  우리가 집을 짓기 위해서는 설계도도 있어야 하고 경험도 있어야 하고 나무를 자르는 법과 망치질을 하는 법을 배워야만합니다..이것이 바로 알고리즘입니다. 

하지만 지금 현실을 어떠한가요..? 회사에서 쇼핑몰 만들어라..게시판 만들어라 하면 인터넷에 많이 공개되어 있는 알고리즘을 그냥 가져다 쓰지는 않으신지요.  그렇게 인터넷에서 가져다 쓰는게 나쁘다는 뜻은 절대 아닙니다. 하지만 한번쯤 여러분은 여러분만의 알고리즘으로 게시판도 만들어 보고 쇼핑몰도 만들어 보려고 노력은 해보셨는지 궁금합니다.

여러분이 앞으로 무엇을 만들던 간에 남의 알고리즘을 배끼지 않고 한번쯤이라도 그 문제에 대해서 고민함으로써 (그것이 성공하던지 실패하던지 간에..) 여러분은 진정한 프로그래머가 될수 있지 않을까 생각합니다. ( 저역시 아직 밥줄걱정하는 프로그래머중 하나 입니다. :) 무슨 프로그램으로 만드느냐와 (asp, jsp, vb , vc++ 등등 ) 무엇을 만드느냐 ( database 연동 프로그램 , 익스플로러, 쇼핑몰 등등..) 은 알로리즘 강의 에서 별로 중요하지 않은거 같습니다.

우리는 어떤 사고방식을 가지고 프로그램을 해야 하는가.! 사람이 할수 있는일과 컴퓨터가 할수 있는 일의 차이점은 무엇이고 그차이점을 우리는 어떤식으로 이용해야 하는가에 대한 얘기를 지금부터 하려고 합니다. (서론이 좀 길었죠..?헤헤..)

앞으로 이야기는 상당히 수학적인 내용일수도 있어서 상당히 재미가 없는 내용이 될것이라고 저역시 생각하지만 여러분이 직업을 바꾸실 생각이 없으시다면 30분정도 시간을 내셔서 그냥 재미 없는 소설책 읽는다 생각하시고 끝까지 읽어주시기 바랍니다 . 그리고 앞으로 가능하면 영어는 쓰지 않고 한글로 하겠습니다. (제가 영어가 많이 딸립니다 . T.T) 그리고 간혹 반말이 섞이더라도 이해 부탁 드립니다. 

이제 알고리즘공부를 왜 해야만 하는지는 말씀드린거 같고. 우선 말씀드리고 싶은것은 "절대적으로 최상의 알고리즘은 없다 " 입니다. 즉 어떤 상황에서도 가장 잘맞는 알고리즘은 존재하지 않고, 항상 주어진 문제의 상황과 제한점이 주어질때에만 최상의 알고리즘을 선택할수 있다는 것입니다. 이것은 경험상 나온것일 수도 있고 통계적으로 나온것을 보고 알고리즘을 구현할수도 있다는 뜻이기도 합니다.

사실 알고리즘이란 어떤 추상적인 것일지도 모르기때문에 이것에 관해서 더 설명을 해드리고 싶고 어떻게 연구 되어 왔는지도 말씀드리고 싶지만 .. 제가 강좌를 많이 봐온결과 그런게 설명이 너무 길면 지루하더라구요..그래서 일단 맛뵈기로 "최대 공약수" 를 찾는 알고리즘을 같이 생각해 보기로 하겠습니다.  ( 여기서 여러분은 난 최대공약수 찾는 프로그램따위는 만들일없을껄 ? 하실지도 모르겠습니다. 저역시 이것을 써본적 없습니다..아까도 말씀드렸듯이 이강좌에서 무엇을 만드느냐는 별로 중요한게 아님을 다시 한번 강조해 드립니다.)

(2) 유클리드의 알고리즘 (Euclid`s algorithm) 일명 최대공약수 알고리즘.

이 알고리즘은 전산과를 졸업하신 분들은 알고리즘 시간에 배웠다고 하더군요..(가조기님이 말씀해 주셨습니다 T.T) 더군다나 이 알고리즘은 실제프로그래밍 하는데 별로 도움이 될만한 알고리즘이 아님에도 첫번째로 소개시켜드리는 이유는 이 알고리즘의 특징이 컴퓨터가 하는일과 사람의 하는 일의 차이를 아주 극명하게 대조해서 보여줍니다.

저의 경우 이 알고리즘을 보고 나서 알고리즘 공부를 시작했고 여러분도 그렇게 느꼈으면 하는 마음에서 유클리드 알고리즘 을 선택하게 되었음을 미리 밝힙니다. 일단 우리는 중학교를 졸업한지가 오래 됐기때문에 최대 공약수 정의에 대해서 다시 말씀드리면 "주어지는 두정수의 약수중에서 가장 큰 공통되는 약수( 아 뭔가 말이 너무 어렵다 --;)" 입니다.

약수란 예를 들어 7을 나머지 없이 나눌수 있는 정수 입니다. 7 의 경우 1과 7밖에 없겠죠? 10의 약수는 1, 2, 5, 10 이 되겠죠 ?

ex ) 280 과 30의 최대공약수 구하기

280 의 약수와 30의 약수중 공통되는것은 1, 2, 5, 10 이며 이중에서 제일 큰 10 이 바로 최대 공약수 입니다.!!

아 그럼 이것을 우리는 중학교때 어떻게 풀었을까요. 기억나실지 모르지만 우리는 이것을 소인수 분해 라는 것으로 풀었었습니다.

여기서 280과 30을 나누었던 2와 5를 곱하면 나오는 수 10 이 우리가 했던 최대공약수 구하는 방법이었습니다. (기억 안나지죠? 저도 기억 안남 T.T) 이방법은 대단히 좋은 방법이기는 하지만 어디까지나 사람이 풀기에 좋은 방법입니다. 컴퓨터에 이방법을 적용하기는 좀껄끄럽습니다. 왜냐하면 공통되는 인수 (2, 5) 를 구하기가 컴퓨터에게는 여간 힘든 작업이 아니기 때문이죠... 그렇다면 어떻게 해야 할까요 ?

A와 B라는 정수가 있다고 가정합시다. 이 A와 B는 최대공약수로써 G를 갖는다고 한다면 A와 B는 다음과같이 표현할수 있습니다.  

A = a * G (A가 280 이라고 가정하면 280 = 28 * 10   여기서 28은 위에서 구한 더이상 나누어 떨어지지 않는정수(공식1 ) 입니다.) 

B = b * G (B가 30 이라고 가정하면 30 = 3 * 10   여기서 3은 위에서 구한 더이상 나누어 떨어지지 않는정수 입니다.)

여기서 한번만 더 생각해 봅시다. (수학시간 같지만 프로그램과 수학은 떨어질수 없는 사이 입니다.) 그렇다면 A - B (즉 여기서는 280 - 30 ) 과 B (여기서는 30) 의 최대공약수는 얼마 일까요 ?

ex) 즉 250 과 30의 최대 공약수는 ? 

이것을 소인수 분해로 풀어 보면

잘보시면 250 과 30의 최대 공약수 역시 2 * 5 = 10 이라는 결론이 나옵니다..  그렇다면 250 - 30 (즉 220 ) 과 30의 최대 공약수는 ?? 이것역시 소인수 분해로 풀어 보면

여기서도 최대공약수는 10 이됩니다. .  우오오오~~ 그렇습니다..우리는 여기서 뭔가의 규칙을 찾을수 있을것만 같습니다..   즉 두숫자의 최대 공약수를 구하는 알고리즘에서 A 와 B의 최대공약수와 둘중에 더 큰수 A에서 B를 뺀숫자 (여기스는 250 혹은 220 )과 B (여기서는 30) 의 최대 공약수는 같다는 결론이 나옵니다..  그렇다면 이것을 구현하는 함수가 있다면..이렇게 표현할수 있을거 같습니다.

function get_gcd(int u, int v ) 라는함수가 있다고 생각합시다. 이 함수는 두정수를 입력하면 최대공약수가 나오는 함수입니다.

헉헉...어떻게 구했는지 잘모르겠지만. 어쨌든 우리는 우리가 원하던 10이라는 숫자를 찾았습니다.. 매우 긴과정이지만 컴퓨터는 이런것을 더 좋아 하고 실제로 구하는데 0.1 초도 안걸립니다.. 이 유클리드의 알고리즘을 말로 표현하면 다음과 같습니다.

  1. 임의의 두정수 u 와 v를 입력 받는다
  2, v가 u보다 크면 v와 u 의 값을 교환한다 (식 2적용)
  3. u 에다가 u-v의 값을 저장한다. (식 1적용)
  4. u 가 0인가 ? 0이 아니면 2로 돌아 가고
      0 이라면 v가 최대 공약수 이다!!!!!! (식 3적용)

이것을 여러분이 좋아 하시는 asp 로 구현하면

이것을 사용하는 방법은

이것이바로 유클리드 알고리즘이란 것입니다. 이해가 되셨는지 모르겠지만. 첫강의 치고는 너무 수학적인 내용이 많아서 어려웠던거 같습니다..  하지만 여러분이 이것을 이해를 했던 안했던 그것은 별로 중요하지 않습니다. 다만 여러분은 이것을 보고 "아 컴퓨터가 일하는 방법과 사람이 일하는 방법은 많이 다르구나",   "나도 프로그래머로 먹고 살기 위해서는 알고리즘이란걸 공부 해야 겠구나..." 라는 생각을 가져 줬으면 하는 게 제 바람입니다. (반드시 이런생각이 들어야 하는데 흑..) 우리는 프로그래머라는 직업을 가지고 있는 사람이기에 다른 사람이 편하게 쓸수 있는 프로그램을 만드는 창조적인 일을 하는 사람들입니다.  이프로그램을 짤때는 어떤 알고리즘으로 구현해야 할지를 우리는 항상 생각해야 합니다.. ^^;

오늘 강의가 너무 수학적이었던 관계로 다음 강의는 알고리즘의 영원한 숙제라 할수 있는 정렬 알고리즘과 검색 알고리즘에 대해서 이야기해볼까 합니다. 그리고 재귀함수 에 대한 이야기와 시간이 되면 게시판 list 보기의 전혀 다른 페이징 방법에 대해서도 같이 고민해 보고자 합니다. ...

혹시라도 질문있으신 분은 메일 주세엽...~~ caelin@dreamwiz.com

Back