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으로 설정한다 이렇게 업데이트 된 값은 정사각형을 구성할 수..

board라는 2차원 배열로 매트릭스가 주어지고, word라는 글자가 sequential하게 이어질 수 있는지 여부를 리턴하는 문제 DFS를 하면서 해당하는 word가 나오면 하나씩 substring하는 방식으로 풀어보았다 일단 dfs함수는 board와 i,j라는 위치, 남은 word인 remain을 인자로 받는다. remain이 더이상 남아있지 않으면 true, 있으면 false를 리턴한다. 모든 요소에 대해 검사를 진행할것인데, 검사가 진행된 board는 - 로 바꿔준다 이후 해당 char에 인접한 동서남북을 각각 dfs하여 remain[0]이 없는 경우는 바로 false를 리턴해주고 나머지는 true로 진행한다.

오름차순으로 정렬된 배열에 대해 target이 주어지면, 이 타겟이 위치한 index의 시작과 끝을 구하라는 문제 binary search 문제다. 여기서 주의할 부분은 target이 2개이상이므로, target=mid일때 리턴하지 않고 mid까지 포함하여 범위를 자른다는 것이다. 기존의 binary search를 이용하면 range중 하나만 찾아낼 것이기 때문이다. 따라서 가장 먼저 등장하는 res[ 0 ]과 가장 나중에 등장하는 res [ 1 ]을 각각 구한다 res[0]의 경우는 다음과 같은 과정을 거친다. mid를 정하고 해당 로직처럼 범위를 좁혀나가면, r=mid, l=mid+1로 설정하므로 l이 해당 target의 첫번째 위치가 된다 res[1]의 경우는 다음과 같은 과정을 거친다. mid를 ..