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

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

문제 https://www.acmicpc.net/problem/10942 팰린드롬이란 반으로 나누어 좌우가 같은 것이다.짝수개일때는 반으로나누어 같은경우 홀수개일때는 중앙값을 기준으로 좌우가 같은것이다.2 2, 4 4 4 4 , 1 ,1 2 1 같은경우 모두 팰린드롬이다.테스트 케이스마다 모두 계산한다면 O(N^2)*M 번이 걸릴것이다.dp를 이용해 모든 경우를 구한뒤 출력만 해주는 방식으로 구현해보자.방법은 먼저 한자리 일때를 모두 1로 초기화 시켜주고 2자리 일때도 각각 구해주었다.그뒤 하나씩 늘려가며 이전값들이 팬린드롬이면서 양끝값을 비교하여 같으면 팬린드롬이고 이를 저장하여 다시 이용한다.작은 예를 들어보자num=[1,2,3,2,1] 이라는 배열이 주어졌을때 4*4의 dp를 만들어주고 초기화시킨다..

2020. 2. 9. 21:40
알고리즘(python)/기본

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

문제https://www.acmicpc.net/problem/7579 냅색 문제이다. 이전에 가방안에 넣을수 있는 무게가 정해져있을때 가장큰 가치를 만들수 있는 경우를 찾아내는 문제로 한번 접해봤다.그때와 같은 방식으로 짜보고 이전 문제는 가방의 무게가 넘치면 안됬었는데 이번에는 메모리가 초과했을때도 시간만 작다면 채택할수있게 만들어보자. 123456789101112131415161718192021import sys N,M=map(int,sys.stdin.readline().split())#앱m=list(map(int,sys.stdin.readline().split()))#메모리c=list(map(int,sys.stdin.readline().split()))#비활성화 비용result=[10001]*(M+..

2020. 2. 8. 21:39
알고리즘(python)/기본

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

문제 https://www.acmicpc.net/problem/1520 처음 코드를 짤때 너무 간단하게 생각했다.내리막길로만 갈 수 있다는걸 아래쪽으로만 이동할수 있는걸로 코드를 작성했고 당연히 실패했다.위로 올라갔다가 내려올수도 있다는걸 생각하지못했다. 12345678910111213141516171819202122232425262728293031323334import sys N,M=map(int,sys.stdin.readline().split()) map=[list(map(int,sys.stdin.readline().split())) for _ in range(N)] result=[[0 for _ in range(M)] for _ in range(N)]result[0][0]=1 for i in ran..

2020. 2. 7. 01:30
알고리즘(python)/기본

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

문제 https://www.acmicpc.net/problem/11049 이전문제를 풀었더면 어렵지 않게 풀수있다.n~m까지의 최소연산을 dp[n][m] 이라고 표현햇을때dp[0][m] 까지의 최소연산은dp[0][0]+dp[1][m]+두 행렬을 곱하는 비용dp[0][1]+dp[2][m]+두 행렬을 곱하는 비용......dp[0][m-1]+dp[m][m]+두 행렬을 곱하는 비용중 하나일것이다. 코드를 짜보자 123456789101112131415161718import sys N=int(input()) matrix=[list(map(int,sys.stdin.readline().split())) for _ in range(N)] dp=[[0]*N for _ in range(N)] for x in range(1..

2020. 2. 6. 16:57
알고리즘(python)/기본

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

문제 https://www.acmicpc.net/problem/11066 n~m까지의 최소합을 dp[n][m] 이라고 표현햇을때dp[0][m] 까지의 최소합은dp[0][0]+dp[1][m]dp[0][1]+dp[2][m]......dp[0][m-1]+dp[m][m]중 하나일것이다. 코드를 짜보자 123456789101112131415161718192021222324import sys n=int(input()) while n>0: n-=1 K=int(input()) file_list=list(map(int,sys.stdin.readline().split())) dp=[[0 for _ in range(K)] for _ in range(K)] sum=[0]*(K+1)#첫번째부터 K번짹 까지의 파일크기합 한번 합..

2020. 2. 5. 00:49
알고리즘(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