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

[Python]동적계획법 백준 1003

문제 https://www.acmicpc.net/problem/1003 앞 문제와 형식만 조금 다를뿐 같은 문제라고 봐도 될거같다.이 문제의 의도는 재귀를 사용했을때 얼마나 많이 함수를 불러와야 하는지를 보여주기위해 낸 문제인거가 같다.풀이는 전과 비슷하다 123456789101112131415t=int(input()) fibo_list=[[0 for _ in range(2)] for _ in range(41)] fibo_list[0]=[1,0]fibo_list[1]=[0,1]for i in range(2,41): fibo_list[i][0]=fibo_list[i-1][0]+fibo_list[i-2][0] fibo_list[i][1]=fibo_list[i-1][1]+fibo_list[i-2][1] for..

2020. 1. 7. 22:28
알고리즘(python)/기본

[Python]동적계획법 백준 2748

문제 https://www.acmicpc.net/problem/2748 이전 피보나치 수열은 재귀를 활용해 푼것으로 기억이난다. 이번에는 동적계획법(Dynamic Programming)을 활용한 방법이다.동적계획법은 특정 범위 까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법이다.https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95밑에 보면 재귀를 이용한 방법과 동적계획법을 이용했을때의 연산 횟수도 나와있다.코드는 매우간단하다.123456789101112131415t=int(input()) fibo_list=[[0 for _ in range(2)] for _ in range(41)..

2020. 1. 7. 19:45
알고리즘(python)/탐색

[Python]백트래킹 백준 14889

문제 https://www.acmicpc.net/problem/14889 역시나 기본에 충실한 문제인거같다.두팀으로 나누는 경우에 수를 모두 구해 각 경우마다 팀의 능력치를 구해서 가장 작은 차를 출력하면 된다.처음 작성한 코드는 조금 느려서 처음엔 시간초과가 떴다.123456789101112131415161718192021222324252627282930313233343536373839404142import sys n=int(sys.stdin.readline()) startlink=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]team=[0 for _ in range(n)] #0은 result=9999999999999#팀을 나누는 경우의..

2020. 1. 7. 17:06
알고리즘(python)/탐색

[Python]백트래킹 백준 2580

문제 https://www.acmicpc.net/problem/2580 나에게는 매우 친숙한 퍼즐이다.중학교 시절 신문에 나오던 스도쿠 문제를 풀던 기억이 난다. 풀이방식은 앞에 문제들과 비슷할거같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import sys sdk = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]zeros = [(i, j) for i in range(9) for j in range(9) if sdk[i][j] == 0] def sudoku(index): # 한 바퀴에서 모든 경우를 다 보았으..

2020. 1. 6. 17:24
알고리즘(python)/탐색

[Python]백트래킹 백준 9663

문제 https://www.acmicpc.net/problem/9663 백트래킹을 이용한 문제의 기본이라고 한다.가장 먼저 떠오르는 방법은 퀸의 자리를 하나 잡고 한줄씩 내려가면서 위와 대각선을 확인하여 퀸이 없다면 자리를 확정하며마지막줄까지 퀸의 자리를 확정짓는다면 수를 1씩늘리는 방법이다.굉장히 코드가 지저분하고 느리다. 시간초과가 뜬다. pypy3으로 제출하면 성공하기는 한다.함수의 사용을 통해 조금은 정리해보고 색다른 방법을 통한 코드도 올려볼려고한다. 함수를 통해 넘어가는 경로에 퀸이 있을때 다음칸으로 넘어가는 부분을 깔끔하게 정리했다.마지막 방법은 아래 사이트를 참조하였다.https://rebas.kr/761 정말 똑똑한 사람들은 많은것같다....12345678910111213141516171..

2020. 1. 6. 00:34
알고리즘(python)/탐색

[Python]백트래킹 백준 15652

문제 https://www.acmicpc.net/problem/15652 N과M마지막 문제이다.비내림 차순이란 오름차순이거나 같은수의 연속이 나와도 된다는것을뜻한다.말그대로 내림차순인 부분만 없으면 된다는 것이다.이번에도 조건을 조금만 바꾸어주면 된다. 12345678910111213141516171819202122232425n,m=map(int,input().split()) check=[0 for i in range(n+1)]result=[0 for i in range(m)] def backTracking(index,n,m): if index==m: for i in result: print(i,end=" ") print() return for i in range(1,n+1): if check[i]==1..

2020. 1. 4. 16:16