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 Search II 문제 내용 주어진 m x n 문자 배열이 있고, Dictionary가 주어진다면 해당 문자배열에서 조합가능한 모든 Dictionary내 words를 찾아라. 접근 방법 이런 board가 주어 졌다고 생각해 보자 가장 쉬운 접근 방법은 하나씩 조회해 보는 것일것 같다. 가령 'o'가 있이니까 Dictionary내에서 'o'가 있는 모든 words를 1회 search한다. 그리고 다음으로 a또는 e로 이동한다. 다시 앞서 조회된 o의 words에서 a또는 e가 있는 words를 찾는다. 이렇게 찾다가 words의 마지막 char와 board의 char가 동일해지는 순간 결과 값으로 등록 하면 된다. 그리고 다시 (0,1)인 'a'부터 다시 조회를 시작하면 된다. 이 방법을 최악의 ..

Sudoku Solver 문제 내용 수도쿠에 빈 칸을 모두 채우시오 접근 방법 full search를 제외하고 해결 방법은 없다. 가장 쉬운 방법은 모든칸에 모든 값을 대입하는 방법이다. row 9개 col 9개의 cell로 구성된 board가 수도쿠 임으로 모든 cell은 81칸으로 이루어져 있다. 각 cell은 1부터 9까지 9개의 값을 갖을 수 있다. 이런칸이 81칸임으로 $$ 9^{81} $$ 이 된다. 이것을 약간 최적화 해보자면 다음과 같이 바꿀수 있다. - 앞서 선택된 값을 선택하지 않는다. 예를 들자면 9개의 네모칸이 있다고 생각해 보겠다. 이중 첫번째 네모칸을 1로 선택한다면 뒤에있는 8개의 칸은 2에서 9사이 선택권을 갖는다. 이런방식으로 첫번째 칸은 9가지 선택권을 두번째 칸은 8가지..

Minimum Window Substring 문제 내용 주어진 t라고 하는 문자열이 s라고 하는 문자열에 완전히 포함되는 경우 중에 가장 작은 사이즈의 부분 문자열을 구하시오 접근 방법 처음에 해당 문제를 접근할때는 1Point에 Index를 두개 두어서 접근 하고자 했다. 상위와 같은 방법으로 count가 모두 0일때 Index의 min과 max를 구해서 가장 작은 문자열을 뺄려고 했는데, 이 방법은 특정 문자가 중복해서 나올경우 예를 들자면 상위 그림에서 A가 2번 나오는 것을 check하고자 한다면 Index를 Array로 관리 해야한다. 개발은 가능하겠지만 개발 복잡도나 Time Complexity에 맞지 않는 것 같다. 그래서 Two Point를 사용하는 방법으로 다시 고려 하였다. left와 ..

Binary Tree Maximum Path Sum 문제 내용 왼쪽에서 오른쪽으로 한개의 라인으로 이었을때 가장 큰 값은? 접근 방법 문제를 이해하기 쉽지 않다. 예제의 Depth가 최대 1 depth로 표현 되어있기 때문이다. Testcase를 돌려보면 몇개의 Depth가 되든 상관없이 왼쪽의 노드에서 오른쪽 노드까지의 Sum이 최대가 되면 된다. 예를 들자면 다음과 같다. 즉 양수이기만 한다면 left child와 right child 중 가장 큰값을 기준으로 sum을 하면 된다. 이런 그림인데 이 그림으로 인해서 혼돈이 발생 할 수도 있는데, 만약 다음과 같은 경우라면 $$ 3 $$ 이 답이 된다. 즉 어떤 Path든 상관없이 왼쪽 오른쪽의 0이상의 Max 값을 더해서 최고가 되는 값을 구하면 된다..

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(..

Reverse Nodes in k-Group 문제 내용 주어진 Linked List를 주어진 상수 값으로 Reverse Node를 시키면서 Linked List를 유지 시켜라. 예를 들자면 [1,2,3,4,5] 가 주어졌을 때 2라고 하면 2개씩 Linked List를 Reverse 처리한다. [2,1,4,3,5] 3이면 3개씩 [3,2,1,4,5] 접근 방법 우선 문제를 2가지로 나누어서 생각할 필요가 있다. 주어진 Linked List 범위를 Reverse 시킨다. Reverse된 Linked List를 Group간에 연결을 시켜야 한다. 우선 Linked List를 Reverse 시키는 방법 부터 고민을 해야한다. 위 그림을 예로 들어보자 [1,2,3,4,5] 라고하는 Linked List가 주어지..

Alien Dictionary 문제 내용 의미를 알수 없는 Alien의 Dictionary 가 alien 기준의 알파벳 오름차순 기준으로 주어진다면, alien 기준의 알파벳 순서를 사용해서 사용된 chars의 순서로 word를 만들어라 접근 방법 words = ["wrt","wrf","er","ett","rftt"] 라는 입력이 들어왔을 때, 알파벳 순서임으로 w < e e < r r < t t < f 을 추측할 수 있다. 예를 들자면 wrf보다 er이 더 작음으로 w보다 e가 알바펫 순서상으로 더 크다고 볼수 있다. 여기서 주의를 해야할 것은 wrf와 er사이에 w와 e의 관계가 성립되었다면, rf와 r 사이에 관계는 더이상 무의미 하다 2번째로 주의해야 할 것은 edge 케이스 인데, "abcd" ..

Maximum Profit in Job Scheduling 문제 내용 주어진 Job List를 이용해서 가장 높은 Profits를 계산 하시오 접근 방법 질문을 Knapsack 으로 변경해도 문제가 동일하다. 가방에 최대한 많은 양의 물건을 담고자 한다. 얼마의 무개까지 담을 수 있는가? 와 동일하다. DP를 이용한 최대 Profits를 계산하면 된다. 문제가 [starttime, endtime, profit]으로 아래와 같이 주어졌다고 생각해 보겠다. [1,3,20] [2,5,20] [3,10,100] [4,6,70] [6,9,60] 이런 문제가 있다고 했을 때 DP는 Profit을 확정짓는 endtime 기준으로 해당 시점의 최대 Profit을 유지하면 된다. 우선 endtime을 기준으로 주어진 문..