목록알고리즘/다이나믹 프로그래밍 (4)

개미의 개열시미 프로그래밍

[알고리즘] 백준11727 2xn 타일링2 - 자바

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net [풀이 코드] package dp; import java.util.Scanner; public class BOJ_11727_2xn타일링2 { static int[] D; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); D = new int[1001]; D[1] = 1; D[2] = 3; for(in..
알고리즘/다이나믹 프로그래밍 2022. 3. 31. 22:21
[알고리즘] 백준11726 2xn 타일링 - 자바

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [풀이 코드] package dp; import java.util.Scanner; public class BOJ_11726_2xn타일링 { static int N; static int[] D; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); D = new int[1001]; D[1] = 1; D[..
알고리즘/다이나믹 프로그래밍 2022. 3. 31. 21:31
[알고리즘] 백준9184 신나는 함수 실행 - 파이썬

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net [풀이 코드] dp = list([ [0]*(51) for _ in range(51)] for _ in range(51)) def w(a, b, c): if a 20: return w(20, 20, 20) # 메모이제이션 활용 if dp[a][b][c]: return dp[a][b][c] if a < b and b < c: dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, ..
알고리즘/다이나믹 프로그래밍 2021. 9. 1. 18:39
[알고리즘] 백준1003 피보나치 함수 - 파이썬

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [풀이 코드] t = int(input()) dp = [0] * 41 dp[0] = (1, 0) dp[1] = (0, 1) for i in range(2, len(dp)): dp[i] = (dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]) for _ in range(t): print(*dp[int(input())]) 1. 동적 프로그래밍 풀이로 해결한 문제로 dp배열은 '메모 이제이 션'개념을 활용했다. 메모 이제이 션(Memoization..
알고리즘/다이나믹 프로그래밍 2021. 9. 1. 14:53
Prev 1 Next