은빛소나기의 개발노트

최근 동아리 신입생 교육에 대해서 골머리를 앓던중에 갑자기 이런생각이 들었다.

신입생들에게 과연 알고리즘을 왜 배워야하는지 설명하려면 어떻게 해야할까?

단순히 백과사전처럼 알고리즘이란

어떤 문제의 해결을 위해 컴퓨터가 사용 가능한 정확한 방법을 말한다. 알고리즘은 여러 단계의 유한한 집합으로 구성되는데, 여기서 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.

이라고 설명해줘야할까?

그건 아니라고 본다. 분명히 이해도 못할 뿐더러 필요성도 못느낄것이리라는 생각이 들었다.

하여 고민중에 이런 생각이 들었다.

자 제군들 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.
연산 시간에 대해서 테스트를 해봤다.
결과는 다음과 같다.