DP
-
[백준 11727] 2×n 타일링 2Algorithm/Source Code 2021. 11. 23. 16:22
문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. solution.py n = int(input()) # dp dp = [0 for _ in range(1001)] dp[1] = 1 dp[2] = 3 for i in range(3, 1001): # 점화식 2*1 직사각형과 2*2 직사각형 방법 두가지 dp[i] = dp[i-1] + dp[i-2] * 2 print(dp[n] % 10007) https://www.acmicpc.net/pro..
-
[백준 11053] 가장 긴 증가하는 부분 수열Algorithm/Source Code 2021. 11. 21. 21:07
문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. solution.py import sys from collections import defaultdict n = int(sys.stdin.readline()) # n만큼 수열 nlist = list(..
-
Dynamic Programming (동적계획법)Algorithm/Source Code 2021. 11. 7. 18:16
DP ? " 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 " 이런 문제에 활용해요 ! 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다 최적성의 원리를 만족하는지 판단 최석성의 원리란 ? 주어진 문제의 부분해가 전체 문제의 해를 구하는데 사용되는지를 의미한다 피보나치 수열로 이해하기 DP 의 가장 좋은 예시인 피보나치 수열이 있다 F(n) 을 구할 때 트리를 보면 f(n-3) 연산식이 여러 번 사용되는데 상위 문제인 F(n) 을 구하기 위해서 여러 소문제들이 사용된다는 것을 알 수 있다 자주 사용되는 소문제들이 존재할 경우 자원의 낭비를 막기위해 " 동적프로그래밍에서는 소문제의 해를 저장" 해두고 사용하게 된다 ! 중복 연산을 방지하기 위..