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를 ..

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

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]는 더할 수 있으므로, 그 둘 중 더 큰 값이 무엇인지 생각해내는 것이다.