Dynamic Programming

Dynamic Programming > 복잡한 문제를 subproblems로 쪼개 해결하고, 결과들을 저장해서, 동일한 문제를 풀 때 다시 계산하는 것을 피하는 방법 이때 두 가지 중요한 특성을 기억해야 한다. overaping subproblems Divide a

시간 제한: 2초메모리 제한: 128MBnaive 하게 풀면, 합 N을 만드는 정수 K개 중에서, 하나의 값은 미리 정해두고 나머지 (k-1)개의 조합을 구하는 방식으로 모든 경우의 수를 구할 수 있다. 이처럼, 문제를 쪼개서 풀 수가 있는데, sub-problems가

시간 제한: 2초메모리 제한: 256MB1~n의 최종 합은, 1 ~ m의 합과 m+1 ~ n의 합과 같다. 무작위의 m 중에서 최소를 만드는 m을 찾으면 된다. Naive 하게 풀면 굉장히 오래 걸리겠지만, 이 문제는 subproblem이 반복되기 때문에 Dynamic

시간 제한: 2초메모리 제한: 128 MBN이 짝수일 때만 타일을 채울 수 있다. 3xN 벽은 3x(N-2), 3x(N-4)... 을 조합해서 만들 수 있다. 3xN 벽에는, 3x(N-2), 3x(N-4).. 에서 볼 수 없었던 고유의 패턴이 생긴다.위의 내용을 조합하

시간 제한: 1초메모리 제한: 128MBNaive하게 풀면, 경찰 a, b에 순차적으로 사건을 맡겨보면서 recursive 하게 풀 수 있다. 이때, 시간 복잡도는 O(2^N)이다. 그러나, sup-problem이 반복적으로 나타나기 때문에, Dynamic Progra

시간 제한: 1초메모리 제한: 4MBN 줄의 k 번째 칸으로 끝나는 최댓값은, N-1 줄의 k-1, k, k+1 칸으로 끝나는 최대값과 조합하여 얻을 수 있다. 이렇게 재귀적으로 쪼개서 풀 수가 있는데, sub-problems이 반복된다. 따라서 Dynamic Prog

시간 제한: 2초메모리 제한: 128MBN 자리의 수가 k인 경우는 N-1자리의 수가 k-1, k+1인 경우로부터 만들어진다. 이렇게 문제를 쪼개서 풀 수가 있는데, sub-problems이 반복되기 때문에 Dynamic Programming 으로 풀 수 있을 것으로

시간 제한: 2초메모리 제한: 256MB답을 구하는 특별한 수식이 존재하지 않는다. 모든 칸을 조사해 보아야 하는데, 현재 칸에서의 최대는, 상하좌우 인접칸에서 시작할 때의 최대 + 1 이다. 즉, Sub-Problem이 반복되는 것이므로, Dynamic Program

문제 시간 제한: 2초 메모리 제한: 128MB Problem Analysis Algorithm Data Struture 결과 Other

시간 제한: 1초메모리 제한: 512MB현재 위치가 (r, c)일 때, 이전의 위치는 좌, 우, 그리고 위가 가능하다. 이렇게 (N, M)에서부터 (1,1)로 돌아가면서 recursive 하게 풀 수 있는데, sub-problems이 반복된다. 따라서, Dynamic

문제 시간 제한: 2초 메모리 제한: 512MB Problem Analysis Algorithm Data Structure 결과 other

시간 제한: 2초메모리 제한: 128MBNaive 하게 풀려면, 다음과 같이 DFS를 진행하면서, 각 node를 포함시킬 때와 포함시키지 않을 때를 모두 조사하여 가능한 최대를 구하면 된다. 그러나, 이 경우 시간 복잡도는 O(2^N)이다.이때, 각 node에서의 최대

시간 제한: 2초메모리 제한: 128MBNaive 하게 각 마을을 포함시키거나 빼면서 모든 경우를 조사하여 풀 수 있다. 그러나 시간 복잡도는 O(2^N)이다. 대신, xxoxA oxoxA 두 순서로 이루어진 경우가 존재할 때, 뒤에 A 순서는 중복되므로 다시 계산해