[코딩테스트 입문]Day25 - 등차수열, 등비수열 이용
연속된 수의 합
문제 설명
연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요.
제한사항
- 1 ≤
num≤ 100 - 0 ≤
total≤ 1000 num개의 연속된 수를 더하여total이 될 수 없는 테스트 케이스는 없습니다.
입출력 예
| num | total | result |
|---|---|---|
| 3 | 12 | [3, 4, 5] |
| 5 | 15 | [1, 2, 3, 4, 5] |
| 4 | 14 | [2, 3, 4, 5] |
| 5 | 5 | [-1, 0, 1, 2, 3] |
문제 풀이
def solution(num, total):
n = total
while num != 0:
s = 0
ss = []
for i in range(num):
s += n-i
ss.append(n-i)
if s == total:
return sorted(ss)
n -= 1
테스트 케이스 9 실패(시간 초과)…좀 더 시간을 줄여야하는데 어떻게 해야할까요.
찾아보니 total = 0인 경우는 보통 0을 중심으로 양 옆의 수가 저장되는 경우만 존재합니다.
위에 작성한 코드는 오직 빼는 경우만 주어져서 total로 주어진 0에서 빼면서 시간 오류가 나는 것 입니다.
그래서 따로 total이 0인 경우를 적어주었습니다.
for문에서 range가 0이면 아무것도 출력되지 않습니다.
def solution(num, total):
n = total
if total == 0:
if num == 1:
return [0]
else:
nn = [0]
for j in range(1, (num+1)//2):
nn.append(j)
nn.append(-j)
return sorted(nn)
while num != 0:
s = 0
ss = []
for i in range(num):
s += n-i
ss.append(n-i)
if s == total:
return sorted(ss)
n -= 1
다른 풀이
def solution(num, total):
return [(total - (num * (num - 1) // 2)) // num + i for i in range(num)]
def solution(num, total):
answer = []
var = sum(range(num+1))
diff = total - var
start_num = diff//num
answer = [i+1+start_num for i in range(num)]
return answer
def solution(num, total):
if num % 2 == 1:
return list(range(total//num-num//2, total//num+num//2+1))
else:
return list(range(total//num-num//2+1, total//num+num//2+1))
첫번째 소스코드가 엄청 단순하면서 좋아서 아래 적힌 설명을 읽어가며 이해해봤습니다.
우선 결과를 일반화하는 과정이 필요합니다.
$result = [x+0, x+1, x+2, …, x+(num-1)]$
result의 전체 요소의 갯수는 num개 이므로 x의 갯수는 num개이고 상수 부분은 첫번째 항이 0이고 마지막 항이 num-1인 등차가 1인 등차수열의 합입니다.
등차수열이란 무엇일까??
이웃하는 두 항의 차의 크기가 일정한 수열을 말합니다.
등차수열의 합은 첫 항과 마지막 항을 더한 뒤 항의 개수를 곱하고 2로 나눈 값입니다.
근데 우리는 첫 항도 모르고 마지막 항도 모릅니다.
그러면 식을 한 번 정리해보겠습니다.
우선 예시 num = 3, total = 0라면,
연속한 수가 기본이니까 공차는 1입니다. num=3이니 $a_0+a_1+a_2$이렇게 세가지의 합이 total이 됩니다.
우리는 공차를 알고 있으니 다시 정의 해보자면,
$a_0+a_1+a_2 = a_0+(a_0+(d*1))+(a_0+(d*2))$입니다.
즉, $3a_0+3 = 3(a_0+1)=0$입니다. $a_0+1 = 0$이고 첫 항인 $a_0 = -1$입니다.
첫 항을 구했으니 num의 개수만큼 +1해서 출력해주면 됩니다.
def solution(num, total):
a0 = (total - sum([i for i in range(num)]))//num
return [a0+i for i in range(num)]
-------------------------------------
>>
def solution(num, total):
return [(total - sum([i for i in range(num)]))//num+i for i in range(num)]
다음에 올 숫자
문제 설명
등차수열 혹은 등비수열 common이 매개변수로 주어질 때, 마지막 원소 다음으로 올 숫자를 return 하도록 solution 함수를 완성해보세요.
제한사항
- 2 <
common의 길이 < 1,000 - -1,000 <
common의 원소 < 2,000common의 원소는 모두 정수입니다.
- 등차수열 혹은 등비수열이 아닌 경우는 없습니다.
- 등비수열인 경우 공비는 0이 아닌 정수입니다.
입출력 예
| common | result |
|---|---|
| [1, 2, 3, 4] | 5 |
| [2, 4, 8] | 16 |
생각해보기
등비수열이란?
등비수열에서 연속되는 두 항의 비는 항상 같습니다. 등차 수열에서는 연속되는 두 항의 차가 같았고 이를 공차라고 불렀습니다.
1, 2, 4, 8, 16, ...
위와 같은 수열의 공비는 2입니다.
등비수열의 식 a(n)은 n번째 항의 값을 뜻합니다.
-
일반항
등비수열의 일반항을 보겠습니다.
첫쨰항: k
공비: r
=> 일반항: $
a(n) = k*r^n-1$이 수열의 점화식을 보겠습니다.
a(1) = k
$a(n) = a(n-1)*r$
-
등비수열의 합:
첫쨰항이 k, 공비가 r인 등비수열의 첫째항부터 제 n항까지의 합은 두 가지 조건에서 나뉩니다.
- $r != 1$
$S_n =$ $\frac{a(r^ -1)} {r - 1}$ = $\frac{a(1 - r^n)}{1 - r}$
- r = 1
$S_n = na$
이렇게 등비수열을 알아봤습니다. 이제 문제에 적용해 보겠습니다.
우선 주어진 수열이 등비수열인지 등차수열인지 구분해야합니다.
그리고 제일 마지막 요소에 공차 혹은 공비를 적용해서 마지막을 구합니다.
풀어 보기
def solution(common):
if common[1] - common[0] == common[2] - common[1]:
w = common[1] - common[0]
return common[-1] + w
else:
w = common[1]//common[0]
return common[-1] * w
처음엔 조건문을 통해서 정렬된 리스트에서 인덱스 값을 저장하고 다음인덱스 값을 뺀 값을 저장하고 또 for문이 다 돌고 그 저장한 값들이 같으면 공차고 아니면 공비수열이다. 라고 길게 쓰다가 조건문에 요소는 3개 이상라고 되어있는 것을 보고 다시 작성 했습니다.
복잡하게 공차수열과 공비수열을 구하지 않고 조건문하나를 작성해주고 바로 리턴하도록 말입니다.
다른 풀이
def solution(common):
answer = 0
a,b,c = common[:3]
if (b-a) == (c-b):
return common[-1]+(b-a)
else:
return common[-1] * (b//a)
return answer
0~2까지 값을 각각 a, b, c에 저장하고 그 값을 비교해서 작성한 코드입니다.
댓글남기기