Valid Perfect Square 문제 내용 주어진 number의 값이 $ x^2 $ 형태로 표현될 수 있는 수 인지 확인하시오. 단, sqrt method는 사용하면 안됨 접근 방법 가장 쉬운 방법은 1에서부터 number까지 자기자신을 곱해서 원하는 값이 되는지 확인하면 된다. var isPerfectSquare = function(num) { if(num===1) return true; for(let i = 1; i*i 16 $$ 8의 우측은 답의 대상이 될 수 없다. right의 위치를 8로 옮겨준다. 다시 한번 더 num/2를 진행해 보자. 단, 8역시 답의 대상이 되지 못하다는 것을 알았음으로 right의 위치를 한칸 밑으로 옮겨 준다. center는 number/2이고 이 값은 4 즉 답..

132 Pattern 문제 내용 좌측, 우측, 가운데 순으로 숫자의 크기가 결정되는 값이 있는가를 확인 하는 문제이다. 예를 들자면 [3,1,4,2]의 경우 좌측 값 1 우측 값 2일 경우 가운데 4의 값이 가장 큼으로 132패턴을 만족한다. 접근 방법 모든 수를 순회하는 방법이 가장 쉽다. 예를 들자면 왼쪽을 left 오른쪽을 right라고 했을 때, left와 right를 고정하고 가운데를 순회 시키면 된다. 이렇게 되면 left, right full search로 n^2 그리고 가운데 search 횟수 포함해서 $ O(n^3) $ 이 되게 된다. 이것을 최적화 하기위해서 min 값을 관리할 수 있다. 예를 들자면 index 2 값 4일때 min은 1이라는 것을 알 수 있다. left와 right를 ..

문제 내용 숫자로 구성된 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..

Satisfiability of Equality Equations 문제 내용 a==b 또는 b!=c 등의 동일 확인 기호가 주어졌을 경우 해당 수식이 모두 성립하면 true 하나라도 성립하지 않으면 false를 return 해라. 접근 방법 문제를 생각해 보자. ["a==b","b!=a"] a는 b와 같지만 b는 a와 같지 않다. 답은 당연히 false가 된다. 그 이유는 위의 두 식이 성립 하지 않기 때문이다. ["a==b","b==a"] 성립하기 위해서는 위와 같이 정의 되어야 한다. 그럼 조금더 길게 봐보자. ["a==b","b==c","a==c"] 이것은 성립하는가? 그렇다 a,b,c는 모두 동일하다고 볼 수 있다. 만약에 ["a==b","b!=c","a==c"] 이경우는 어떠한가? 성립하지 않는..

Average Selling Price 문제 내용 아래와 같은 Table 2개가 있다. product id의 제품이 팔린 날짜의 price와 팔린 units 갯수를 곱하고 unit 하나당 팔린 가격의 평균을 구하는 query를 작성하라 접근 방법 1. 두개의 Table을 join 한다 select * from Prices a,UnitsSold b where a.product_id = b.product_id select * FROM Prices as a JOIN UnitsSold as b ON a.product_id=b.product_id 위에 두개는 동일한 inner join이다. 2. purchase_date가 start_date와 end_date 사이에 있는 경우만 추출한다. select * from..

Find Center of Star Graph 문제 내용 Star Network에서 center를 찾아라 접근 방법 2개 이상의 Nodes를 이웃하고 있는 점은 단 하나이다. 아무 두점이나 찾아서 2번 나온 값이 답이다. var findCenter = function(edges) { return edges[0][0] === edges[1][0] || edges[0][0] === edges[1][1] ? edges[0][0] : edges[0][1]; }; 그런데 만약에 Start Networks인데 Center는 하나이지만, 다른 Nodes들도 서로를 이웃할 수 있다면 어떻게될까? 이 경우는 아래와 같이 모든 Points에 대한 Count를 해서 최고로 많은 Count가 나온 값을 답으로 하면 된다. v..

Edit Distance 문제 내용 두개의 word가 주어 진다. 예) 'abc', 'abd' 다음 3개준 하나의 Operation이 가능하다고 할때 delete : char 하나를 삭제한다 input : char 하나를 넣는다. replace : char 하나를 바꾼다. 두개의 word가 같아 질 수 있도록 최소한의 Operation 횟수를 구하라. 접근 방법 처음에는 이와 비슷한 문제인 2021.07.05 - [Problem Solving] - One Edit Distance 를 사용해서 Two Points를 이용한 해결 방법을 모색하였다. 그러나 최종적으로 이와 같은 접근법으로는 해결 할 수없다는 것을 알 수 있었다. 본 문제는 Levenshtein 알고리즘을 알고 있느냐에 따라서 쉽게 문제를 해결..

One Edit Distance 문제 내용 두개의 문자열을 비교해서 단 하나의 차이점만 있을경우 true 차이점이 없거나 2개 이상의 차이점이 없으면 false를 return하라 접근 방법 일단 즉각적으로 문제를 해결할 수 있는 경우 2가지를 처리한다. 두 words의 length가 2이상 차이 나는가? 두 words는 같은가? 이 2가지가 문제가 없다면 다음과 같은 2가지로 나뉠수 있다. 2개의 words의 length는 같다 2개중 하나의 word의 length가 + 1 길다 2개의 words중 length가 같은 경우 답이 될 수 있는 경우는 단 한가지 경우밖에 없다. 특정 지점에서 양쪽의 value가 달라야 한다. 상기의 예를 보면 c와 b가 달라지는 지점을 찾았고, 이후의 두개의 value ee..

The Skyline Problem 문제 내용 평평한 선위에 직사각형으로 구성된 네모로 만들어진 그룹이 있다. 이것을 [start point,end point, height]의 집합으로 표현한다고 했을 때, 겹친곳을 제외하고 외곽만 선으로 이었을 때, 수평선의 시작점과 height가 0인 마지막 포인트 하나로 구성된 Points 그룹을 만드시오. 접근 방법 우선 문제를 이해하는게 중요하다. 상기와 같은 문제가 주어졌다고 생각해 보자. 답은 outline의 수평선이 시작하는 포인트가 답이 된다. x와 높이 y 즉 height를 좌표로 한다고 했을 때, (2,10)은 수평선을 시작하는 점이다. (3,15)는 수평선을 시작하는 점이다. 여기서 (5,12) 겹쳐진 네모 안에 있기 때문에 불필요한 포인트이다. (..