📒 Dictionary

immutable한 key와 mutable한 value로 맵핑되어있는 순서 없는 집합.
내부적으로는 해시 테이블로 구현되어 있다.
len(a), a[key], a[key]=value, key in a 의 시간 복잡도는 모두 O(1)이다.
Python3.7+ 에서는 입력 순서가 유지된다.

✏️ 오늘의 문제 : 의상

📌 의식의 흐름

Naive하게 접근한다. 제한사항에서 의상 수는 1개 이상 30개 이하이므로, [의상 이름, 의상 종류] 30개의 배열로는 어지간하면 시간 초과가 나기 힘들다고 판단했다.
의상의 종류가 뒤죽박죽 들어오기에, 의상 종류를 dictionary의 key값으로, 의상 이름들 리스트를 value 값으로 가지는 clothes_dict에 list의 값을 파싱한다.
new_dict에 clothes_dict의 key 값은 그대로, value는 의상 갯수로 갖도록 한다.
한번 의상을 정할때의 규칙은 다음과 같다
1. 같은 의상 종류에선 하나만 선택이 가능하다.
2. 하루에 최소 한개의 의상을 선택한다.
3. 착용 의상의 일부가 겹치더라도, 완벽히 똑같은 의상 조합이 아니라면 다른 의상으로 판단한다.
n개의 의상들이 있고 m개의 의상 종류, 각 의상 종류마다 k_i개의 의상이 있다면 총 조합할 수 있는 가짓수는 다음과 같다.
1. n개의 의상 종류중 i개의 종류를 고른다.
2. i개의 의상 종류들의 의상 갯수들을 모두 곱한다.
python itertools의 combination을 이용해 new_dict의 key들중 i개를 뽑아 해당 value값을 곱해 총합에 추가한다.
1번 테스트 케이스에서 시간 초과가 발생한다. worst case를 통과하지 못한다는 뜻인 것 같아 worst case를 찾아본다.
아래 코드에서 keylen * nCr * j 이고 combinations의 시간 복잡도가 θ[r (n choose r)] 이라고 하니, 생각보다 오래 걸릴 수도 있겠다는 생각이 든다. 정확한 시간 복잡도를 파악하는 방법은 잘 모르겠다.
점화식을 세워본다. 각 종류의 의상 갯수를 a,b,c라고 할때, 총 조합의 가짓수는 (a+b+c)+(ab+bc+ac)+(abc) 인데, 생각해보니 (1+a)*(1+b)*(1+c) -1 의 형태이다.

아래는 itertools.combination으로 naive하게 구현한 코드이다.

 cnt = 0
    keylen = len(new_dict.keys())
    for i in range(1,keylen+1):
        nCr = itertools.combinations(new_dict.keys(),i)
        for j in nCr:
            curcnt = 1
            for k in j:
                curcnt *= new_dict[k]
            cnt += curcnt

아래는 이항계수로 구현한 코드이다

ans = 1
    for i in new_dict.values():
        ans *= (i+1)
        
    return ans-1;

📌 문제점

itertools.combination을 사용하는 방법은 지양하는 것이 좋겠다. 정확한 시간 복잡도 파악이 힘들기 때문이다.

📌 해결방법

점화식을 세우는 습관을 들이자. 특히 조합과 같이 수학적인 지식이 들어가는 상황이라면 더더욱 점화식을 세우자.

📌 공부해야 할 것

ps시 itertools의 사용처에 대해

➕ itertools.combinations

itertools.combinations의 공식 문서를 살펴보자

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

stackoverflow의 설명을 참고하자면, 결과적으로 시간 복잡도는 θ[r (n choose r)] 이다.

n choose r은 generator가 yeild해야하는 횟수이면서 동시에 바깥 while의 반복횟수이다.

각 반복은 최소 길이 r의 tuple 이 생성되어야 하고, 동시에 시간 복잡도에 영향을 주는 추가 요소 r이 생성된다. 안쪽의 반복문은 각각 바깥 반복문마다 O(r)의 시간 복잡도가 추가로 생성된다.

(출처 : https://stackoverflow.com/questions/53419536/what-is-the-computational-complexity-of-itertools-combinations-in-python)

아까 나의 알고리즘에서는, keylen * θ[r (n choose r)] * (nCr값) * j 이기에 m(종류) * θ[r (n choose r)] * nCr갯수 * nCr 원소참조 이므로 정확하겐 잘 모르겠지만 삼중 포문, combinations의 2중 포문으로 시간 효율적인 알고리즘은 아니었다는 것을 알 수 있다.