임의의 pivot index에 의해 rotate된 배열에서 target이 몇번째 위치에 있는지 찾아라. 오름차순으로 정렬된 배열은 binary search로 해결하는 것이 일반적이다. start와 end index를 두고, endIndex가 클때까지 Loop를 돌린다 이 loop는 middle index를 구하고 target이 있다면 해당 값을 리턴하고, target이 더 크다면 startIndex를 우측 반으로, 더 작다면 endIndex를 좌측 반으로 설정한다. 이는 배열이 오름차순으로 정렬되어 있다는 전제하에 가능한 것이다 이 문제도 target이 있다면 리턴해주면 되는데, 문제는 target이 mid가 아닌 경우다 일반적인 binary search 문제대로 오름차순으로 정렬되어 있다면 그냥 쪼개면..

Linked List와 n을 input으로 받았을 때, 뒤에서부터 n번째 원소를 지우고 다시 List를 리턴하는 문제. two pointer를 사용할 것이다. pointer2은 0번째 원소를 pointer1 는 n번째 원소를 가리키도록 한다. 이는 n만큼 loop시키면 next를 옮기면 된다. 이 시점에서 ponter1을 끝까지 이동시키고(pointer.next가 null일때까지) 그 만큼 ponter2를 이동시키면, pointer2는 끝에서부터 n번째만큼 앞에 있는 원소를 가리킨다. pointer2.next가 우리가 원하는 뒤로부터 n번째 원소이다. 따라서 next를 next.next로 바꿔준다. 만약 원소가 1개짜리라면 pointer1.next가 null이 된다. 그 경우 head를 .next를 이용..

LCA는 Lowest Common Ancestor인 노드를 뜻한다. input으로는 조건이 되는 두개의 노드와 함께 트리가 들어온다. 간단한 트리 재귀문제였다. root가 조건 p,q를 만족할때 리턴해주고, 해당 노드의 left, right를 각각 재귀로 돌려주면된다. 최종적으로 left에 p,q가 없다면 right를, right에 없다면 left를 리턴해주고, 둘 다 있다면 다시 root를 리턴해주면 된다.

트리에서 특정 sum을 만들어 낼 수 있는 연속된 부분집합을 찾아라 약간 헷갈렸는데, dfs와 재귀를 별개로 사용하면 된다. 하나의 노드에서 dfs를 실행하는데, 그게 모든 node가 root가 되어 실행되어야 한다. 그렇기 때문에 dfs는 원래대로 해준다. 이때 오해하지 말아야 할 점이, 같은 root에서 시작한다고 하더라도 조건을 만족하는 답은 여러개 있을수 있으므로, left와 right를 leaf까지 dfs돌려줘야 한다. 최종적으로는 특정 root를 기준으로 나온 count들을 전부 합하면 된다.

단순한 DP문제라서 설명없이 바로 풀어본다 이때 dp[ i ]는 length가 i일때 최대값이라는 것에 주의하자. 경험상 dp는 내가 만드는 index 배열의 의미를 유념하는 것이 중요한 것 같다. length가 i일때 최댓값은 dp[i-1]와 dp[i-2]+i값 중 더 큰 값이다. 이게 사실 dp의 핵심인데 이미 dp[i-1]과 dp[i-2]는 완벽하게 계산된 값이라는 전제하에, dp[i-1]은 nums[i]을 더하지 못하지만 dp[i-2]는 더할 수 있으므로, 그 둘 중 더 큰 값이 무엇인지 생각해내는 것이다.

예시1을 보면 문제 이해가 쉬운데, 두개의 Linked List가 인풋으로 들어오면, 각각 순서를 바꿔서 저장한 후 int로 만들어 이를 더한다. 더한 값을 다시 Linked List로 만드는데, 얘 역시 거꾸로 만든다 이 문제는 reverse연산인데, 원래 942+476으로 연산해야 할 input이 거꾸로 들어온다. 그렇다면 들어온 리스트 순서 그대로 연산한다면 어떤 부분을 고려해야 할까? 자릿수대로 더해주고 결과 linked list에 거꾸로 집어넣으면 된다. 그런데 문제는 두 노드의 합이 10이 넘어가는 경우다 10이 넘어가면 1을 다음 자릿수로 넘겨준다. 따라서 이 문제의 index는 4개가 필요하다. List를 만들고 우리는 List.next를 결과로 리턴해줄것이다. 이 List에는 연산값이 담..