문제번역문자열 s가 주어졌을때, 가장 긴 팰린드롬 부분배열의 길이를 반환해라.여기서 부분배열이란, 원래 문자열에서 일부 문자를 지우거나 지우지 않아서 만들 수 있는 수열이다.일부 문자를 지워도 남아있는 문자들의 순서는 바뀌면 안 된다. 접근 방법 및 소스코드문자열 전체를 보지 않고 작은 구간부터 찾아가면 된다.dp[i][j] 는 문자열 i번째부터 j번째까지의 구간에서 만들 수 있는 가장 긴 팰린드롬 부분배열의 길이라고 하자. 양 끝 문자가 같다면 이 둘은 팰린드롬의 양 끝으로 같이 쓸 수 있다.그러면 안쪽 구간에서 만든 가장 긴 팰린드롬에다가 양쪽 문자 2개를 더하면 된다. 양 끝 문자가 다른 경우 둘 다 쓸 수 없다.그래서 왼쪽 문자 i를 버리거나 오른쪽 문자 j를 버려야 한다.이 둘 중 하나를 버렸을..

문제번역정수 배열 nums가 주어졌을 때, 배열을 2개의 부분 배열로 나누었을 때 두 배열의 합이 같으면 true를 반환해라.그렇지 않으면 false를 반환해라.접근 방법 및 소스 코드일단, 배열의 합이 홀수이면 그 어떤 경우의 수로 나누어도 두 부분배열의 합이 같아질 수 없다. 이 문제를 풀기 위해서는 부분배열의 합 = 전체 배열의 합 / 2 인지를 확인해야 한다.즉 nums에서 몇 개의 수를 골라서 전체 합 / 2를 만들 수 있는지 확인하면 된다. bool dp[10001];bool canPartition(int* nums, int numsSize) { memset(dp, 0, sizeof(dp)); int s=0; for(int i=0;i= t; j--) { d..

문제번역정수 n이 주어졌을때, n을 만들 수 있는 가장 적은 perfect squares 수의 개수를 구해라.perfect squares 란 어떤 정수의 제곱이 되는 정수를 말한다.예를 들어 1,4,9,16은 perfect squares 이지만, 3과 11은 아니다.접근 방법 및 소스 코드일단 어떤 숫자 i에 대해서, 이 수를 만들 수 있는 가장 적은 perfect squares 수의 최악의 경우는 1로만 이루어진 경우이다.즉, 숫자 i를 만들기 위해 1을 i번 쓰는 것이 가장 최악이다. 그 다음, i라는 숫자를 만들기 위해 어떤 제곱수 하나를 더 더한다고 생각해보자.k라는 제곱수가 있다고 해보자.k그 중 가장 작은 값을 저장하면 된다. int dp[10005];int min(int a, int b) {..

문제번역m by n 정수 배열 matrix가 주어진다.이때 matrix에서 가장 긴 증가하는 길의 길이를 반환해라.각 셀에서, 우리는 상하좌우로만 움직일 수 있다. 대각선으로 움직이거나 경계 밖으로 나갈 수는 없다.접근 방법 및 소스코드Hard 단계라서 처음에 조금 두려웠는데, 생각보다 쉽게 풀렸다.DP를 사용한 풀이로 접근하면 된다. 각 칸을 그래프의 노드로 보고 상하좌우 중 현재 값보다 큰 값을 갖는 노드로 이동한다.DFS를 통해 해당 칸에서 시작하는 최대 증가 경로 길이를 위해 자신을 기준으로 해 상하좌우 노드를 탐색한다.같은 칸의 결과를 재계산하지 않도록 DP를 통해 저장하고 재사용한다(메모이제이션 기법) 이를 코드로 구현하면 다음과 같이 작성할 수 있다. int m,n;int dr[4] = {-..

문제(영어) 문제(번역)너는 계단을 오르고 있다. 꼭대기에 다다르려면 n 걸음이 걸린다.한번에 1칸 또는 2칸 오를 수 있다. 정상에 다다르려면 몇가지 구별되는 방법이 있나요? 접근 방법문제를 보자마자 DP가 생각났다.정상이 1인 경우, 갈 수 있는 경우의 수는 1칸만 이동하는 1개 밖에 없다.정상이 2인 경우, 1칸 이동하고 1칸을 이동하거나 바로 2칸을 이동하는 경우가 존재한다.정상이 3인 경우, 1번째 칸에서 올라오거나 2번째 칸에서 올라올 수 밖에 없다. 즉, 정상 t에 오르기 위해서는 t-1에 오는 방법의 수와 t-2에 오는 방법의 수를 더하면 된다! 코드int climbStairs(int n) { int array[46] = {0}; array[0] = 0; array[1] =..