Longest Increasing Subsequence 문제 내용 주어진 Array에서 가장 긴 연속된 순서의 길이를 찾아라. Array내의 Position을 수정할 순 없지만, 중간에 있는 값을 삭제 할 수는 있다. 접근 방법 Brute Force 상위와 같은 배열이 주어졌을 경우 다음과 같이 Array를 찾을 수 있다. 9보다 작은 값이 이전에 있었는가? 없었다면 dp 1을 유지한다. 2보다 더 작은 값이 있는가? 없음으로 유지한다. 5보다 작은 값이 있는가? 2가 더 작았다. 그럼 2의 dp + 1을 해준다. 3도 같은 방법으로 dp의 값을 올려준다. 7의 경우 2,5,3 중 가장 높은 dp의 값에 + 1을 해준다. 101은 4가 된다. 18도 4가 된다. 위의 방식은 Time Complexity가..

Data Stream as Disjoint Intervals 문제 내용 Class 를 만드는 문제이다. Class의 목표는 다음과 같다. addNum(int) : integer를 입력 받는다 getIntervals() : 입력받은 integer의 배열이 1의 차이로 연결되어 있다면 [start,end]로 연결되어 있는 값의 시작값과 연결이 끝나는 끊값으로 구성된 2차원 배열을 return 한다. 접근 방법 해당 문제는 다음과 같은 constraints를 갖는다. $ 0

Super Egg Drop 문제 내용 N개의 달걀이 있다. K 층으로 이루어진 빌딩이 있다. 달걀은 해당 빌딩의 특정 층 F에서 깨지기 시작한다. N개의 달걀을 이용해서 F 층을 찾을 수 있는 가장 적은 시도 횟수를 갖는 방법 횟수를 찾아라 접근 방법 문제 자체를 이해하는데 굉장히 난해했다. 이 문제는 굉장히 오래된 문제인데, 아직도 Youtube나 Article을 보면 적당히 설명이 된 글이 많지 않았다. 어떤 글은 너무 쉬운 부분만 설명하거나, 또 어떤 글은 굉장히 어려운 말로 설명되어있었다. 우선 문제를 이해하자. 5층으로 이루어진 빌딩이 있고 달걀 1개가 주어졌다면 몇번 욺직여야 f를 찾을 수 있을까? 한개의 달걀로 f를 무조건 찾을 수 있는 방법은 5층에서 부터 2층사이에 달걀을 던지면 안된다는..

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

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