알고리즘(python)/기본 검색 결과
50 개의 검색 결과가 있습니다.
알고리즘(python)/기본

[Python]동적계획법2 백준 2293

문제 https://www.acmicpc.net/problem/2293 다시 DP문제이다.메모리 제한이 있긴하지만 크게 문제되지 않을거같다.동전의 가치가 10만까지라면 0.4MB 정도 소모될것이다.방법은 간단하다. 동전의 가치만큼의 크기를 가진 배열을 만들고 각 동전마다 만들수 있는 가치를 구해준다.각 코인마다 이전에 만들수 있던 가치를 받아와서 더해준다.설명보다는 코드를 보고 조금만 생각해보면 이해할수 있을것이다. 12345678910111213141516import sys input=sys.stdin.readlinen,k=map(int,input().split())coin_list=[]for i in range(n): coin_list.append(int(input())) result=[0 for _..

2020. 2. 4. 10:18
알고리즘(python)/기본

[Python]분할정복 백준 2749

문제 https://www.acmicpc.net/problem/2749 n의 크기가 무지막지하다.주어진 n의 크기는 0의 숫자 조차 세기 힘들다.메모이제이션은 O(n)이라는 시간이 걸린다. 보통의 풀이방식으로는 불가능하다피보나치 수열을 분할정복으로 풀 수 있는 방법이 있다는건데 찾아봐야겟다...https://www.acmicpc.net/blog/view/28https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9..

2020. 1. 29. 22:48
알고리즘(python)/기본

[Python]분할정복 백준 10830

문제 https://www.acmicpc.net/problem/10830 분할정복으로 제곱을 구현했던것과 같다.(A)^8을 계산하는데 8번(N번) 계산해야한다면(A^2)^2)^2로 구할시 3번(logN번)만에 계산할수있다. 1234567891011121314151617181920212223242526272829303132333435363738import sysN,B=map(int,sys.stdin.readline().split())A=[list(map(int,sys.stdin.readline().split())) for _ in range(N)] def matric_mul(A,B): if B==1: for i in range(N): for j in range(N): A[i][j]%=1000 return ..

2020. 1. 29. 00:34
알고리즘(python)/기본

[Python]분할정복 백준 2740

문제 https://www.acmicpc.net/problem/2740 행렬의 곱셈을 구현하는 문제이다.행렬의 인덱스를 그려놓고 구현하는게 헷갈리지 않을것이다.행렬의 곱셈을 모른다면 https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88를 참고하여 구현하면 될것이다. 1234567891011121314151617181920212223242526import sysN,M=map(int,sys.stdin.readline().split())A=[list(map(int,sys.stdin.readline().split())) for _ in range(N)] Nb,Mb=map(int,sys.stdin.readline().split())B=[list(..

2020. 1. 28. 18:57
알고리즘(python)/기본

[Python]분할정복 백준 1629

문제 https://www.acmicpc.net/problem/1629 제곱의 계산을 분할정복을 통해 해결하는 문제이다. 1234567891011121314151617#a=nc+r이라고 생각햇을때#a^2=(nc)^2+2(nc)r+r^2#a^2를 c로 나눈것의 나머지는 r^2%cdef squared(a,b): if b==0: return 1 elif b==1: return a elif b%2==1: return squared(a,b-1)*a half=squared(a,b//2) half%=c return half**2%c a,b,c=map(int,input().split())print(squared(a,b)%c)cs

2020. 1. 26. 23:07
알고리즘(python)/기본

[Python]분할정복 백준 1780

문제 https://www.acmicpc.net/problem/1780 앞의 색종이 문제와 동일하게 풀어냈다.코드를 짜는데 있어서 달라진점은 등분을 나누기 위해 for문을 사용하였다. 이후 3등분이 아니라 5등분 10등분이여도 같이 적용할수있도록... 123456789101112131415161718192021222324252627282930313233343536373839import sys n=int(sys.stdin.readline()) #-1 0 1paper=[list(map(int,sys.stdin.readline().split())) for _ in range(n)] result=0#-1result0=0#0result1=0#1 def cut(x,y,n): global result,result0,..

2020. 1. 24. 20:45