다이나믹 프로그래밍

백준 9095 파이썬 문제 풀이 : 1, 2, 3 더하기 문제 링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 입출력 예시 제출 코드 T = int(input()) for i in range(T): n = int(input()) arr = [0 for i in range(n+3)] i = 0 arr[1] = 1 arr[2] = 2 arr[3] = 4 if n < 4: pass else: for i in range(4, n+1): arr[i] = arr[i-1] + arr[i-2] + arr[i-3] i += 1 print(arr[n])

백준 2579 파이썬 문제 풀이 : 계단 오르기 문제 링크 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 입출력 예시 제출 코드 n = int(input()) s = [int(input()) for i in range(n)] d = [0] * (n) if len(s) < 2: print(sum(s)) else: d[0] = s[0] d[1] = s[0] + s[1] for i in range(2,n): d[i] = max(d[i-3]+s[i-1]+s[i], d[i-2]+s[i]) print(d[-1])

백준 1463 파이썬 문제 풀이 : 1로 만들기 문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 입출력 예시 제출 코드 test = int(input()) num = [0] * (test+1) for i in range(2, test+1): num[i] = num[i-1] + 1 if i % 3 == 0: num[i] = min(num[i], num[i//3]+1) if i % 2 == 0: num[i] = min(num[i], num[i//2] + 1) print(num[test])

백준 1003 파이썬 문제 풀이 문제 링크 https://www.acmicpc.net/problem/1003 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. 출력 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. 제출 코드 test = int(input()) def fibonacci(n): while len(result0) < n+1: a..

다이나믹 프로그래밍의 개념 다이나믹 프로그래밍은 하나의 큰 문제를 작은 여러 개의 문제로 나누어 해결하는 알고리즘 기법이다. 중복되는 문제의 하위 해답을 저장하고 재사용하여 계산해서 재 사용성을 높이는 방법이다. 다이나믹 프로그래밍의 원리 1. 작은 문제로 분리 - 큰 문제를 작은 문제로 나눈다. 2. 하위 문제 해결 - 하위 문제를 해결하고 그 답을 저장한다. 3. 상위 문제 해결 - 하위 문제의 답을 가지고 재귀적으로 반복적으로 상위 문제를 해결해 나간다. 다이나믹 프로그래밍 문제 예시 백준 1463번 - 자세한 설명 및 문제는 링크를 통해 확인 풀이 n = int(input()) d = [0] * (n + 1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 if ..