백준 1010번 파이썬

머신러닝에 들어갔는데 너무어려워서 할맛이 안나서 좀 멘붕이 왔었다

애초에 문제도 어려운데 구현도 어렵고 

질문방에 진짜 잘 모르겠는거 질문해놓고 백준이나 풀기로했다

 

역시 백준은 재밌었다 내가 이해할수있으니까 

내가 이해할수 없다면 난 절대 즐길수없다 이해도 안되는 문제를 억지로 외우는건 정말 고통스럽다!

 

이번에 푼문제는 다리놓기이다

더 넓은 범위의 이항 계수를 동적 계획법으로 구하는 문제라고 문제 설명에 붙어있었다

동적계획법은 얼마전에 공부해서 어떤 개념인지 대충 알고있었다

 

그러나 이항계수는 위키를 보고 구하는 법만 알고있을뿐 왜 만들어졌는지 어떤상황에서 활용할수있는지 전혀 모른다

어쨋든 문제 풀이에 들어갔다

 

노트에 끄적거리면서 낙서를하다가 내가 저번에 풀었던 문제와 상당히 유사하다는 생각이들었다

아니 유사한게 아니고 거의 똑같다

 

바로 백준문제 2775번 부녀회장이 될테야이다

분명히 저번에 풀었는데 이친구가 과거에 어떻게 풀었는지 존경스럽다고 느껴질만큼

도저히 이것을 어떻게 동적계획법으로 구현해야할지 감이 안왔다

 

내가 푼답을 봤다 

dic = {}

def num(층,호):
    
    if 층 == 0:
        return 호
    if 호 == 1:
        return 1
    
    if (층,호) in dic:
        return dic[(층,호)]

    
    if (층,호) not in dic:
        output = num(층 - 1, 호) + num(층, 호 - 1)
        dic[(층,호)] = output
        return output

        
        
z = int(input())
for i in range(z):

    층 = int(input())
    호 = int(input())
    print(num(층, 호))

아...하....

이걸가지고 1010번을 풀었다

위에것도 사실상 동적계획법으로 푼것이라 놀랐다

난 동적계획법을 배우기도전에 이미 스스로 동적계획법으로 풀고있었던것이였다

# 호=M-N 층=N
dic = {}

def num(층,호):
    
    if 층 == 1:
        return 호+1
    if 호 == 0:
        return 1
    
    if (층,호) in dic:
        return dic[(층,호)]

    
    if (층,호) not in dic:
        dic[(층,호)] = num(층 - 1, 호) + num(층, 호 - 1)
        return dic[(층,호)]

for i in range(int(input())):
    N, M=map(int,input().split())
    print(num(N, M-N))

 

옛날에는  부녀회장문제를 혼자 생각해서 풀었지만

이번엔 못푼이유를 내가 너무 동적계획법으로 풀려고했기 때문이었다고 생각한다

열린사고로 다가가지못하고 

 

아 이걸 어떻게 2차원리스트로 구현하지..?

저번에 동적계획법으로 피보나치랑 개미전사 풀때는 1차원 리스트였는데

 

이런생각만 계속했다

 

공부를 위한 공부를 했지만 돌아오는건 닫힌 사고뿐이였다

 

앞으로는 그래서 너무 알고리즘이라는거에 너무 겁먹고 이방법아니면 못푸니까

이거일단 공부하고 시작하자 식의 행동은 그만하려고한다

 

한문제를 푸는 방법은 절대 한가지가 아니고

무엇보다 공부를 위한 공부는 굉장히 지루하기때문이다

 

나에게 맞는 공부법은 아무래도

일단 부딪힌다!! => 잘안된다!! => 공부한다!

인것같다