meetcode-2020-07-11

매우 간단한 문제입니다.가장 쉬운 방법은 그냥 문제에 주어진 대로 코딩을 하면 됩니다.이 경우 시간복잡도는 O(N^2) 가 됩니다.조금 더 생각해보면 우리는 갯수만 알면 되고, 조합을 사용할 수 있습니다.만약 1 의 갯수가 4개 라면 1 로 만들수 있는 Good pai

전형적인 탐색 문제입니다. DFS 을 사용할 수도 있고, BFS 을 사용할 수도 있고, UnionFind 을 사용할 수도 있습니다.저는 간단한게 DFS 을 사용해서 구현을 하였습니다.시간복잡도는 O(H\*W) 가 됩니다.

전형적인 dp 문제 입니다.선은 교차하지 않기 때문에 우리는 선을 순서대로 이을 수 있습니다.아래 그림에서 만약 우리가 중간의 1 빨간색 선으로 이으면나머지 왼쪽 부분과 오른쪽 부분에서의 부분문제로 나눠서 풀 수있습니다.문제의 정의상 오른쪽부분에서 왼쪽부분으로 선을 긋

원하는 값이 lower 이상, upper 미만의 조건을 가질 경우, 일반적으로 각각을 따로 구하는 것으로 문제을 쉽게 풀 수 있습니다.문제을 바꾸어 봅시다. 만약 Subarray 의 최댓값이 upper 이하인 갯수을 구하는 함수을 만들어 봅시다.일반적으로 subarra