메모이제이션

프로그래밍/백준
백준 11726: 2xn 타일링 해설- python
✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✏️ 풀이 뭘 어쩔지 모를땐 늘 그렇듯 규칙을 찾아보자. 모든 경우의 수를 한번 생각해보았다. n=1 > size 1 : 1개 n=2 > size 1: 2개 || size 2: 1개 n=3 > size 1: 3개 || size 1: 1개 + size 2: 2개 || size 1: 2개 + size 2: 1개 n=4 > size 1: 4개 || size 1: 2개 + size 2: 2개(L) || size 1: 2개 + size 2: 2개(R) || size 1: 1개 + s..
→2022.01.23
프로그래밍/자료구조 & 알고리즘
[Python & Algorithm] Dynamic Programming(동적프로그래밍)
✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..
→2022.01.22

• 이전
• 1
• 다음