Memoization 백준 피보나치2&3

후... 피보나치3를 3시간 넘게 푼 듯..

우선 list로 메모이제이션 구현해서 풀려고 했다.
근데 리스트의 인덱스가 994를 넘어가면 메모리가 초과되는 한계를 갖고 있었다.

따라서 그러면 내가 필요한 만큼 만들어 쓸 수 있는 SingleLinkedList를 만들어서 풀려고 했다. 그래서 input 1000넣었을 때 아주 만족스러운 속도로 되길래 제출했는데 메모리 초과가 뜸...ㅠㅠ

햐... 그래서 공간복잡도를 줄이기 위해 생각을 해보니까 CircularList로 node 3개만 있어도 메모이제이션을 구현할 수 있을 것 같길래 위에 것 주석처리하고 CircularList를 구현해서 제출함. input 1000에 대해서 역시나 만족스러운 속도를 보여줌.

근데... 이번엔 시간초과 에러가 뜸.. 뭐지 싶어서 보니까 input 1000000000000000일 때 시간이 어마어마하게 걸리는 것이었다. 왜 이걸 검사 안 했지 싶었는데.. 정답률 낮아진 거 보니까 마음이 아팠음.. ㅠㅠ
하여튼 그래서 이건 내가 모르는 개념이다 싶어서 구글링 해보니까 피사노 주기라는 게 있음... ㅋㅋㅋ 진짜 별 게 다 있네.

n = int(input())


class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None


class CLinkList:
    def __init__(self):
        self.head = None
        self.size = 0

    # def insert(self, prev_node, data):
    #     node = Node(data)
    #     self.size += 1
    #
    #     if prev_node:
    #         node.next = prev_node.next
    #         prev_node.next = node
    #     else:
    #         node.next = self.head
    #         self.head = node
    #
    def insert(self, data, prev_node):
        node = Node(data)
        self.size += 1

        if prev_node:
            node.next = prev_node.next
            prev_node.next = node
        else:
            self.head = node
            node.next = node


def fibonacci(n):
    SLL = CLinkList()
    SLL.insert(0, None)
    cur = SLL.head
    SLL.insert(1, cur)
    cur = cur.next
    SLL.insert(1, cur)
    cur = cur.next

    for i in range(1, n+1):
        data = cur.data + cur.next.data
        cur = cur.next
        cur.next.data = data

    return cur.next.data % 1000000


print(fibonacci(n))

아마 피보나치2 문제에 대해서 가장 최적화된 코드라고 생각이 됨.
피보나치3 은 피사노 주기로 풀면 되는데 풀이까지 봐버려서 내 코드라고 말할 수가 없네. 게다가 피사노 주기에 대해서 공부도 해야한다. 왜 그렇게 도출된 건지를 본 게 아니라 그냥 이 때 주기가 이렇게 된다고만 봤기 때문에..