Max Points on a Line 문제 내용 어떤 1차 방정식의 선분을 그었을 때 해당 선을 지나가는 가능 많은 Points의 갯수를 구하라. 접근 방법 지극히 수학적인 접근이 필요하다. 우선 기본적인 1차 방정식을 생각해 보자. $$ y = ax + b$$ 여기에서 a는 기울기 b는 절편이라고 생각하면 된다. 기울기는 다음과 같이 나타낼 수 있다. y의 변화량을 x의 변화량으로 나눈 값이 된다. $$ slope = (y2 - y1) / (x2 - x1) $$ 이것을 3개의 Point가 한개의 선을 지나가는가? 라는 접근 방법은 아래와 같이 나타낼 수 있다. $$ (y2 - y1) = (x2 - x1) * slope + bias $$ 그런데 위 수식에서 bias는 두점에 대한 상대라고 생각했을 때 b..

사람이 최대 공약수를 구하는 방법은 다음과 같은 계산 방식으로 해결을 한다. 그럼 프로그램 적으로는 어떻게 접근 하는 것이 좋은가? 모든 경우의 수를 계산 한다. 최대공약수는 기본적으로 a와 b를 동시에 나눌 수 있는 가장 큰 수라는 전제가 있다. 그렇기 때문에 a와 b중 작은 수를 기준으로 모든 수를 나누어 보면 된다. function gcd_linear(a, b) { let min = Math.min(a, b); for (let i = min; 0

Reaching Points 문제 내용 (sx,sy)로 시작한 point는 다음과 같이 값을 변화 시킬 수 있다. (sx + sy, sy) (sx, sy + sx) 최종값이 (tx,ty) 가 가능한가? 접근 방법 기본 적인 접근법은 Binary Node를 확장하는 것이다. (sx, sy)가 (1,1)일 경우 sx를 증가 시키거나 sy를 증가시키거나 하는 방법으로 $ 2^n $ 으로 node를 늘려가면서 정답을 찾으면 된다. 그러나 이것은 매우 비효율 적이다. 만약에 tx, ty가 (2,3)이라고 생각해 보자. back ward로 거슬러 올라오는 방식으로 접근을 한다면, 가지 치기가 되게 된다. 이 가지 치기를 할때 한가지 rule만 따르면 된다. 큰곳에서 작은 것을 뺀다. 왜냐면 작은것에서 큰것을 빼면 ..

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

이진검색은 많은 곳에서 사용되는데 의외로 Lower Bound와 Upper Bound 문제가 나오면 정확한 코드를 만들지 못해서 쉬운 풀이임에도 틀리는 경우가 많고 오류가 많이 난다. 그래서 이번 기회에 Bound에 대해서 정리 하려고 한다. Binary Search 이진 탐색은 가장 유명한 탐색 기법이다. 만들기도 쉽고 직관적이다. 아주 쉬운 내용이기 때문에 간단히만 설명 하겠다. Target이 3이고 길이 6의 array가 있다. 3을 찾기 위해서는 $ O(N) $으로 왼쪽에서 오른쪽으로 값을 찾는 방법도 있지만 Binary Search를 하면 $ O(logN) $ 으로 처리가 가능하다. 이를 처리하기 위한 핵심은 mid를 찾는데 있다. 일반적인 mid를 찾는 기법은 let mid = Math.flo..

Remove Invalid Parentheses 문제 내용 '(' 와 ')' 로 구성된 문자열이 있다. 해당 문자열을 중괄호라고 부를때 '(' 와 ')'의 pair가 맞게 할 수 있는 최소한의 delete가 된 가능한 모든 문자열을 결과로 return 해라 단, 중간에 문자가 있을 수 있다. 접근 방법 일반적인 Parentheses 문제를 이용해서 문제를 해결해 나가야 한다. 우선 validation check에 대해서 생각해 보자. 기본적으로 Parentheses 문제는 '('의 갯수가 무조건 ')'의 갯수보다 많은 경우 Validation이 된다고 생각해야한다. 2020.09.15 - [Problem Solving] - 괄호 변환 문제에서 getBalancedCount 부분을 참고하자. 이 내용을 기..

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

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를 순회한다. 가장 접근 하기 쉬운 방법이다. 이렇게 생긴 문제가 주어졌다고 생각해 보자. 한눈에 보기에 ..