목록DP (1)
이지선의 블로그
[boj 11726] 2×n 타일링
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 문제 해결 문제를 풀기 전 DP 알고리즘에 대해 학습 후 진행하였다. DP, 즉 다이나믹 프로그래밍(동적 계획법)은 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하여 사용하는 것으로 하나의 문제해결 패러다임으로 볼 수 있다. 일반적인 재귀를 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있다. 예를 들어 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 다음과 같다. f..
Algorithm/BaekJoon
2024. 4. 13. 18:06