# 1003

피보나치 함수라는 문제입니다. 해당 문제를 보았을 때, 메모이제이션을 활용하여 먼저 풀었고 재귀를 응용할 수 있는지 확인하며 진행하였습니다.

 

메모이제이션

"""
recursion(4) = recursion(3) + recursion(2)
-> recursion(4) = recursion(1) + recursion(0) + recursion(1) + recursion(1) + recursion(0) == 2 3
recursion(3) = recursion(2) + recursion(1)
-> recursion(3) = recursion(1) + recursion(0) + recursion(1) == 1 2
recursion(2) = recursion(1) + recursion(0)
recursion(1) = 1
recursion(0) = 0

0 - 1 0
1 - 0 1
2 - 1 1
3 - 1 2
4 - 2 3
5 - 3 5
6 - 5 8
결국 이거도 피보나치처럼 간다? 그러면 메모이제이션이나 재귀로 해결 가능해보임 -> 근데 문제의 최대 입력값은 40 (3억 회로 에러)
arr[i] = [arr[i - 2][0] + arr[i - 1][0], arr[i - 2][1] + arr[i - 1][1]]
"""

처음에 구상했던 주석입니다. 저는 재귀의 방식은 도저히 생각나지 않았지만 메모이제이션은 금방 생각나서 먼저 제 생각대로 풀이를 진행했습니다. 찾았던 규칙은 2번째 인덱스가 이루어지는 것은 0번째 인덱스의 0번째 값과 1번째 인덱스의 0번째 값, 0번째 인덱스의 1번째 값과 1번째 인덱스의 1번째 값으로 이루어진다는 것을 알게 되었습니다.

 

따라서 구했던 점화식은 arr[i] = [arr[i - 2][0] + arr[i - 1][0], arr[i - 2][1] + arr[i - 1][1]]입니다.

 

def memoization(n):
  arr = [[0, 0]] * (n + 1)
  arr[0] = [1, 0]

  if n == 0: return arr[0]
  arr[1] = [0, 1]

  for i in range(2, len(arr)):
    arr[i] = [arr[i - 2][0] + arr[i - 1][0], arr[i - 2][1] + arr[i - 1][1]]

  return arr[n]
  
T = int(input())

for _ in range(T):
  N = int(input())
  print(*memoization(N))

코드로 구현하면 다음과 같습니다. 후에 알았지만 배열의 생성은 올바르지 않은 방법입니다. 부가적으로 리턴값이 배열이기 때문에 언패킹을 통해 값을 도출하도록 조정하였습니다.

 

재귀로 가능한가?

재귀로 구현할 경우에는 문제에서 기재된 최댓수인 40을 놓고보면 약 3억 회의 연산을 진행해야되기에 단일 재귀로는 해결하기가 어렵습니다.

 

재귀함수 + 메모이제이션

그래서 재귀와 메모이제이션으로 처음 구현하려고 했으나 생각이 나질 않았고 다른 풀이를 보면서 또 다른 점화식을 찾을 수 있었는데 그를 통해 적용해보기로 하였습니다.

 

"""
0 - 1 0
1 - 0 1
2 - 1 1
3 - 1 2
4 - 2 3
5 - 3 5
6 - 5 8
i - (i - 1)[1], (i - 1)[0] + (i - 1)[1]
"""

두번째로 단 주석은 다음과 같은 규칙을 찾을 수 있었습니다. 2번째 인덱스의 0번째 인덱스는 1번째 인덱스의 1번째 인덱스, 1번째 인덱스는 1번째 인덱스의 0번째 인덱스와 1번째 인덱스의 합임을 알 수 있었습니다.

 

메모이제이션을 구현했으니 재귀로는 어떻게 이를 행하게 만들지 고민을 많이 하게 되었습니다. 일단, 배열을 하나 생성해주고 이는 [-1, -1]이라는 값으로 초기화하였습니다. base case는 배열에 입력된 인덱스 안의 값이 -1이 아니면 값이 입력되었다고 판단하여 그 값을 리턴하게 하는 것으로 두었습니다. recursive case는 이전 인덱스의 값을 꺼낼 수 있도록 하였습니다.

 

def recursion_memoization(n):
  global arr2

  if arr2[n][0] != -1: return arr2[n]

  index = recursion_memoization(n - 1)

  arr2[n][0] = index[1]
  arr2[n][1] = index[0] + index[1]

  return arr2[n]
 
T = int(input())
MAX = 40
arr2 = [[-1, -1]] * (MAX + 1) 
arr2[0] = [1, 0]
arr2[1] = [0, 1]

for _ in range(T):
  N = int(input())
  print(*recursion_memoization(N))

처음에 구현했던 방법은 다음과 같았으나 index의 부분이 모두 공통적이게 변한 것을 확인하였습니다. 이게 왜 이렇게 되었는지 몰랐는데 나중에 확인해보니 문제있는 녀석은 다음과 같았습니다.

 

arr2 = [[-1, -1]] * (MAX + 1)

메모이제이션을 담아둘 배열이 위와 같은 선언으로 인해 올바르지 않게 된 것이었습니다.

 

test = [[-1, -1]] * 40

print(id(test[0]))
print(id(test[1]))

4303982720
4303982720

그 이유를 찾으면 다음과 같습니다. 해당 선언은 같은 주소값을 가진 객체를 여러 개 만드는 방식으로 정확히는 * 연산자가 그렇게 만든 것입니다. 각각을 다른 객체로 보게 만들기 위해서는 선언부를 변경해야합니다.

 

def recursion_memoization(n):
  global arr2

  if arr2[n][0] != -1: return arr2[n]

  index = recursion_memoization(n - 1)

  arr2[n][0] = index[1]
  arr2[n][1] = index[0] + index[1]

  return arr2[n]
 

T = int(input())
MAX = 40
arr2 = [[-1, -1] for _ in range(MAX + 1)]
arr2[0] = [1, 0]
arr2[1] = [0, 1]

for _ in range(T):
  N = int(input())
  print(recursion_memoization(N))

다음과 같이 변경 후 정답처리 될 수 있었습니다.