문제 내용 숫자로 구성된 Array가 있다. 해당 Array와 동일한 길이의 0으로 채워진 Array가 있을 때 연속된 Sub Array를 1 증가 시킬 수 있다면, 몇번의 Sub Array 증가 Operation이 필요한가? 접근 방법 [1,2,3,2,1] 이 있을 때 우리는 어떻게 계산을 해야하는가? 전체 Array에 1을 한번 채워서 [1,1,1,1,1]을 만들고 다시 중간에 [0,1,1,1,0]을 채우고, 마지막으로 [0,0,1,0,0]을 채우면된다. 그럼 조금더 복잡한 값을 생각해 보자. [3,1,5,4,2]를 계산해 보자. 가장 하단에서 부터 11111을 채우고, 다시 2단에서 10111을 채워 넣어야 한다. 그런데 연속된 Sub Array를 1 증가시키는 Operation만 가능함으로 100..

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으로밖에 갈수..

Critical Connections in a Network 문제 내용 노드와 nod-directed edges가 주어졌을 때, 어떤 edge가 없어지면 노드 그룹이 분리되게 되는 지 찾아라 접근 방법 이 문제는 하기 링크의 문제와 그 접근 방법이 같다. 2020.08.31 - [Problem Solving] - 1568. Minimum Number of Days to Disconnect Island 2가지의 문제 해결 방법이 있다. edge를 삭제하고 dfs를 순회한다. 타잔(tarjan) 알고리즘을 이용해서 critical edge를 찾는다. 우선 첫번째 방법을 알아보자 Edge를 삭제하고 dfs를 순회한다. 가장 접근 하기 쉬운 방법이다. 이렇게 생긴 문제가 주어졌다고 생각해 보자. 한눈에 보기에 ..

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

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을 기준으로 주어진 문..