Development/C++
1부터 n까지의 합 구하기
대박단백질
2007. 1. 26. 23:53
C나 C++, 비베, JAVA, Delphi 등을 배우면서도, 언제나 제어문, 특히 for 문이 등장할 때 즈음해서 잘 나오는 예제가 1 .. n까지의 합 구하기인것 같습니다.
물론 for문 하나만 알면 금방 해결되는 문제이긴 합니다.
C에서라면 이렇게 되겠죠. (C++도 마찬가지겠지요...^^)
--------------------------------------------------------------
int sum = 0;
for (i = 1; i <= n; i++) sum += i;
--------------------------------------------------------------
베이직에서라면
--------------------------------------------------------------
Sum = 0
FOR i = 1 TO n
Sum = Sum + i
NEXT
--------------------------------------------------------------
Delphi라면
--------------------------------------------------------------
sum := 0;
for i := 1 to n do Sum := Sum + i;
--------------------------------------------------------------
그리고 스몰토크로 만들어보면,
--------------------------------------------------------------
| sum |
sum := 0.
1 to: n do: [:each | sum := sum + each ].
--------------------------------------------------------------
또는
(1 to: n) inject: 0 into: [:prev :each | each + prev].
--------------------------------------------------------------
그런데 이게 '누적'이라는 개념을 기반으로 하는 알고리즘이기 때문에, 프로그램을 처음 접하는 사람은 잘 이해가 안갈수 있습니다. 기본적으로 '변수'라는 것이 메모리의 한 공간이고, 거기에 값이 기록되어서 변경된다는 개념을 인지하고 있어야 비로소 이해가 되는 부분이죠.
물론 스몰토크에서는 좀 개념이 다르긴 하지만, 여기에 쓰인 것도 결국은 계산 결과의 누적을 이용한 겁니다.
그런데, 이 for에 의한 루프의 원리를 알고나면, 어디서 어디까지의 수를 가지고 계산을 하라는 문제가 나오면, 의례 for를 가지고 루프를 돌리는 것을 떠올려 버리게 되는데...
가만히 생각해 보면...
수학 문제에서 "1 ~ 1000까지의 합을 구하라."라고 나온다면, 우리는 과연 1부터 1000까지의 수를 일일이 다 더할까요. (종이에 적어가면서...)
이럴때 써먹으라고 고교 공통수학에서는 등차수열 공식이 나옵니다. 그래서 인간은 절대 저렇게 무식한 방법으로 문제를 풀지 않습니다.
1 부터 n까지 1씩 증가하는 수열의 합은 이런 공식으로 간단히 풀 수가 있죠.
제가 이런 문제를 한번 내보면, 다들 for를 사용하더군요.
1 ~ 100, 1 ~ 1000까지라고 지정한 것도 아니고, 저는 반드시 1 ~ n까지라고 얘기합니다. 왜냐면, n이 1000이 될 수도 있고, 10000이 될수도 있고, 1000000000이 될 수도 있다는 것을 암시하기 위함이었죠. 더구나 스몰토크같은 언어는 1000000000000000000000000000 이라는 말도 안되는 수도 쓸 수 있습니다.
제 아무리 빠른 CPU를 가지고 있다고 해도, 저런 말도 안되는 수를 가지고 루프를 돌리게 되면 프로그램이 먹통이 될 수밖에 없습니다. (물론 루프가 끝날때까지 한참을 기다리면 돌아오겠지요...)
for를 가르칠때, 이렇게 쓰면 좋다는 것만 얘기하지, 이렇게 쓰면 안된다는 것을 가르치는 경우는 아직까지 보질 못했습니다.
1 ~ n까지의 합은 for나 누적의 개념 같은건 몰라도 충분히 풀 수 있는 문제고, 실제로 수식을 이용해서 푸는 것이야말로 가장 효과적인 알고리즘입니다.
딱 한줄이면 끝나거든요.
n * (n + 1) / 2
C, C++, JAVA, Delphi, smalltalk 할 것없이 이거 하나만 쓰면 끝나는 문제죠.
출처 : 미확인
물론 for문 하나만 알면 금방 해결되는 문제이긴 합니다.
C에서라면 이렇게 되겠죠. (C++도 마찬가지겠지요...^^)
--------------------------------------------------------------
int sum = 0;
for (i = 1; i <= n; i++) sum += i;
--------------------------------------------------------------
베이직에서라면
--------------------------------------------------------------
Sum = 0
FOR i = 1 TO n
Sum = Sum + i
NEXT
--------------------------------------------------------------
Delphi라면
--------------------------------------------------------------
sum := 0;
for i := 1 to n do Sum := Sum + i;
--------------------------------------------------------------
그리고 스몰토크로 만들어보면,
--------------------------------------------------------------
| sum |
sum := 0.
1 to: n do: [:each | sum := sum + each ].
--------------------------------------------------------------
또는
(1 to: n) inject: 0 into: [:prev :each | each + prev].
--------------------------------------------------------------
그런데 이게 '누적'이라는 개념을 기반으로 하는 알고리즘이기 때문에, 프로그램을 처음 접하는 사람은 잘 이해가 안갈수 있습니다. 기본적으로 '변수'라는 것이 메모리의 한 공간이고, 거기에 값이 기록되어서 변경된다는 개념을 인지하고 있어야 비로소 이해가 되는 부분이죠.
물론 스몰토크에서는 좀 개념이 다르긴 하지만, 여기에 쓰인 것도 결국은 계산 결과의 누적을 이용한 겁니다.
그런데, 이 for에 의한 루프의 원리를 알고나면, 어디서 어디까지의 수를 가지고 계산을 하라는 문제가 나오면, 의례 for를 가지고 루프를 돌리는 것을 떠올려 버리게 되는데...
가만히 생각해 보면...
수학 문제에서 "1 ~ 1000까지의 합을 구하라."라고 나온다면, 우리는 과연 1부터 1000까지의 수를 일일이 다 더할까요. (종이에 적어가면서...)
이럴때 써먹으라고 고교 공통수학에서는 등차수열 공식이 나옵니다. 그래서 인간은 절대 저렇게 무식한 방법으로 문제를 풀지 않습니다.
1 부터 n까지 1씩 증가하는 수열의 합은 이런 공식으로 간단히 풀 수가 있죠.
n x (n + 1) / 2그런데 왜 프로그래밍 문제에서는 이렇게 안하는 걸까요?
ex) n = 1000 이라고 하면: 1000 x ( 1000 + 1) / 2 = 500500
제가 이런 문제를 한번 내보면, 다들 for를 사용하더군요.
1 ~ 100, 1 ~ 1000까지라고 지정한 것도 아니고, 저는 반드시 1 ~ n까지라고 얘기합니다. 왜냐면, n이 1000이 될 수도 있고, 10000이 될수도 있고, 1000000000이 될 수도 있다는 것을 암시하기 위함이었죠. 더구나 스몰토크같은 언어는 1000000000000000000000000000 이라는 말도 안되는 수도 쓸 수 있습니다.
제 아무리 빠른 CPU를 가지고 있다고 해도, 저런 말도 안되는 수를 가지고 루프를 돌리게 되면 프로그램이 먹통이 될 수밖에 없습니다. (물론 루프가 끝날때까지 한참을 기다리면 돌아오겠지요...)
for를 가르칠때, 이렇게 쓰면 좋다는 것만 얘기하지, 이렇게 쓰면 안된다는 것을 가르치는 경우는 아직까지 보질 못했습니다.
1 ~ n까지의 합은 for나 누적의 개념 같은건 몰라도 충분히 풀 수 있는 문제고, 실제로 수식을 이용해서 푸는 것이야말로 가장 효과적인 알고리즘입니다.
딱 한줄이면 끝나거든요.
n * (n + 1) / 2
C, C++, JAVA, Delphi, smalltalk 할 것없이 이거 하나만 쓰면 끝나는 문제죠.
출처 : 미확인