고슴도치의 IT여행

풀이 문제 : 백준 11726번 2×n 타일링 풀이 언어 : C++ 알고리즘 : 다이나믹 프로그래밍 문제링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제요약 문제는 매우 간단하다. 접근 방식 처음엔 짝수랑 홀수를 따로따로 생각해봤는데 아무리 해도 답이 안나와서 알고리즘 분류를 봤더니 다이나믹 프로그래밍 문제였다,, 다이나믹 프로그래밍은 문제를 보자마자 알고리즘이 떠오르지 않아 어려운거 같다. DP문제인 것을 깨닫고 나서 처음엔 재귀함수를 짜서 풀었다. ..

코딩테스트에서 DP 알고리즘은 단골 문제로 나온다. 그런데도 많은 사람들이 어려워하고, 나 또한 매우 어려워한다. 이번 기회에 개념을 확실히 다지고 DP 를 정복하고자 한다!! 피보나치 수열 DP 알고리즘의 대표적인 예시이다. 예시를 보면서 DP를 이해해보자. 피보나치 수열은 점화식으로 표현할 수 있다. 이 점화식을 따라서 알고리즘을 짜기 위해서는 재귀 함수를 이용해야한다. int fib(int n){ if (n==1 or n==2){ return 1; } return fib(n-1) + fib(n-2); } 그런데 이런식으로만 작성하면 구하고자 하는 값이 커질때는 시간이 너무 오래 걸릴 수도 있다는 한계점이 있다. 왜냐하면 이미 구한 값을 계속 구해야하기 때문이다. n이 1이거나 2일때가 나올때까지 계..