최근 동아리 신입생 교육에 대해서 골머리를 앓던중에 갑자기 이런생각이 들었다.
신입생들에게 과연 알고리즘을 왜 배워야하는지 설명하려면 어떻게 해야할까?
단순히 백과사전처럼 알고리즘이란
어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다. 알고리즘은 여러 단계의 유한한 집합으로 구성되는데, 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.
이라고 설명해줘야할까?
그건 아니라고 본다. 분명히 이해도 못할 뿐더러 필요성도 못느낄것이리라는 생각이 들었다.
하여 고민중에 이런 생각이 들었다.
자 제군들 1부터 100까지 더하는 프로그램을 만들어라.
아마 대부분 다음과 같은 프로그램을 코딩할것이다.
#include <stdio.h>
#include <conio.h>
int main(){
int sum, maxplus;
sum = 0;
maxplus = 100;
for(int i = 1; i <= maxplus; i++)
sum += i;
printf("%d\n",sum);
getch();
return 0;
}
그러나 알고리즘을 알고 있다거나 조금 머리가 비상한 친구는 다음과 같이 코딩을 할 수도 있을 것이다.
#include <stdio.h>
#include <conio.h>
int main(){
int sum, maxplus;
sum = 0;
maxplus = 100;
sum = (maxplus+1)*(maxplus/2);
printf("%d\n",sum );
getch();
return 0;
}
차이가 느껴지는지 모르겠다.
1부터 100까지 더하는 프로그램을 코딩할때 단순히 100번의 루프를 돌리면 간단하다.
하지만 조금더 생각해본다면 우리가 초등학교 중학교때 배웠던 방법을 응용할 수 있다.
바로 더하려는 최대값(100)의 절반값(50)이 총 최대값 + 1 만큼(101) 반복 된다는 것.
즉 1~100의 합을 구하기 위해서는 아래와 같은 식을 이용할 수 있다는 것이다.
(x/2) * (x + 1) = r
(ex: 50 * 101 = 5050)
지금 당장 이런 루틴에 머리 아프게 이런 식을 써야 하나 라는 생각을 할 수 있지만, 만약 1부터 백만까지의 수를 더해야하는 경우가 발생하다면 단순 루프의 반복보다는 계산식이 좀더 효율적일 것이다.
나는 이것이 알고리즘의 필요성을 한 절반정도 느낄 수 있게 해주리라 믿는다.
사실 알고리즘은 특정한 문제를 해결하기 위한 최적화 된 방법이기도 하지만,
어떤 문제에 부딪쳤을때 해결방법을 제시해주는 역할도 한다고 생각한다.
이 부분에 대해서는 조금 더 생각하여 쉽게 가르칠 수 있는 방법을 연구해야할것 같다.
ps1.
연산 시간에 대해서 테스트를 해봤다.
결과는 다음과 같다.
