Longest Increasing Path in a Matrix 문제 내용 Matrix에서 오름차순으로 갈수 있는 최대의 길이를 구하라 접근 방법 음... 오랫만에 쉬운문제라 행복했다. dfs만으로 해결이 된다. Matrix가 M x N 이라고 할때 하나의 cell을 한번만 순환하게 만들면 된다. 예를 들어보면 상기 문제에서 $ (1,0) $에는 4가 들어있다. 4에서 오름차순이 가능한 cell은? 없다. dp로 보면 자기 자신만이 가능함으로 1의 길이를 갖는다. 이 길이는 확정이 된다. 그럼 $ (1,1) $ 은 어떤가? 4로만 오름차순으로 올라갈 수 있다. 하지만 4는 이미 dp의 값이 확정이다. 4로 순회 할 필요 없이 4의 dp 값 1에 자기 자신 1을 더하면 된다. 2는 어떤가? 3으로밖에 갈수..

Count of Smaller Numbers After Self 문제 내용 숫자로 이루어진 Array가 주어지고, 각 숫자의 오른쪽에 위치한 숫자중에 현재의 숫자보다 작은 숫자의 갯수를 맞추는 문제 이다. 접근방법 굉장히 다양한 접근이 가능한 문제이다. 가능하다면 모든 경우의 문제를 푸는 것이 좋다고 생각한다. full search segment tree & binary indexed tree insertion sort merge sort full search 모든 경우의 수를 조회하는 방법이다. 예를 들어 보자. $ [5,2,6,1] $ 이 있다고 생각해 보자. 5보다 작은 우측의 수는 2와 1 두개가 있다. 이것을 알기 위해서는 2,6,1을 한번씩 순회하면 된다. 다음은 2일때다. 2일때는 6과 1 ..

Regular Expression Matching 문제 내용 s와 p라는 문자열이 주어진다. p는 일반 영문자와 아래 2개의 char로 구성될 수 있다. `.` : 단 한개의 모든 char 종류와 동일하다 `*` : * 직전에 오는 char가 0개 이상 존재 할 수 있다. s와 p가 동일한 문자열이 가능한지 비교하라 접근 방법 가장 쉬운 방법 부터 생각을 해보자 `*` wildcard가 없는 경우를 생각하자. 단순히 왼쪽에서 오른쪽으로 s와 p의 index를 하나씩 움직여 가면서 모든 문자열이 동일한지 확인 하고 만약에 동일하지 않은 것이 나오면 false를 return 하면된다. 주의 해야할 것은 `.`이 모든 문자열을 대치 할 수 있다는 것이다. 그러면 wildcard가 들어간다고 생각해 보자. 이 ..

Sliding Window Maximum 문제 내용 1차원의 숫자 배열 Array가 주어졌을 때 일정한 범위의 widow size 만큼의 길이 안에서 최대 Number 값을 찾아라 접근 방법 2가지로 접근이 가능한다. Doubled Array List Dynamic Programming Doubled Array List로 접근을 알아보겠다. Doubled Array List는 java 경우 Deque이용해서 Head와 Tail을 O(1)의 시간으로 접근 가능하고 Head, Tail 삭제도 O(1)로 가능하다. 단, removeFirstOccurence 같은 경우는 값을 찾아야 해서 O(N)의 시간이 걸린다. Deque를 사용하는 경우 javascript는 직접 구현을 해줘야 하는게 있어서 간단히 그림으로..

Word Break II 문제 내용 및 풀이 방법은 2020.09.29 - [Problem Solving] - 139. Word Break 와 동일하다. 다른 점이 있다면 word break 1번 문제는 Dictionary로 해당 문자를 만들 수 있는가? 이고 word break 2번 문제는 모든 경우의 수를 return 하는 것이 다르다. public List wordBreak(String s, List wordDict) { return dfs(s, wordDict, new HashMap()); } public ArrayList dfs(String s, List wordDict, HashMap dp) { ArrayList result = new ArrayList(); if (dp.containsKey(..