전체 글 썸네일형 리스트형 11055번 11055번 - 가장 큰 증가하는 부분 수열 11053번인 가장 긴 증가하는 부분 수열과 똑같은 문제. D[N] = N번째 수를 포함하는 가장 큰 증가하는 부분 수열 이라는 점화식을 세운후, 값을 구한다.D[N] 은 항상 A[N] 이상의 값이 되어야 하므로, 캐시 조건을 D[n] != A[n] 이라고 하면 한번 이상 계산된 D[N] 값만 리턴된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include#include#include using namespace std;int A[1001];int D[1001];int N;int ans;int go(int n){ if (D[n] != A[n]) {.. 더보기 11053번 11053번 - 가장 긴 증가하는 부분 수열 ★★★★★다시 풀 문제★★★★★ D[N]을 N번째 수를 포함하는 가장 긴 증가하는 부분 수열의 길이 로 정의 했습니다.그렇기 때문에 N번째 수를 무조건 포함하고 1 ~ N-1 번째 수 각각에 대해서 for문을 돌렸습니다. 점화식 조건에 의해 D[N]은 최소 1이 되기 때문에 그렇게 초기화하였고, 2이상의 값에 대해서 캐시로 간주하고 리턴해주었습니다. 이렇게 하면 왜 안될까? 생각하면서 오래 고민했던 문제... 생각해보니 처음에 작성한 완전탐색 코드부터 문제가 있었던 것 같다. D의 값을 해당 범위 초기화하는 것과 전부 초기화 하는데 문제가 발생 -> Q&A에 질문 123456789101112131415161718192021222324252627282930313.. 더보기 2017-11-15 DP , 완전탐색 1463, 11726, 11727, 9095, 10844, 11057, 2193,9465,2156,11053 오늘 푼 문제 9문제 + 1문제 (고민중...) 더보기 2156번 2156번 - 포도주 시식 완전탐색 후 -> DP변환 완전 탐색 코드는 시간 초과 DP로 변환하는 과정에서 다양한 실수 실수 1. 기저 조건을 좀 더 명확하고 세세하게 정의 할 것. 빠뜨린 것이 없도록.=> 모든 인자에 대해서 확인할 것.이번 문제에서 n값만 확인하고 left 인자에 대해서는 기저 조건에서 빠뜨린 부분이 존재했다. 실수 2. 출력 값을 정확하게 확인할 것.=> 맨 마지막 잔을 먹을 때, 먹지 않을 때 다 비교해서 출력해야 하는데맨 마지막 잔은 항상 먹는 것으로 착각해서 처음에 drink(n,2) 값만 출력했었다. 실수 3. 인덱스 범위를 확실히 할 것.=> 이번 문제에서 포도잔을 0번이 아닌 1번 부터로 계산했는데 머릿속으로만 그렇게 하고실제 코드에서는 입력부터 1~n-1 까지만 받았었고.. 더보기 9465번 9465 - 스티커 처음에 완전탐색 -> 시간초과두번째 완전탐색을 DP로 변환 -> 실패세번째 완전탐색 DP변환 -> 성공 두번째 완전탐색을 DP로 변환할 때, 캐시는 2차원 배열이지만, 재귀함수는 sum값을 포함해서 넘겨주었다.왠지 될 것 같았지만 오류가 발생하였다. ==> 문제점은 재귀호출은 N값을 뒤에서부터 1까지 갔다가 다시 1부터 축적해가면서 캐시를 저장하는 것인데, 내가 작성한 코드는 N값을 뒤에서 1까지 갈 때 sum을 모두 저장하고 , 다시 앞에서부터 사용하기 때문에 생기는 문제.... 복잡하다.. 즉, DP란 뒤에서 앞으로 왔다가 앞에서 뒤로 가는 과정인데, 함수에 sum 인자를 넣어서 return 하니 앞에서 뒤,앞에서 뒤가 되었다. 나만 알아볼 수 있는 설명...ㅋㅋ ##재귀함수는 밑.. 더보기 2193번 2193번 - 이친수 완전탐색으로 푼 후 , DP로 전환해서 풀었다. 이 문제도 조심할 것은 int 범위를 넘어가서 long long 으로 해줘야 한다는 사실.항상 문제를 풀고 최대 범위의 N을 넣어서 확인하는 습관이 필요. D[N][L] = N자리, 끝 수가 L 인 이친수의 갯수 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include#include using namespace std;int ans;long long D[91][2]; long long go(int n,int num){ if (n == 1) { if (num == 0) { return 0; } else if (num ==.. 더보기 11057번 11057 - 오르막수 완전 탐색으로 구현후, 메모이제이션을 이용해 DP로 변환 앞서 풀어봤던 10844번과 매우 흡사한 문제 , 점화식이 똑같다.D[N][L] = N자릿수이고 끝 수가 L인 오르막 수의 갯수. 10844번과는 다르게 첫번째 수가 0이 될수 있고, 숫자가 갈수록 커지기만 하면 된다는 사실. 항상 나는 캐시 값(D[N][L]) 을 -1로 초기화 했었는데, 이번 문제의 경우 기존 값에 덧셈이 필요해서 0으로 초기화 시켰다.이 부분을 스스로 문제 풀면서 유의해야 할 것 같다.어떤 문제는 0으로 풀면 안될 때가 있고, -1로 풀면 안될 때가 있고... 유의하자! = 0; i--) { go(n - 1, i); } return; } int main(){ int N; cin >> N; for (int.. 더보기 10844번 10844번 - 쉬운 계단 수 DP를 이용해서 풀었다. 처음에 완전탐색으로 풀고, 시간초과로 인해 메모이제이션을 사용하는 DP로 풀게 됐다.이차원 DP를 이용해서D[N][L] = N자릿수, 마지막 숫자가 L인 쉬운 계단 수의 가짓수. 이 문제에서 발견한 나의 실수 2가지 1. 아직도 기저 사례에 대해서 완벽하게 하지 않고 풀었다.=> 이번 문제의 경우 N이 1일 때, 첫번째 자리에 0이 들어가면 안된다는 조건을 까먹고 자꾸 갯수가 +1 되는 것을 처음부터 생각하지 못함. 2. int값을 벗어나는 변수일 경우, long long 타입을 해줘야 하는데 그걸 잊었다. 삼성 기출 문제에서도 이런식으로 변수값을 벗어나는 문제가 있었는데그때도 틀렸던 점을 다시 잊고 틀렸다. 1234567891011121314151.. 더보기 이전 1 ··· 56 57 58 59 60 61 다음