Dynamic Programming

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

LIS(Longest Increasing Subsequence) arr = \[ 1, 4, 2, 3, 6 ] 이런 수열에서 어떻게 하면 LIS를 찾을 수 있을까? Naive 1 0부터 순서대로 조사하여, 매번 arr[i]를 포함하거나, 포함하지 않는 경로를 각각 살펴

Longest Common Subsequence (LCS) 개념 Longest Common Subsequence (최장 공통 부분 수열) 두 문자열에서 문자의 상대적인 순서를 유지하면서 공통으로 만들 수 있는 가장 긴 Subsequence (부분 수열)의 길이를 구

시간 제한: 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 순서는 중복되므로 다시 계산해

Backtracking을 통해 모든 경우의 수를 조사하면 최적의 방법을 찾을 수 있다.그러나 최악의 경우 시간복잡도가 O(N!)이므로 불가능하다.문제를 자세히 살펴보면,(1번,0원)->(3번,5원)->(다음 조사)(1번, 0원)->(2번,4원)->(3번,5원)->(다음

DFS Bruteforce로 전부 처리하는 경우 시간복잡도가 상당할 것이다.이때, bruteforce중에 반복적으로 조사하는 부분이 생기는 걸 확인할 수 있다.12원->10원->8원->(다음)12원->11원->8원->(다음)결국 DP-tabulation으로 풀 수 있다

bruteforce로 완전탐색하면 풀린다. 다만 시간 복잡도가 문제이다.M(목표 메모리)을 60 확보해야할 때, 아래와 같이 반복되는 조사 대상이 생긴다.60->50->30->(다음)60->40->30->(다음)따라서, DP를 사용할 수 있을 것 같다.문제는 M이 10

5명이 주어졌다고 가정해보자.1번부터 누구의 선물을 받을 지 순서대로 정해보자.5->4->2->..4->5->2->..이후 상황은 같기 때문에 DP로 풀 수 있지 않을까 했다.다만, 이 경우엔 bitmask가 필요한데 10^6 명을 체크해야 해서 쉽지 않다.여기서 막혔

Naive 하게 풀면 (N-1)! 순서대로 연산을 시도해보는 것이다.그러나 이는 시간 복잡도에 문제가 있다.그러나 이 Naive한 케이스들 실행하는 과정을 잘 살펴보면,결국 마지막엔 왼쪽 행렬과 오른쪽 행렬을 곱하는 게 마지막이다.그럼 왼쪽 행렬은 어디서 왔나 생각해보

Recursive 함수로 풀면 쉽게 풀 수 있다.이때, 반복되는 계산이 존재할 것이므로, dp를 사용하면 된다.피보나치에서 사용하는 기본적인 발상과 거의 같다.다만, 큰 범위 내에서 듬성듬성 필요한 부분만 저장하고 재활용 해야하는 상황이므로, 단순히 Array를 쓰기보

처음엔 Greedy를 생각해보았다.큰 수를 최대한 많이 넣으면 되지 않을까?한번 생각해보자.그러나 아래와 같은 경우 Greedy로 풀 수 없다.13, 5, 4, 1 6413 13 13 13 5 5 1 113 13 13 13 4 4 4그러

주어진 요리의 만족도(satisfaction) 배열을 활용해서, 만족도 $\\times$ 조리 시간(순서)의 총합이 최대가 되도록 요리 순서를 정하거나 특정 요리를 포기하는 문제.정렬의 필요성: 만족도가 큰 요리일수록 나중(후반)에 조리해야 시간 곱셈(Time Mult