DP

💡  오늘의 학습 키워드더보기📌  동적 프로그래밍 문제 설명문제 링크 : https://leetcode.com/problems/count-square-submatrices-with-all-ones/Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.제한 사항1. 1 2. 1 3. 0  문제 회고💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지dp로 풀지 않으면 시간 복잡도 문제를 해결할 수 없는 문제였습니다. 문제 풀이 과정보다 풀이 아이디어를 생각하는게 중요했던 문제이고, DP 배열은 다음과 같이 정의됩니다.DP 배열은 dp[i][j]로 주어진 matrix와..

다이나믹 프로그램은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이다. 다음의 2가지 조건을 만족할 때 다이나믹 프로그래밍을 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있음 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일함 위 조건을 만족하는 대표적인 예로 피보나치 수열이 있다. 피보나치 수열은 다음의 점화식을 만족하는 수열이다. 해당 피보나치 수열을 Python 재귀함수로 구현한다면 다음과 같은 코드로 표현할 수 있다. import time def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) for num in range(5, 40, 10): start = time.time() r..