피보나치를 배열 없이 쓰는 형태는 익숙하다.
n = 10
a, b = 0, 1
for i in range(n + 1):
print(a, end=' ')
a, b = b, a + b
a 와 b 가 한 칸씩 밀린다. 오른쪽이 먼저 다 계산되고 나서 왼쪽에 한꺼번에 들어가므로 임시 변수가 필요 없다.
배열에 쌓는 형태와 비교하면 차이가 분명하다.
li = [0, 1]
for i in range(2, n + 1):
li.append(li[i - 1] + li[i - 2])
이쪽은 지나간 값을 전부 들고 있다. 중간 값을 나중에 꺼내 쓸 게 아니라면 남길 이유가 없다.
세 칸으로 늘리기
한 번에 최대 3칸까지 오를 수 있는 계단 문제는 앞의 세 개를 더한다. 변수를 하나 더 두면 그대로 옮겨진다.
stair, power = 10, 3
a, b, c = 1, 1, 2
for i in range(stair + 1):
print(a, end=' ')
a, b, c = b, c, a + b + c
a, b, c 가 0칸, 1칸, 2칸을 오르는 방법의 수다. 0칸은 아무것도 안 하는 한 가지, 1칸은 한 가지, 2칸은 1+1과 2로 두 가지다.
한 번 굴릴 때마다 셋이 한 칸씩 밀리고 새 값이 뒤에 들어온다. 배열을 안 쓰므로 stair 가 아무리 커져도 변수는 세 개다.
같은 걸 재귀로도 썼다.
def climbing(n, a, b, c):
if n == 0:
return a
print(a, end=' ')
return climbing(n - 1, b, c, a + b + c)
인자를 밀어서 다시 부른다. 반복문의 a, b, c = b, c, a+b+c 와 하는 일이 같다. 돌아오면서 하는 일이 없어서 반복문으로 바꿔도 그대로다.
배열 버전과 비교
같은 문제를 배열로 쓰면 이렇게 된다.
stair, power = 10, 3
li = [1]
for i in range(1, stair + 1):
p = max(i - power, 0)
li.append(sum(li[p:i]))
power 가 3으로 고정이 아니라 값으로 들어온다는 게 다르다. 변수 세 개짜리는 power 를 바꾸려면 변수 개수와 대입문을 손으로 고쳐야 한다.
power 가 정해져 있고 개수만 세면 되면 변수 쪽이 짧고, power 가 바뀌거나 중간 값이 필요하면 배열 쪽이 낫다.