알고리즘은 어떻게 만들까?

난 알고리즘을 만드는 방법을 체계적으로 배운 적은 없다. 다만, 그때그때 필요한 일을 시키기 위해서 컴퓨터의 생각 방식과 나의 생각 방식 사이의 연결 관계를 찾았을 뿐이다. 아마 이 작업을 알고리즘을 만드는 작업이라고 하는 것이라고 생각한다. 프로그램 제작을 직업으로 삼아서 일하시는 분들과 비교하면 아주 허접한 수준이지만, 혹시라도 누군가에게 도움이 될 수도 있다면 그것도 좋지 않을까 해서 몇자 적어둔다. 만약 틀린 부분이 있다면 지적해도 좋다.

앞서 얘기한바와 같이, 컴퓨터가 생각하는 것과 내가 생각하는 것 사이의 연결고리를 찾아내는 것이 알고리즘을 만드는 작업이다. 그렇다면, 일단 두가지를 알아야 한다. 1.컴퓨터가 생각하는 방식과 2.내가 생각하는 방식이다.

1.컴퓨터가 생각하는 방식
컴퓨터의 사고 구조는 단순하다. 숫자들을 아주 많이 늘어놓고서, 그 숫자들을 적당히 골라서 산수 계산을 하고, 그 결과를 저장한다. 그리고 이러한 일을 무작정 반복할 수 있다. 이러한 사실로부터 알 수 있는 몇가지 사실들은 컴퓨터에게 주는 자료는 숫자가 되어야 한다는 것과, 그 숫자로부터 얻을 수 있는 결과들은 역시 숫자가 된다는 것이다. 컴퓨터에게 A+B를 입력해봐야 A와 B가 뭔지 알려주지 않으면 그 출력은 A+B일 뿐이다.

2.내가 생각하는 방식
보편적인 사람이 생각하는 방식은 아주 복잡하다. 사람은 컴퓨터와 달리 논리적인 생각을 한다. 그리고 계산의 지름길을 찾아낼 수 있다. 컴퓨터가 하는 계산이 무조건 미친듯이 반복해서 답을 찾아내는 것이라면, 사람이 답을 찾는 계산은 대충 생각해보고 이미 알려진 사실로부터 답을 유도하는 것이다. 컴퓨터가 생각하는 방식으로는 아직 인간의 증명을 따라가기는 힘들다.
하지만, 사람이 할 수 없는 일들을 컴퓨터에게 시킬 수는 있다. 가령, 10425의 계승을 정확히 계산해 내는 일이라든가 등등. 10425의 계승을 사람보고 계산하라고 시키려면 누구라도 일단 짜증부터 내고 하든가 말든가 할 것이다. 하지만 컴퓨터에게 일을 시키는 것은 쉽다. 프로그램을 만들고 컴파일 한 후에 돌리면 된다.

3.알고리즘
따라서, 내가 얻고 싶은 정보와 입력할 수 있는 정보를 숫자로 나타내는 것이 가장 중요하다. 이러한 이유로, 컴퓨터를 이용해서 푸는 방법을 이용한 것이 바로 수치해석이다. 수치해석은 손으로 풀 수 없거나 풀기 힘들거나 아직 안 풀린 문제들을 당장 활용하기 위해서 근사적인 답을 찾아내는 방법을 제안해 준다. 물론 근사적인 답이라도 얼마든지 실용적으로 활용할 수 있으므로 이 분야는 연구할 가치가 있는 분야가 된다.
가령, 미분방정식을 풀어야 한다면, 찾아야 할 함수를 아주 많은 미지수로 두면 된다. 이러한 미지수들 사이의 관계식이 바로 미분방정식이 되고, 입력하는 숫자들은 바로 초기값이나 경계값이 된다.

4.실제 알고리즘은?
가령, 1부터 100까지 더하는 프로그램을 만든다고 하자
그럼 그 가상 코드는 다음과 같다.
출력(1+2+3+...+100)
자, 이 코드는 허무할 정도로 쉽다. 하지만 100까지 더하는 게 아니라 10000까지 더해야 한다면? 프로그램의 길이가 너무 길어지지 않을까? 입력하다가 차라리 계산하고 싶어질 것이다. 잔머리를 굴려라. 컴퓨터는 산수에 있어서는 아주 끝내주는 녀석이다.
숫자=1
반복(만약 숫자가 100과 같거나 작으면 계속하고, 100보다 크면 그만해라)[합=합+숫자, 숫자=숫자+1]
출력(합)
이러면 좀 짧아졌나? 게다가 원하는대로 100보다 더 많은 숫자를 넣을 때도 고칠 곳이 딱 두군데 뿐이다. 물론 코드의 길이를 더 줄일 수 있는 여지가 있지만, 그건 각자 해 보시라.

컴퓨터 프로그램 언어에는 기본적으로 다음과 같은 명령들이 있다

A=B
이 명령은 B를 A에 대입한다. 정확히는, =의 오른쪽에 있는 녀석이 가진 값들을 왼쪽에 있는 녀석의 값으로 입력해 준다.

만약(조건)[실행문] ; 아니면[실행문] ;
보통은 if ~ else 문으로 주어지는데, 계산을 하다가 멈추거나, 다른 조건들을 대입할 필요가 있을때 등, 아무튼 뭔가 판단할 때 사용할 수 있다.

반복(조건)[실행문]
이건 조건이 맞으면 조건이 틀릴 때 까지 계속 실행문을 반복실행한다. 따라서, 실행문 안에 원하는 만큼 계산을 했으면 조건을 틀리게 만드는 명령을 넣지 않으면 무한루프에 빠져버리게 될 것이므로 조심하자.

+, -, *, /, %
당연히 사칙연산 계산이다 %는 앞에 있는 수를 뒤에 있는 수로 나눈 다음에 그 나머지가 궁금할 때 사용한다.
실제로, 이것만 이용해서도 꽤 많은 것들을 할 수 있다. 가령, 3n+1문제라든가, 조화진동자 문제 등을 해결할 수 있다는 거다.


by snowall 2006. 12. 30. 01:33