-
[알고리즘] 가우스의 덧셈 공식알고리즘/정수론 2021. 10. 1. 12:37
목표
- 가우스 덧셈에 대해 알아보자
- 가우스 덧셈을 이용한 문제 풀이
가우스 덧셈 등장 배경
- 천재적인 수학자 독일의 가우스는 어려서부터 수학에 재능을 보였다. 가우스가 초등학교 3학년 때 수학 선생님이 1 ~ 100 숫자를 모두 합하면 얼마가 되느냐는 문제를 냈다. 가우스는 시작하지 얼마 되지 않아서 손을 번쩍 들었습니다. 오래 걸릴 줄 알았던 선생님은 가우스에게 정답을 물어봤고, 가우스는 정답을 말씀드렸다. 정답을 맞힌 가우스에게 어떻게 문제를 해결했는지, 풀이해보라고 요청했고, 가우스는 기꺼이 자신이 계산한 방법을 선생님께 말씀드린다.
가우스 덧셈 이란
- 가우스가 선생님께 가져온 계산법은 이러했다.
- 첫 숫자 1과 끝 숫자 100을 더하면 101 이 된다
두 번째 숫자 2와 끝 숫자 99를 더하면 101 이 된다.
...
모두 합하여 101은 모두 50번이 된다.
앞의 숫자와 뒤의 숫자를 더하면 모든 쌍의 합이 101이나 오며,
그 개수는 전체 개수의 절반인 50개가 된다는 점을 발견하여 풀어냈다. - 이와 같은 가우스 덧셈 방법은 수학 계산에 있어서 대표적인 창의적인 방법으로 여겨지고 있다.
가우스 덧셈 활용하기
- 연속된 숫자를 암산으로 계산해보기
1 ~ 10까지 숫자를 더한 합은?
앞의 숫자와 뒤의 숫자를 더한 합 11, 개수는 전체 개수의 절반인 5개 이므로
55라는 결과를 도출해낼 수 있다.
그림과 같이 11 × 5 이므로 55이다.
우리 모두 암산왕!! - 가우스 덧셈을 수식으로 정리해보자
a ~ b까지의 숫자를 더한 합은?
처음 숫자와, 마지막 숫자를 더한 합 = ( a + b )
더할 숫자의 개수 총합의 1/2 = ( b - a + 1) * 1/2
= ( a + b ) * ( b - a + 1) * 1/2 - 알고리즘 문제 풀어보기
프로그래머스 -https://programmers.co.kr/learn/courses/30/lessons/82612?language=javascript
문제 풀이 - https://workshop-code.tistory.com/50
정리 및 느낀 점
- 연속된 숫자를 더할 때 아주 효율적인 알고리즘이다.
참조
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=smartedumoa-balsan&logNo=220955678631
728x90'알고리즘 > 정수론' 카테고리의 다른 글
[알고리즘]나머지 연산(모듈러 연산) (0) 2024.02.27