1 ~ n까지 합을 구하는 원리
전에 1 ~ n 까지 합 구하기 문제에 관해서 글을 올렸지만, 내용을 좀 더 보충하고자 합니다.
그럼 1에서 n까지의 합을 구하는 문제에 대해서 처음부터 다시 생각해 보겠습니다.
이 문제 자체의 정의를 그대로 프로그램으로 표현한다고 하면, 1에서 n까지의 수를 카운트해서 전부 더하면 됩니다. 일단 문제의 정의에 가장 충실하면서도, 구현도 비교적 간단합니다.
그러나, n이 10, 100, 1000, 10000 정도까지라면 이 알고리즘에 별다른 문제는 발생하지 않지만, 만일 n이 10억, 100억 단위로 커지게 되면 문제가 발생합니다.
반복적 제어구조를 이용하기 때문에, 그만큼의 숫자를 카운트하려다 보면 알고리즘의 수행성능이 대단히 느려집니다. 그러면, 주어진 문제에 대한 해법을 다른 방식으로 찾아볼 필요가 있습니다.
자, 우선 n = 5 라고 가정하고, 1부터 5까지의 합을 계산해 봅시다.
1 + 2 + 3 + 4 + 5 = ?
잠깐... 이걸 한번 그래픽으로 표현해 볼까요?
인간의 뇌는 뭔가를 그림으로 표현할때 이해가 잘 되는 법입니다.
○
○○
○○○
○○○○
○○○○○
앗, 삼각형이 되는군요!
그렇다면, 1 ~ 5의 합계는 결국 삼각형의 넓이라는 것으로도 표현될 수 있을 겁니다.
바로 계산해 봅시다.
삼각형의 넓이 = 밑변 x 높이 / 2
→ 5 x 5 / 2 = 12.5 (??)
어.. 뭔가 답이 이상하죠? 그야 당연한 결과입니다. 삼각형의 넓이는 사각형의 넓이의 절반이라는 개념에서 나온것입니다. 그러니까, 우선 삼각형을 사각형으로 변환하지 않으면 안됩니다. 그래서 밑변 x 높이를 해주는 것이죠.
그런데, 5 x 5를 하게되면...
○○○○○
○○○○○
○○○○○
○○○○○
○○○○○
이런 사각형이 되는 겁니다. 구하고자 하는 삼각형의 2배 넓이를 가지는 사각형을 만들어야 하기 때문에, 제대로 하자면 이렇게 되어야 합니다.
○○○○○○
○○○○○○
○○○○○○
○○○○○○
○○○○○○
자, 그럼 계산해 보죠.
5 x (5 + 1) / 2 = 15
자, 그럼 이 공식을 일반화 해볼까요?
5라는 숫자 대신, n으로 바꿔주면 됩니다.
n x (n + 1) / 2
자, 그러면 1 ~ n까지의 합이란 문제에 대해서... 위의 공식만 대입하면 끝나는 겁니다. n이 아무리 큰 숫자가 들어와도 단 한줄의 수식만 처리하면 됩니다. 알고리즘의 속도는 비교할 것이 못됩니다.
제가 여기서 강조하는 싶은 건, 공식이 아니라, 수학적인 사고 방법입니다. 수학은 복잡해 보이는 것을 단순하게 만들어 놓고 계산하는 것입니다. 이것이 바로 '추상화'의 과정입니다. 수학은 이런 추상화의 과정 위에서 비로소 계산을 시작하는 겁니다. 그래서 수학은 숫자의 학문이 아니라, 생각의 학문이라고 합니다.
그리고 또 한가지 말하고 싶은 것은, 문제를 해결하는 관점을 여러 각도에서 생각해 보자는 겁니다. 문제를 풀어나가는 방법은 여러가지가 있을 수 있습니다. 위에서 예를 든 경우도, 반복을 통한 누적계산으로 풀어나가는 방법과, 수식으로 계산하는 방법이 있습니다.
둘다 장단점은 있습니다.
누적계산은 문제의 정의를 가장 충실하게 구현한 것이고, 따라서 더 이해하기도 쉽습니다. 하지만 n이 무한히 커지면 수행속도가 현저히 떨어지는 문제가 있습니다. 반면 수식을 통한 방법은 성능에 있어서는 탁월하지만, 저 공식이 어떤 원리로 나왔는지 모를경우에는 저게 뭐하는 것인지 잘 이해가 안될겁니다. (주석이 안달려 있다면 말이죠)
제가 전에 올렸던 피보나치 수열 구하는 방법도 역시, 문제의 정의에 따라서 충실히 구현한 방법과, 황금분할비를 이용해서 곱셉으로 처리하는 방법이 있었습니다. 세상에 한가지 약으로 만병을 치료할 수 없듯이, 어떤 문제에 대해서도 하나의 알고리즘이 만능으로 적용되지는 않는다고 봅니다. 그때 그때 상황에 따라서 방법을 바꿀 필요도 있는 것입니다.
문제를 바라보는 관점에 따라서 얼마든지 방법은 달라질 수 있습니다.
마지막으로, 한가지 문제를 내보겠습니다.
심심하신 분들은 한번 도전(?)해 보시죠...(^^)
[문제]
위에서 1 ~ n까지의 합을 구하는 공식을 만들었습니다. 그러면 1부터가 아니라, a ~ b까지의 합을 구하는 것은 어떻게해야 할까요? 그리고 1씩 증가하는 수열이 아니라 2나 3 등으로 증가하는 수열에 대해서 공통으로 적용될 수 있는 방법은 무엇일까요?
이에 대한 저의 답안은 아래에 있습니다.
이것을 스몰토크에서 표현하면...
Interval>>sum
^(self first + self last) * self size / 2
-----------------------------------------------
출처 : http://sizuha-textcube.blogspot.kr/2006/04/1-n%EA%B9%8C%EC%A7%80-%ED%95%A9%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%9B%90%EB%A6%AC.html
