728x90 반응형 Dynamic Programming11 [백준/Python] 1003 피보나치 함수 문제: https://www.acmicpc.net/problem/1003 사용 알고리즘: DP - dp 배열 초기화 0 과 1 이 출력되는 횟수를 함께 구해줘야 하기 때문에 dp 배열을 2차원 배열로 만들고, N 의 최대 값이 40 이기 때문에 배열의 크기를 41로 만들었다. dp 값은 n 번째 피보나치 수를 계산할 때 0, 1 이 출력된 수이다.dp = [[0, 0] for _ in range(41)] # [0이 출력된 수, 1이 출력된 수]dp[0] = [1, 0]dp[1] = [0, 1] - 0 과 1 이 출력되는 횟수 구하기 입력받은 테스트케이스 수만큼 for 문을 돌면서 계산 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) 이므로dp[n] = dp[n.. 2024. 7. 14. [백준/Python] 9184 신나는 함수 실행 문제: https://www.acmicpc.net/problem/9184 사용 알고리즘: 재귀, DP 사실 문제를 처음 읽고 어엉? 했지만 다시 보니 주어진 코드를 거의 그대로 사용해서 풀 수 있는 문제였다. 문제에서 주어진 코드는 재귀만을 사용해서 w(a, b, c) 를 구하기 때문에 시간이 너무 오래걸린다. 시간을 단축하기 위해 DP 를 사용해서 전에 계산했던 값을 가져다 쓰면서 시간을 줄였다. - dp 배열 초기화 문제에 주어진 코드를 읽어보면 a, b, c 중 한개라도 20 을 초과하는 값이 있다면 w(20, 20, 20) 로 통일해 버린다. 그래서 n 값은 최대 50 까지 가능하지만, dp 배열은 51 까지 만들 필요없이 21 까지만 만들면 된다. dp = [[[0 for _ in ran.. 2024. 7. 14. [백준/Python] 11660 구간 합 구하기 5 문제: https://www.acmicpc.net/problem/11660 사용 알고리즘: DP, 누적합 입력받기import sysinput = sys.stdin.readlineN, M = map(int, input().split())arr = [[0] * (N+1)]for i in range(N): arr.append([0] + list(map(int, input().split()))) 위와 같은 모양으로 사용하기 위해 배열의 0 번째 열과 행을 모두 0 으로 초기화 시켰다. ( 배열의 0 번째 열과 행을 0으로 초기화 시켜놓지 않으면 dp 값을 채울 때 인덱스 에러가 난다 ) dp 값 채우기 dp 의 값은 (i,j) 의 총 누적합이다. 인덱스 1 부터 사용하기 위해 (N+1)*(N+1) .. 2024. 7. 13. [백준/Python] 9461 파도반 수열 문제: https://www.acmicpc.net/problem/9461 사용 알고리즘: DP 입력첫째 줄에 테스트 케이스의 개수 TN (1 ≤ N ≤ 100) 첫 삼각형은 정삼각형으로 변의 길이는 1다음과 같은 과정으로 정삼각형을 계속해서 추가할 때 나선에서 가장 긴 변의 길이 찾기 이 문제는 그림을 보고 규칙을 찾아서 쉽게 풀 수 있었다. P(1) = 1P(2) = 1P(3) = 1P(4) = 2P(5) = 2P(6) = P(5) + P(1)P(7) = P(6) + P(2)P(8) = P(7) + P(3)P(9) = P(8) + P(4)P(10) = P(9) + P(5) 점화식을 써보면-> P(n) = P(n-1) + P(n-5) 인덱스 1부터 사용할거라 0번 인덱스에는 0을, 1~5번 인덱.. 2024. 7. 11. 이전 1 2 3 다음 728x90 반응형
