node가 집이고 도둑이 여기를 순회하면서 node의 value만큼 돈을 훔친다. 이때 바로 옆집을 훔치면 경찰에 잡혀서, 한칸이상 떨어진 집의 돈을 훔쳐야 할 때, 총 얼마나 훔칠 수 있는지 구하라는 문제 하나의 node에 방문했을 때, 그 node의 집을 훔치기로 한다면 r, 아니라면 n이라고 하자 leaf라면 [0,0]이 되겠지만, 그것이 아니라면 [ 훔치기로 함, 안훔치기로 함]이 된다 훔치기로 하면 그 node의 value를 리턴해주면 된다. 안훔치기로 했으면 그 아래 노드의 최댓값을 리턴해준다

tree가 valid한지 판단하라는 것인데, 이 트리의 valid함은 left, right 트리가 크기대로 잘 정렬되어있냐의 여부이다 경계값을 제거하고, helper함수에 대해 root가 min보다 작은 value를 가졌거나, max보다 큰 value를 가진 경우에 false를 리턴해주면 된다.

양의 정수들로 이루어진 배열이 주어질 때 + 와 - 를 적절히 사용해서 특정 합 S 를 만들 수 있는 경우의 수를 찾는 문제 DP로 문제를 풀어보려한다. 배열에 있는 원소중 A그룹은 양수가 될 것이고, B그룹은 음수가 될 것이다.(배열에는 모두 양수인 정수이다) 따라서 A그룹은 우측 연산에 의해 (S+sum)/2로 표현된다 아래부터 A그룹은 target이라 부른다 일단 S가 sum보다 크거나 연산값이 홀수라면 답이 나올수 없으므로 경계값을 처리해준다 이후 findSubSet이라는 함수를 만들어 nums와 target을 넘겨준다 이 target은 양수가 될 원소들을 모두 합한 부분합이다 이것을 dp라는 배열로 만들것인데, dp[ i ]의 값은 target이 i가 되는 경우의 수이다. i를 기준으로 Loop..

Linked List를 오름차순으로 정렬하라는 문제이다. 공간복잡도가 O(1)이라 최대한 해당 리스트내에서 sort해보겠다 일단 경계값을 제외한다 이후 메인로직에 서는 Merge Sort를 이용한다 분할-> 합병의 순서로 배열을 처리한다. 분할의 경우 반으로 쪼갠다. 보통 Array를 정렬하는 경우 반으로 나누면 되는데, Linked List는 길이를 알 수 없으므로 fast와 slow라는 노드를 두고, slow는 한칸, fast는 두칸씩 움직이면 fast가 끝나는 시점에서 딱 반절의 위치를 알수 있게 된다. 이를 재귀로 길이가 0또는 1이 될때까지 쪼갠다. 이때 prev는 이전 함수에서 사용한 인덱스이므로 next를 null로 설정해주어야 한다. 분할이 끝나면 합병을 진행한다 재귀를 통해 0또는 1길이..

점프게임 1과 조건은 같지만, last index까진 무조건 도착한다는 전제이다. 이때 0부터 시작해서 가장 적은 횟수로 last index까지 가려면 몇회가 소모되느냐이다 Greed를 쓸껀데 여기에서 착각하지 말아야 하는 점은 범위단위로 움직인다는 것이다. count, now, max라는 세가지 변수를 두었다 순서대로 배열을 하나씩 돌면서 이를 업데이트 해줄 것이다. max를 local마다 업데이트 할 것이고, 이는 각 지점에서 최대로 갈 수 있는 지점까지의 값이다 모든 배열에서 로직이 돌면 global max를 찾을 수 있다. index=0에서 시작하니 count가 하나 올라가고 max가 변경된다. 이때 주의점은 범위단위라는 것인데, now와 실제 minmum이 별개로 움직인다는 뜻이다. 예컨데 문제..

각 element의 값은 해당 index로부터 element의 값만큼 떨어진 index로 점프할 수 있음을 나타낸다 이때 마지막 index로 갈 수 있는지의 여부를 묻는 문제이다. 이렇게 단순히 배열을 순회하는 케이스에서는 greedy로 풀어내면 수월하다. target을 배열의 마지막 index로 설정한다. target을 배열의 맨뒤부터 설정하고, 각 원소로부터 target까지 갈 수 있는지 여부를 판단한다 한곳에서라도 방법이 있다면 해당 위치로 타겟을 바꾸어 검사한다 예컨데 [3,2,1,0,4] 은 false인데, 0,1,2,3 위치에서 어떻게 하더라도 index=4로 갈 수 없기 때문이다. 만약 [3,3,1,0,4] 라면 true일 것이다. index=1의 위치에서 index=4로 갈 수 있기 때문이..