백준 9375 파이썬 탐구

현재 머신러닝 프로젝트가 한창이다 대강의 모델링은 끝났고 최고의 결과물을 향해 개선중이다

프로젝트가 진행될수록 뭐랄까 점점 자신감이 붙는기분이다

어려움을 만나고 어떻게든 극복해나가면서 작은 성공을 여러번 반복해왔기때문이다

 

개발자의 삶은 수많은 실패와 수많은 성공의 반복 끊임없는 도전인것같다

 

다만 하나 수정할때마다 코드를 다시 실행하다보면 제대로 제보진 않았지만 3~5분정도가 걸린다

가장 빠른 모델을 사용해서 이정도지 이상한거쓰면 메모리다쓰고 다운되거나(대부분의 경우) 프로그램이 팅기거나

30분정도 걸린다 애초에 행수가 많긴하다 400만개정도 된다

 

현재는 캐글리더보드 기준 상위 10퍼센트를 목표로 하고있다

 

그래서 이번에 머신러닝중간에 기다리는시간이 좀 아까워서 백준을 풀었는데  쉽게 풀리지않았고

잠깐 짬내서 백준을 푸는 본래의 목적을 잊고 몇시간 머리아파하다가 결국 답을보았다

 

그동안 알고리즘을 소홀히했던것같다 뇌주름이 펴지고있었나보다

사실 머신러닝은 노가다니까... 머리를 쓸필요가 없지

 

옷종류별 개수를 리스트로 환산했을때

예를들어 

머리장식:2

바지:3

일때 [2,3]으로 저장된다

 

옷을입을수있는 총 경우의수는 리스트에서 나올수있는 전체 조합의 조합의곱을 모두 더한것 이라는사실을 발견했다

간단히 예를들어

머리:3

바지:2

신발:1

이면 [1,2,3]으로저장

 

나올수있는 모든 조합은

[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]

 

조합안의 수끼리 곱한다

1, 2, 3, 2, 3, 6, 6

 

이것들을 다 더하면 답이다

23

 

전에 개미전사를 풀면서 조합을 구하는 코드에대해 이해했었기때문에 

재귀를 이용한 조합을구하는 코드를 그대로 따왔다

 

아래는 내가 제출한답이다

def 조합(thelist,num):
    chosen=[]
    if len(thelist)<num:
        return
    elif num == 1: # 재귀끝
        for i in thelist:
            chosen.append([i])
        return chosen
    elif num > 1: # 재귀 구현
        for i in range(len(thelist)-(num-1)):
            for j in 조합(thelist[i+1:],num-1):
                chosen.append([thelist[i]]+j)
        return chosen

def 모든조합(thelist):
    output=[]
    for i in range(1, len(thelist)+1):
        for j in 조합(thelist,i):
            output.append(j)
    return output

def multiply(thelist):
    a=1
    for i in thelist:
        a=a*i
    return a

# 패션왕 신해빈

for i in range(int(input())):
    dicta={}
    for j in range(int(input())):
        A, B=input().split()
        try:
            dicta[B]+=1
        except:
            dicta[B]=1

    ans=0
    for i in 모든조합(list(dicta.values())):
        ans=ans+multiply(i)
    print(ans)

그나저나 한글로 함수명만들면 왜 색깔표시안해주는걸까

난 한글로 쓰는게 좋다 고쳐줬으면 좋겠다

 

결과는 메모리 오류가 났다 50퍼센트정도에서 튕겼다

사실 나는 시간초과를 예상했는데 메모리 초과라니

 

재귀함수가 문젠가 싶어 파이썬 내장함수 combinations도 이용해봤지만 똑같이 메모리초과

조합으로 푸는게 문젠가? 라는 생각이 들었지만

아무리 생각해봐도 조합을 이용하지않고 푸는 방법이 떠오르지 않았다

 

여기서 답을 보게됨

[백준] 9375 패션왕 신해빈 (Python 파이썬) :: AndroidTeacher (tistory.com)

 

해답은 정말 간단했다

옷의 종류 a,b,c가 있다고할때 옷을입는 경우의수는 ((a+1)* (b+1) * (c+1))-1

옷을 안입는 경우를 더해서 경우의수를 계산한게 천재적인것같다

 

풀이방법을 이해하고 코드를 구현해보는데는 오랜시간이 걸리지않았다

for i in range(int(input())):
    dicta={}
    for j in range(int(input())):
        A, B=input().split()
        try:
            dicta[B]+=1
        except:
            dicta[B]=1
    ans=1
    for i in dicta:
        ans=(dicta[i]+1) * ans
    print(ans-1)

 

여기서 궁금해진건 그렇다면 옷의 종류가 30개일때 조합의수는 몇개이길래 메모리 초과가 떳던것일까?

뭔가 천재적인 수학적 계산법이 있을것같았지만 코드로 구현해 알아보았다

def 팩토리얼(num):
    ans=1
    for i in range(1,num+1):
        ans=ans*i
    return ans

def 조합수(num,pick):
    return factorial(num)//(factorial(num-pick) * factorial(pick))

def 모든조합수(num):
    ans=0
    for i in range(1,num+1):
        ans+=조합수(num,i)
    return ans

모든조합수(30)

결과는 코드를 복붙해서 확인해보기 바란다

메모리초과될만하네...