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

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

s의 부분집합 중 가장 긴 palindromic한 요소를 찾아라! DP문제고 투포인터의 원리(실제로 투포인터는 아님)를 이용하여 문제를 풀었다. i를 Loop를 돌리면서 j라는 포인터를 두고, 두개의 스트링이 같은 지점까지 모두 검사한다. 만약 두개의 스트링이 같다면, left는 한칸 줄이고, right는 한칸 늘리면서 최대 palindromic까지 검사한다. 이렇게 검사한 결과가 max의 길이보다 크다면, max를 해당 값으로 바꿔준다(substring이용)

coins배열의 원소들을 합하여 amount로 입력된 값을 만들려고 한다.(원소들은 중복 사용이 가능하다) 이때 만들 수 있는 갯수가 가장 적은 케이스를 찾아 해당 갯수를 리턴한다. 만드는것이 불가능하다면 -1을 리턴한다. 전형적인 DP문제로, amount만큼을 갯수로 가진 배열을 만들어 각 부분의 solution을 구해 global과 비교하면 된다. dp라는 배열을 만들고 amount가 0일때의 값을 입력한다. 그 뒤, 0부터 amount까지에 대한 Loop를 돌면서 coin의 각 원소와 비교한다 예컨데 [ 1, 2, 5 ]인 coins에 대해 i가 5라고 해보자. 일단 coin이 i보다 커지면 의미가 없으므로, i는 coin보다 항상 크거나 같아야 한다. 이 조건을 만족하는 경우에 대해, 해당 coi..

n개의 노드가 주어졌을때 만들수 있는 BST의 조합 갯수를 구하는 문제이다. Tree의 전형적인 재귀방식으로도 풀 수 있으나, 기본적으론 DP로 풀어낼 수 있다. BTS는 크기에 따라 자연스레 노드가 배치된다. 그러니까 root node만 배치하고 갯수만 나누어주면, 각각의 경우의 수는 고정된다는 뜻이다. 예컨데 다음과 같이 세개의 원소가 주어진다고 해보자. 만약 특정원소를 root로 정한다면, 양옆에 BST를 만들 수 있는 경우의 수는(2개,0개) (1개,1개) (0개,2개)로 나누어지는 방식일것이다. 예컨데 n개의 원소가 존재하고, f(n) 을 n개로 만들 수 있는 BST의 수라고 한다면 f(n) =( f(n)*f(0) ) + ( f(n-1)*f(1) ) + ( f(n-2)*f(2) ) + ( f(n..

전형적인 DP 이전 문제의 솔루션과 유사하다 시작하기전에 모든 [ 0, j ] 와 [ i, 0]을 1로 채워준다. 해당 지점까지 도달하는 방법은 한가지이기 때문이다 일단 i가 0인 element는 모두 1로 채워준다 그 뒤 m개의 행,n개의 열이 존재하므로, 2행부터(1행은 1로 모두 채웠다) 채워준다 이때 모든 [ i , 0 ]자리 역시 1가지 경우의수만 존재하므로 1로 채우고 시작한다.