속도는 느렸지만 Hard 문제를 혼자서 풀었다는점에 점수를 주는 문제입니다. https://leetcode.com/problems/maximal-rectangle 주어진 matrix 에서 1만으로 구성된 가장큰 rectangle의 넓이를 구하는 문제입니다. dp[i][j] 를 (i ,…
중요한건 꺾이지 않는 마음 이라고 하지만 Hard 문제 앞에서는 거의 항상 좌절하는것 같습니다. 아직 갈 길이 멀다는 뜻이겠지요. 이번 문제는 처음 dp 문제를 잘못…
https://leetcode.com/problems/minimum-height-trees/ 트리 문제로 처음에는 모든 노드를 dfs 로 탐색하며 가장 height 가 낮은 label 을 관리하는식으로 접근했습니다. 당연히 Time out 이 발생했고요.. O( N…
https://leetcode.com/problems/maximum-product-subarray 152번 문제는 문제 자체가 전형적인 DP 문제처럼 보여서 바로 DP 로 접근했습니다. 음수 와 음수를 곱하면 양수간 된다는 점에서 규칙을 찾아서 문제를 풀었습니다.…
https://leetcode.com/problems/word-break/ 리트코드 139번 문제는 사실 Dynamic Programming(DP) 로 이 문제를 풀어야한다는걸 알면 쉬운 문제입니다. 쉽게 가고 싶어서 Related Topics 를 잠깐 확인했고 DP 로 풀수…
리트코드 1976번 문제는 그래프의 최단경로를 찾는 문제입니다. https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/ “알고리즘 트레이닝”에서 그래프에서 최단 경로 구하는 방법을 3가지 소개하고 있는데요. ( 벨만-포드 알고리즘 / 다익스트라…
리트코드 207번 문제 풀이