python functools cache

@cache 사용 조건

import sys
from functools import cache

input = sys.stdin.readline


@cache
def solution2(s: list, words: list):
    global res

    if len(s) == 0:
        res = 1
        return

    for i in range(len(s)):
        partition = ''.join(s[i:])
        print(f'partition: {partition}, words = {words}')
        if partition in words:
            words.remove(partition)
            solution2(s[:i], words)
            words.append(partition)


# input
s = input().rstrip()
n = int(input())
words = []
for _ in range(n):
    words.append(input().rstrip())

res = 0
solution2(list(s), words)
print(res)

Traceback (most recent call last):
File "/Users/nekote42/Desktop/swjungle/baekjoon/week03/16500-문자열 판별.py", line 48, in <module>
solution2(tuple(s), words)
TypeError: unhashable type: 'list'

다음과 같이 오류가 발생한다.

인자로 사용된 list 타입의 변수는 unhashable 하기 때문인데 unhashable한 이유는 다음과 같다.

python의 list는 1. 내용이 변경될 수 있고 2. 순서가 중요한 데이터 타입이다.

해시화를 진행하면 set() 이나 dict() 같이 순서가 뒤바뀔 수 있고, 애초에 변경 가능한 값은 해시가 불가능 하기 때문에 애초에 파이썬은 list를 hash하려는 시도 자체를 막는것이다.

hashable한 기준은 무엇일까?

hash가 가능하려는 조건은 불변성(Immutable)이다. 데이터의 값 또는 객체가 변하지 않는다는 것을 의미한다.

hash function의 결과로 나타나는 값(hash)은 고유의 값이며 원래의 값을 참조할 때 사용된다.

같은 값 혹은 객체 A, B를 hash로 변경하여 Hash_A, Hash_B로 저장했다고 해보자. A라는 값이 변경된다면 A를 찾을 때 사용되는 Hash_A의 값은 무용지물이 된다.

게다가 A와 B를 비교하기 위해 hash_A와 hash_B 를 사용하면 실제 값은 다르지만 둘의 값은 같다고 잘못판단할 수도 있다.

이 때문에 변경 불가능한 상수, dict, tuple 같은 값만 해시가 가능하고 list는 불가능하다.