start와 end로 이루어진 interval의 배열이 input으로 들어올 때, 범위가 중복되는 값을 합쳐서 리턴하라 stack을 이용하여 풀이하였다 오름차순으로 정렬 후, stack에 interval[0]를 기준으로 넣어 둔다 interval[0][0]은 start, interval[0][1]은 end일 것이다. 이때 stack의 원소의 end보다(Loop가 돌면 마지막 원소와 비교하게 될 것) intervals의 start가 짧다면, 두개를 합친 배열로 stack의 end를 바꿔준다. 그것이 아니라면 범위를 그대로 푸쉬해주면된다.

무작위로 정렬되어 있는 정수를 원소로 가진 배열에 대해, 오름차순으로 정렬된 원소의 갯수를 구하라는 문제이다. DP와 Binary Search를 써서 풀 수 있는 문제 DP의 경우는 간단하다. nums의 길이만큼 1로 채운 dp 배열을 만든다 이때 dp [ i ]는 nums의 i번째 원소의 longest Increasing Subsquence이다. 원소가 하나만 들어오면 longest Increasing Subsquence는 1개이므로 초깃값은 모두 1로 설정한다 nums의 원소를 하나씩 Loop하면서 i보다 작은 j를 모두 검사한다. nums[ j ]가 nums[ i ]보다 작다면 오름차순으로 정렬이 되어 있다는 뜻이다. i보다 작은 j번째 원소를 기준으로 longest Increasing Subsqu..

nums라는 배열에 대해 두개의 subset을 만들어 각 subset 원소의 합이 같은 subset을 만들 수 있는지 여부를 리턴하라 이때 dp [ i ]는 'i라는 부분합을 만들 수 있는지 여부'이다 경계값은 total을 구해서, total을 반으로 나눌 수 없는 경우엔 조건 만족 불가능이다 경계값에 해당하지 않는다면 total의 반을 target으로 만들어 dp를 돌릴것이다. nums의 각 element에 대해서, dp[complement]가 true라면 해당 dp[i]는 true이다 예컨데 [1,5,11,5]라는 배열에 대해 target은 11이다. 이 시점에서 dp[11] 은 dp[11-1]일 것이다. 왜냐하면 10을 만들 수 있다면, 1이 존재하기 때문에 11을 만들수 있다는 뜻이기 때문이다. ..

s와 p를 input으로 주는데, index=n에서 끊으면 p의 anagrams으로만 구성된 s의 부분집합을 찾으라는 문제이다 여기에는 sliding window라는 알고리즘을 적용할 수 있다 슬라이딩 윈도우는 배열의 일정 범위 값을 비교할때 유용하다 index를 두개 두고 범위만큼 조금씩 움직이는 방법이다 모든 배열의 요소를 일일이 체크할 필요가 없기 때문이다 s안에서 p의 anagram을 찾아야하기 때문에, left를 시작점, right를 p의 길이로 둔다 이후 left를 s의 길이가 되기 전까지 Loop에 돌려주는데, left-right구간만큼 배열을 substring하여 해당 구간을 sorting하고 비교한다. 이 둘이 같으면 시작index인 left를 결과에 집어넣는다 타임아웃 에러뜬다

2차원 matrix가 주어질때, target이 있는지 찾아라. 이때 행렬별로 모두 오름차순으로 정렬되어있다 오름차순 배열에서 무언가를 찾으려면? binary search ㄱㄱ 간단한 문제였지만 2차원 배열도 binary search를 한번 적용해 본다는 의미로 기억할만한 문제

1로 구성된 사각형의 최대 크기를 구한다 다음과 같은 원리를 적용해보았다 크기와 모양이 같은 Matrix를 만든 후 , dp로 각각 순회한다 1을 발견했을 때 왼쪽, 위쪽, 좌상단의 값이 모두 1이면 정사각형이 구성된다 이 경우 길이가 2인 정사각형이 만들어지므로 해당 node를 2로 변경한다 일단 index가 되는 매트릭스를 구성하는데 input matrix에 행렬을 하나씩 더한 값으로 구성한다 왜냐하면 1.1 위치가 1일때 node를 1로 순회해주려면 기준값을 주는 것이 편하기 때문이다 이후 루프를 도는데, 하나씩 돌면서 값이 1인 노드를 만나는 경우, 왼쪽,위쪽,좌상단쪽 중 가장 작은 값에 1을 더해 업데이트 해준다 그게 아니라면 노드는 0으로 설정한다 이렇게 업데이트 된 값은 정사각형을 구성할 수..