스칼렛의 코딩라이프

이제 좀 동적계획법이 뭔지 익숙해 진 것 같다. 점화식을 알아내는게 동적계획법의 핵심인듯 처음 12개정도는 하나씩 보면서 규칙을 찾았다. 5번째부터는 바로 전 숫자와 5번째 전 숫자의 합이라는것을 알아내어 점화식을 썼고, 첫 5번째까지는 별다른 규칙이 없어서 임의로 입력해서 사용했다. def P(n): if n

거의 다 와서 헤맸다.. 계속 메모리 초과가 나와서 대체 왜!! 왜!!! 라고 했는데 15746으로 나눈 나머지를 출력하라고 한게 힌트였다! def get_cnt(n): dpN[1]=1 dpN[2]=2 for i in range(3,n+1): dpN[i]=(dpN[i-1]+dpN[i-2])%15746 return dpN[n] N=int(input()) dpN=[0]*(N+2) a=get_cnt(N) print(a) 나머지끼리 계속 더해도 그 값이 나오는구나.. 하긴 왜 굳이 15746으로 나누라고 한지는 잘 모르겠지만 어쨌든 done! 근데 함수 선언 안해도 비슷한데,,, 함수는 왜 쓰는걸까.. N=int(input()) dpN=[0]*(N+2) dpN[1]=1 dpN[2]=2 for i in range..

동적계획법,, 너무 어렵다,, 문제 자체에 점화식을 써 준것인지도 몰랐다. 아직 너무 아무것도 몰라서 결국 다른분 풀이를 보고 참고했다. def w(a,b,c): if a 20: return w(20, 20, 20) if dp[a][b][c]: return dp[a][b][c] if a < b < c : dp[a][b][c]=w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) return dp[a][b][c] dp[a][b][c]=w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) return dp[a][b][c] Max=21 dp=[[[0]*Max for _ in range(Max)] for _ in rang..

동적계획법.. 사실 동적계획법이 뭔지도 모르고 문제를 접했다. 열심히 구글링을 해서 대충 이해를 했다. def fibonacci(n): if n==0: calltime.append(0) return 0 elif n==1: calltime.append(1) return 1 else : return fibonacci(n-1)+fibonacci(n-2) N=int(input()) for i in range(N): calltime=[] a=int(input()) fibonacci(a) zerocnt=calltime.count(0) onecnt=calltime.count(1) print(zerocnt,onecnt) 처음에는 이렇게 문제 그대로 피보나치 함수를 쓴다음에 0이 호출되면 0을 리스트에 추가하는 식으로 ..

백트래킹 문제 너무 어렵다.. 사실 백트래킹 문제인데 계속 브루트포스로 풀게된다. 왜 이렇게 구현아이디어가 부족하지.. 이번에도 일단 브루트포스로 모든 쌍의 값을 구한다음에 차이를 하나씩 구하면서 차이가 만약에 0인경우 바로 출력될 수 있도록 구현했다. 나름 0인 경우에 바로 출력되고 for문을 탈출하니까 나름(??) 백트래킹이 아닐까.. def making_speclist(arr): for i in range(len(arr)): tempsum=0 temp=list(permutations(arr[i],2)) for j in temp: tempsum+=slist[j[0]-1][j[1]-1] arr[i]=tempsum return arr import sys from itertools import permut..

삼성 SW 역량 테스트 기출문제라고 해서 굉장히 겁을 먹었다. 역시 머릿속에 있는것을 구현하는게 쉽지않았는데, 일단 차근차근 했다. from itertools import permutations N=int(input()) numlist=list(map(int,input().split())) calcnt=list(map(int,input().split())) callist=[] for i in range(4): if calcnt[i]==0: continue else: for j in range(calcnt[i]): callist.append(i) calcombi=list(permutations(callist,len(callist))) def calchoice(a,tmp,elem): if a==0: retu..