[Algorithm] 짝수의 합 (가우스 덧셈 공식)

Algorithm

짝수의 합

 

문제
정수 n이 주어질 때, n 이하의 짝수를 모두 더한 값을 return 하도록 solution 함수를 작성해 주세요.

 

예시
n = 10, result = 30 / n = 4, result = 6

 

 

// 내가 적은 풀이
const solution = (n) => {
  let number = 0
  for(let i=0; i<=n; i+=2) {
    number += i
  }
  return number
}

// 다른 풀이
function solution(n) {
    let half = Math.floor(n/2);
    return half*(half+1);
}

 

 

기본 풀이는 for문

신박한 풀이는 가우스 덧셈

짝수의 합 알고리즘을 풀다가 신박한 풀이법이 보여서 찾아보았다.

 

이래서 개발자가 수학을 공부해야 하나 싶다.

학교 다닐 때 어렴풋이 들었던 기억이 나는 가우스 덧셈 공식을 활용해서 문제를 간단하게 풀었다.

이참에 가우스 공식이 어떤 것이며, 어떤 로직으로 돌아가는지 궁금해서 풀이를 해봤다.

 

가우스 덧셈 공식

1786년 독일의 한 초등학교 3학년 교실

뷔트너 선생님은 칠판에 수학 문제를 하나 냈다.

 

"1부터 100까지의 합을 구하시오."

 

아이들은 일제히 종이에 덧셈을 시작했다.

뷔트너 선생님은 계산을 시작한 아이들을 바라보면서 이제는 좀 쉴 수 있겠다는 생각으로 잠시 숨을 돌렸다.

1부터 차례대로 더하려면 분명 꽤 많은 시간이 걸린 것이 분명했다.

그런데 잠시 후, 한 아이가 손을 번쩍 들었다.

 

"가우스 무슨 일이지?"

"선생님, 답을 구했어요. 답은 5050 이에요!"

 

선생님은 깜짝 놀랐다.

너무나도 짧은 시간에 가우스는 정답을 정확하게 맞힌 것이다.

 

가우스의 계산법은 아주 기발했다.

등차수열의 합을 이용한 것으로 이는 어떤 수와 그 수에 차례로 일정한 수를 더하여 얻어지는 수열을 의미한다.

양 끝의 1과 100을 더한 후 50을 곱해서 50 * 101 = 5050 이라는 답에 바로 접근한 것이다.

 

 

가우스는 겨우 10살 때 이미 등차수열의 해법을 꿰뚫어 보았으며, 수의 규칙성을 깨닫고 문제를 푼 것이다.

그렇다면 가우스는 어떤 사람일까?

 

요한 카를 프리드리히 가우스

아르키메데스, 뉴턴과 함께 세계 3대 수학자

독일의 수학자로 대수학, 해석학, 기하학 등 여러 방면에 걸쳐서 뛰어난 업적을 남겨

19세기 가장 위대한 수학자라고 일컬어진다.

 

알고리즘 문제에 적용

첫 번째 예시인 n = 10 일때의 경우를 살펴보자.

하드코딩식으로 접근하자면 2 + 4 + 6 + 8 + 10 = 30 이라는 결과가 나온다.

 

여기서 가우스 공식은 가장 외곽에 있는 숫자들끼리 더하면서 접근한다.

즉, 껍질을 벗기듯이 가장 끝에 있는 수를 더하고, 그다음으로 가장 끝에 있는 수를 더하고...

 

2 + 10 = 12

4 + 8 = 12

6 = 6

 

나온 값을 보면

12 + 12 + 6

어떤 형태로 묶으면 좋을지 보이지 않는가?

같은 숫자로 표현할 수 있게 6을 넣어서 표현해보자.

6이 5개가 나온다.

(6 + 6) + (6 + 6) + 6

6 * 5

보기 쉽게 작은 숫자부터 표현하자면

5 * 6

5 * (5 + 1)

여기 또한 같은 숫자로 표현할 수 있게 5를 넣었다.

어디서 많이 본모습이다.

let half = Math.floor(n / 2);
return half * (half + 1);

아하! 똑.같.다!

 

10과 5의 연관성을 찾아보자. 거의 다 왔다! 5는 10을 2로 나눈 것

즉 n에 10을 넣어보자.

let half = 5

return 5 * (5 + 1)

이렇게 풀어서 보니까 너무 쉽다.

근데 알고리즘을 풀이할 때 이 공식을 알고 있어야 생각이 날 것 같다.

만약 공식을 모르는데 머릿속에서 떠올랐다면... 수학자가 됐어야지..

 

아무튼 이렇게 공식을 뜯어보며 어떻게 작동하는지 확실하게 알 수 있었다.

다시금 수학과 코딩의 로직은 정말 비슷하다는 것을 느꼈다.

 

프로그래머스