무작위로 정렬되어 있는 정수를 원소로 가진 배열에 대해, 오름차순으로 정렬된 원소의 갯수를 구하라는 문제이다. DP와 Binary Search를 써서 풀 수 있는 문제 DP의 경우는 간단하다. nums의 길이만큼 1로 채운 dp 배열을 만든다 이때 dp [ i ]는 nums의 i번째 원소의 longest Increasing Subsquence이다. 원소가 하나만 들어오면 longest Increasing Subsquence는 1개이므로 초깃값은 모두 1로 설정한다 nums의 원소를 하나씩 Loop하면서 i보다 작은 j를 모두 검사한다. nums[ j ]가 nums[ i ]보다 작다면 오름차순으로 정렬이 되어 있다는 뜻이다. i보다 작은 j번째 원소를 기준으로 longest Increasing Subsqu..

nums라는 배열에 대해 두개의 subset을 만들어 각 subset 원소의 합이 같은 subset을 만들 수 있는지 여부를 리턴하라 이때 dp [ i ]는 'i라는 부분합을 만들 수 있는지 여부'이다 경계값은 total을 구해서, total을 반으로 나눌 수 없는 경우엔 조건 만족 불가능이다 경계값에 해당하지 않는다면 total의 반을 target으로 만들어 dp를 돌릴것이다. nums의 각 element에 대해서, dp[complement]가 true라면 해당 dp[i]는 true이다 예컨데 [1,5,11,5]라는 배열에 대해 target은 11이다. 이 시점에서 dp[11] 은 dp[11-1]일 것이다. 왜냐하면 10을 만들 수 있다면, 1이 존재하기 때문에 11을 만들수 있다는 뜻이기 때문이다. ..

1로 구성된 사각형의 최대 크기를 구한다 다음과 같은 원리를 적용해보았다 크기와 모양이 같은 Matrix를 만든 후 , dp로 각각 순회한다 1을 발견했을 때 왼쪽, 위쪽, 좌상단의 값이 모두 1이면 정사각형이 구성된다 이 경우 길이가 2인 정사각형이 만들어지므로 해당 node를 2로 변경한다 일단 index가 되는 매트릭스를 구성하는데 input matrix에 행렬을 하나씩 더한 값으로 구성한다 왜냐하면 1.1 위치가 1일때 node를 1로 순회해주려면 기준값을 주는 것이 편하기 때문이다 이후 루프를 도는데, 하나씩 돌면서 값이 1인 노드를 만나는 경우, 왼쪽,위쪽,좌상단쪽 중 가장 작은 값에 1을 더해 업데이트 해준다 그게 아니라면 노드는 0으로 설정한다 이렇게 업데이트 된 값은 정사각형을 구성할 수..

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

반드시 연속된 부분집합 중 원소들의 곱이 가장 큰 것을 찾아 그 값을 리턴하라 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이라는 부분이다