1. 문제
2. 다이나믹 프로그래밍 개념.
도저히 풀 수 없어 블로그 검색을 통해 다른 분들의 도움을 받았다.
다이나믹 프로그래밍이란 개념을 활용하여 풀어야했다.
다이나믹 프로그래밍 개념이란?
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
1️⃣ 분할정복(Divide and Conquer)도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
2️⃣ 다이나믹 프로그래밍과 분할 정복의 차이는 큰 문제를 작은 문제로 나눴을 때, 중복이 가능한지 불가능한지이다.
3️⃣ 다이나믹 프로그래밍은 작은 문제의 중복이 된다.
4️⃣ 분할정복은 작은 문제의 중복이 안 된다.
5️⃣ 10을 나눌 때 분할정복이라면 5/5, 6/4, 7/3, 3/7과 같이 중복이 되지 않게 나눈다.
6️⃣ 10을 나눌 때 다이나믹 프로그래밍이라면 5, 5, 3과 같이 중복이 되게 나눈다.
7️⃣ 다이나믹 프로그래밍이란 이름 자체에는 아무런 의미가 없다.
다이나믹 프로그래밍의 활용
- 큰 문제를 작은 문제로 나눠서 푸는 방식이기 때문에 다음과 같은 곳에 활용될 수 있겠다.
1️⃣ 겹치는 부분 문제가 있는 경우 (Overlapping Subproblem) :
큰 문제를 작은 문제로 쪼갤 수 있는 경우
2️⃣ 최적화 부분 구조 (Optimal Substructure) :
작은 문제를 풀어나감으로써 큰 문제의 정답을 구할 수 있는 경우
3. 고수의 풀이법
✳️ 접근
1️⃣ 이중 포문을 사용해서 경우의 수를 직접 탐색하려고하면 O(N^3)이 되어 최대 ROW길이가 1000이므로 1000^3=1,000,000,000 이므로 약 10초의 시간이 걸린다.
따라서 시간복잡도를 줄이기 위해 DP를 사용해야한다.
문제 해결 방식은 다음과 같다.
2️⃣ 해당 인덱스의 map 값이 1일 경우 왼쪽, 위쪽, 왼쪽위쪽의 최소값 +1이 현재 길이가된다.
참고 : 자바스크립트로 알고리즘 정리하기 #9 다이나믹 프로그래밍 개념
프로그래머스 - 가장 큰 정사각형(Level 2)/Wanna Be 컴잘알
[프로그래머스] 가장 큰 정사각형 찾기 | JavaScript
코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스
start!