수열이란?
1, 2, 3, #, 5, 6
#에 들어갈 숫자는?
예측한대로 4가 들어올것이다.
우리는 여기서 알 수 있듯이 1씩 차례대로 늘어난다는 것을 알았다.
이와같이 규칙을 가진 숫자를 수열이라고 한다.
등차수열이란?
예시를 먼저 들어보겠다.
수열 a = 3, 5, 7, 9, 11... // 2씩 증가
수열 b = 11, 6, 1, -4... // -5씩 감소
수열 c = 6, 6, 6, 6... // 0
공차란 것은 수열이 나열되있을때 차이값을 말한다.
초항이란 것은 첫번째 값을 나타낸다.
수열 a의 공차는 2 초항은 3이다.
등차수열의 일반항

예시를 들어보겠다.
임의의 n번째 항을 n에 관한 식으로 나타낸 것을 등차수열의 일반항이라 한다.
위의 식으로 예시를 들어보겠다.
3,5,7,9,11...의 경우
공차 = 2
초항 = 3
공차가 2이기 때문에 2n을 만든다. 그후 초항이 3이기 때문에
2n+1 = 3
즉 n에 1을넣고 1을 더해서 3이되면 된다.
2를 넣으면 두번째 값인 5가 나온다.
등차수열의 합 구하기
등차수열의 항이 홀수일때
ex) 3, 5, 7, 9, 11
정가운데는 7이다.
여기서 공차는 a라고 가정한다면 구하는 식은
3 = 7-2a
5 = 7-a
7 = 7
7 = 7+a
7 = 7+2a
이런식으로 가운데부터 차례대로 식을 나열하게되면 공통되는 부분은 바로 3도 2a를 가지고있고 7도 2a를 가지고있다.
여기서 위의 식을 모두 더하게 되면 7이 5개 남게된다.
즉 7x5가 위 등차수열의 합이 된다.
등차수열의 항이 짝수일때
ex) 1, 2, 3, 4, 5, 6
홀수처럼 정가운데가 없다.
합을 구하는방법은 간단하다.
위의 예를 토대로 처음 끝과 마지막을 더해주면 값은 7이된다.
1 + 6 = 7
두번째값과 마지막에서 두번째를 더해주면 또 값이 7이된다.
2 + 5 = 7
이렇게 반복하여 보면 결국 또 7만 남게된다.
결과 = 7 + 7 + 7 = 7 x 3
두개의 방법도 있지만 짝수냐 홀수냐 구분없이 구하는 공식도 있다.

ex)1, 2, 3, 4, 5, 6
Sn = 합(21)
a1 = 1(초항)
an = 6(마지막 수)
n = 등차수열 총 갯수(6)
간단한 방법이라 따로 설명은 생략하겠다.
'알고리즘 메모 > 분할 정복 헷갈렸던 부분' 카테고리의 다른 글
| 이분탐색 시 헷갈렸던 부분 (0) | 2023.05.28 |
|---|---|
| 분할 정복에 관한 메모 (0) | 2023.05.27 |