알고리즘 선택하기

1부터 n까지 합을 구하는 알고리즘 ①과 알고리즘 ②를 살펴보았습니다. 어느 것이 더 효율적이라고 생각되나요?

알고리즘 ①은 n 값이 커지면 덧셈을 하는 횟수가 많아집니다. 10까지 합은 덧셈을 10번 수행해야 하고, 100까지 합은 덧셈을 100번 수행해야 합니다. n 값이 커질수록 덧셈 횟수는 훨씬 더 많아져 숫자가 커지면 계산하는 데 무리가 있습니다.

알고리즘 ②는 n 값이 커져도 덧셈, 곱셈, 나눗셈을 한 번씩만 수행하면 됩니다. 그래서 더 효율적인 알고리즘이라고 할 수 있습니다. 이처럼 알고리즘 분석은 주어진 문제를 분석하여 다양한 해결 방법을 찾은 후 가장 효율적인 방법이 무엇인지 판단하는 것입니다.

올림픽 경기에서 선수는 세세하게 분석하고 과학적으로 접근해서 0.1초를 단축하는 데 최선의 노력을 다합니다. 컴퓨터가 명령을 하나 처리하는 데 10억 분의 1초가 걸린다고 했을 때, 컴퓨터 입장에서 연산 1회 감소는 어마어마한 것입니다. 여러분이라면 100까지 합을 구할 때 100번 연산하는 알고리즘과 3번 연산하는 알고리즘 중 무엇을 선택할 것인가요?

3번 만에 연산을 끝내는 알고리즘 ②를 선택하겠지요? 이처럼 주어진 문제에서 정확한 결과가 나오는 알고리즘 중 효율성이 높은 알고리즘을 선택합니다.

우리는 좀 더 효율적인 알고리즘 ②를 스크래치에서 구현해 보겠습니다.