일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 코테
- 프로그래머스코테
- 리액트
- 백준알고리즘
- css기초
- JS프로그래머스
- 프로그래머스JS
- 프로그래머스
- 포이마웹
- dp알고리즘
- HTML5
- 백준골드
- JS
- 알고리즘
- 백준
- 백준구현
- CSS
- HTML
- 백준구현문제
- js코테
- 백준nodejs
- 자바스크립트
- 코딩테스트
- 리액트커뮤니티
- 익스프레스
- 백준js
- 리액트댓글기능
- 다이나믹프로그래밍
- 안드로이드 스튜디오
- 몽고DB
- Today
- Total
개발새발 로그
다이나믹 프로그래밍(Dynamic Programming) - 타일링 문제 본문
다이나믹 프로그래밍 기법의 기본인 타일링 문제를 알아보자.
https://www.acmicpc.net/problem/11726
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
이 문제를 푸는 방법은 먼저 n=1일 때 n=2 일 때 n=3일 때를 구하면서 규칙성을 찾아야한다.
그러면 n = k 일 때를 가정해보자.
만약에 n = k-1 인 경우에서 1칸을 앞에 뺐을 때 나올 수 있는 경우의 수는 1개다 (1X2 막대가 하나 붙을 수 있다.)
그리고 n= k-2 인 경우에서 2칸을 앞에 뺐을 때 나올 수 있는 경우의 수는 1개다 (2X1 막대가 두개 붙여서 가능하다.)
여기서 k-2인 경우에 1x2 막대로 두개를 세우는 경우는 왜 포함하지않는지?
-즉 k-1에서 1x2를 하나 세운 경우에 포함되기 때문입니다.
쉽게 설명
현재 n = 3일 때의 경우를 그림으로 그렸다.
이때 앞에서 한칸을 뺐을 경우를 그림으로 그린다.
즉 D[n] = D[n-1] +D[n-2] 라는 식이 도출된다.
근데 왜 3칸을 뺀 경우는 하지않는지?? -> 이또한 n-1에 포함되어있음 위에 쉽게 설명한 부분보면 이해가능
즉 D[n-1]의 계산에서 포함이된다. D[n-1] = D[n-2]+D[n-3] 이니까
그럼 코드로 살펴보자
이전에 배웠던 메모제이션도 포함시켜서 더욱 빠르게 계산한다.
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N = Number(input);
var d = Array(1001).fill(0)
function DP(x) {
if(x==1) return 1;
if(x==2) return 2;
if(d[x] !=0) return d[x]; //메모제이션
return d[x] = (DP(x - 1) + DP(x - 2)) % 10007;
}
DP(N);
console.log(DP(N));
이렇게 된다
그러면 이제 응용이 된 문제를 풀어보자
https://www.acmicpc.net/problem/11727
2×n 타일링 2
1 초 | 256 MB | 62575 | 37333 | 29936 | 59.070% |
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
.
이번의 경우에는 도형을 3개를 사용가능하다.
그래서 D[n] = D[n - 1] + 2*D[n - 2] 라는 식이 나오게 된다.
코드로 바꿔보면 아래와 같다.
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');
let N = Number(input);
var d = Array.from({length:10001},()=>0);
function DP(x) {
if(x==1) return 1;
if(x==2) return 3;// 2칸일 때 3가지의 경우의 수가 나오므로
if(d[x] !=0) return d[x]; //메모제이션
return d[x] = (DP(x - 1) + 2 * DP(x - 2)) % 10007; // DP(x-2) 에 2를 곱해준다.
}
DP(N);
console.log(DP(N));
x==2 즉 2칸일때 3개의 경우의 수가 나오는 것을 적어줘야한다.
출처
https://blog.naver.com/ndb796/221233586932
'알고리즘' 카테고리의 다른 글
다익스트라 알고리즘 (2) | 2023.06.02 |
---|---|
다이나믹 프로그래밍 (Dynamic Programming) - 타일링문제 2 (0) | 2023.06.01 |
다이나믹 프로그래밍(Dynamic Programming) - 메모제이션 (0) | 2023.05.31 |
그래프 이론 (이진트리의 구현과 순회방식) (0) | 2023.05.31 |
그래프 이론(크루스칼 알고리즘) (0) | 2023.05.31 |