1을 섬, 0을 물이라고 할때 섬의 갯수를 구하라는 문제이다 섬끼리는 adjacent되어 있다 예시로 설명을 해보자면, 이렇게 동서남북이 물에 의해 끊기지 않는 덩어리의 갯수를 구하라는 뜻이다. 이러한 문제는 DFS로 풀어낼 수 있다. DFS는 기본적으로 stack을 하나 두고, 방문전 node들을 모두 false로 둔다 이후 방문한 node에 대해 true로 바꾸고, 방문한 node와 인접한 node들을 모두 stack에 담는다. stack 에 담긴 node에 하나씩 접근하는데, 이때 node의 로직처리를 스택의 순서대로 한다. 예시를 들어보자면 다음과 같다. DFS를 하면 해당 그래프는 우측상단의 순서대로 순회가 될 텐데, 그 과정에서 stack과 array의 변화를 일부 살펴보면 아래와 같다. 방문..

반드시 연속된 부분집합 중 원소들의 곱이 가장 큰 것을 찾아 그 값을 리턴하라 DP문제이고, min, max 배열을 만들어 Loop를 돌리면서 매 순간의 max를 찾아주면 된다. 좀 더 줄여보았다.

perfect squeres는 결국 제곱수를 말하는데 가장 적게 쪼갤 수 있는 제곱수 경우의 수를 구하라는 문제이다 예컨데 13이라면 4와 9라는 제곱수를 더한 꼴이 가장 적은 경우의 수일 것이다. 전형적인 dp문제이다 dp라는 배열을 n까지 만든다 이때 초깃값으로 dp[0]은 0일 것이다. dp[ i ]는 i라는 수에 대한 minmum squre일 것이다. 따라서 이전 제곱수를 빼가면서 각 element의 해를 구하면 된다. 예를 들어 dp[13]은 기존 13의 값과 dp[13-1], dp[13-4]. dp[13-9] 를 비교하면 된다. 이 비교값중 가장 작은 값이 dp[13] 이 될 것이다. 주의할 부분은 dp[i]는 이미 만들어진 원소이므로 초깃값이 1이라는 부분이다

반복되는 character가 없는 최대 길이를 가진 부분 단어를 구하라 start, maxLen이라는 지표를 두고, map이라는 dictionary를 통해 비교한다. 하나씩 글자를 순회하면서 같은 문자가 이미 map에 있다면 start를 해당 map의 위치로 바꿔주고, 그것이 아니라면 그냥 set만 해준다. 이후 start가 고려된 현재 길이가 이전 maxLen보다 크다면 교체해준다.

특정 부분집합을 찾아야 하는데, 이 부분집합만 오름차순으로 sort하면 배열 안의 모든 원소가 오름차순으로 sort되는 부분집합을 말한다 나는 전체 원소를 오름차순으로 만들어 index로 두고, start를 이용하여 처음부터 끝까지 비교하여 완전 같은지 파악한 후 어디서 같지 않은지 표기한다. end도 마찬가지 방식으로 어디서부터 다른지 표기한다 이후 해당 지점을 구하기 위해서 end에서 start를 빼서 센다

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