Ustory

Problemhttps://leetcode.com/problems/count-square-submatrices-with-all-ones/ Sol0과 1로 만들어진 행렬(matrix)에서 1로 만들 수 있는 정사각형의 최대 개수를 구하는 문제  Dynamic Programming 어떤 단계에 있을 때 처음부터 여기에 어떻게 왔는지는 중요하지 않다. 바로 그 앞 단계에서 어떻게 여기까지 왔는지 중요 특정 위치 i에 도착해있다고 가정하고  '그럼 그 전에도 어떻게든 알아서 잘 왔겠지' 라는 생각으로 푸는 형식입니다.  🌱 참고Dynamic Programming lectures Dynamic Programming lectures www.youtube.com문제는 짧은데 생각해내는데 너무 오래걸려서 냅다 유튜브..

Problemhttps://leetcode.com/problems/partition-array-for-maximum-sum/ Sol주어진 배열 arr를 최대 길이 'k'인 연속된 배열로 분할하고, 각 부분 배열의 모든 값을 그 부분 배열의 최대값으로 바꾼 후 배열의 합을 최대값을 구하는 문제 (변경된 배열의 최대합 구하기!)  해결 방법👀 작은 부분 문제를 해결하고 전체 문제를 해결하는 DP(Dynamic Programming)을 사용하였습니다. tab라는 저장 배열을 만들어주고 결과를 저장하며 업데이트하는 방식으로 구현했습니다.Bottom-UP1. tab : 배열 arr의 최대합을 저장하는 배열으로, 0으로 초기화2. 외부 반복문(i) : 1부터 n까지  - i : 배열 arr의 인덱스, tab[i]..

Problemhttps://leetcode.com/problems/count-sorted-vowel-strings/ Sol모음 (a, e, i, o, u)를 가지고 길이가 n인 사전순으로 정렬된 모음 문자열의 개수를 계산하는 문제 해결 방법 1: Combination👀  오늘은 문제를 보자마자 중복조합으로 풀어야겠다고 생각해서 math.comb을 사용해서 해결했습니다. 1. 중복 조합 : [식1] 선택할 수 있는 항목이 r개 일때, 중복을 허용하여 n개를 선택하는 경우의 수  ❓ 각 위치마다 모음을 중복하여 선택 가능(aa, oo, .. 가능) ❓문제 예시에서 'ae'가 나왔으면 'ea'는 같다고 취급함을 알려줍니다.2. 식 표현 : [식2] 이 문제에서는 입력으로 주어지는 길이 n, 모음 5개를 선택..

Problemhttps://leetcode.com/problems/all-possible-full-binary-trees/ Soln개의 노드를 가지는 가능한 모든 완전 이진트리(Full Binary Tree)를 생성하는 문제 Dynamic Programming 동적 프로그래밍동적 프로그래밍 DP == 동적 계획법문제를 작은 하위 문제로 나누고결과 저장➡ 동일 하위 문제에 대한 중복 계산 피하기중복되는 하위 문제큰 문제를 해결하기 위해 동일한 하위 문제를 여러번 해결해야 하는 경우, 중복되는 계산을 피하기 위해 사용문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성될 수 있는 경우Memoization이미 계산한 하위 문제의 결과를 저장해두고 필요할 때마다 결과를 사용하는 방식주로 재귀를 사..