(25.03.29) 최대 사각형 구하기 알고리즘 : 히스토그램, DP, 비트마스크
Maximal Rectangle 이란 알고리즘을 비트마스크와 DP를 사용하는 예제로 풀게 되었는데,상당히 이해하는데 많은 시간이 걸렸기에.. 일단 완벽하게 이해를 하는것 보다 이렇게 작동되는지 알고 코드 흐름을 기억하는 수 밖에 없는 것 같다. 추후에 언젠가 보여질 수 있기 때문에 반복해서 코드를 기억해서 작성하기도 했다.Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0"..
2025. 3. 29.
(25.03.27) 비트 마스크의 활용 : DP 심화
비트마스크가 생각보다 빠르게 적용할 수 있는 점을 알게 되어서 DP 부분에 많은 적용을 해보려고 노력하고 있다. You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.For example, if nums = [1, 2, 3, 4]:[2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.[1, 4] and [4] are not good subsets with pro..
2025. 3. 27.