Algorithms/DP

https://www.acmicpc.net/problem/5015 5015번: ls 첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 www.acmicpc.net 1. Preview 시간 복잡도: p * n (= 패턴 길이 * 문자열 길이) 공간 복잡도: n 유형 : DP, 문자열(✋ 유형에는 없지만 문자열로 풀었다) 2. 초기 접근 방법 "문자열" 탐색으로 풀었다. '패턴'에 문자 중 '*'은 무엇이든 들어갈 수 있으니 무시하고, 알파벳 문자와 '.' 이 순서대로 있는지 파악했다. 1. 먼저 '*'을 기준으로 패턴을 split 한다. 2..

[초기 접근 방법] 당시 잘못된 접근법 → dp[i][j] : i번째 앱까지 중 j byte를 얻는데 소모되는 최소 cost 그러나 i의 범위는 100, j의 범위는 1천만이었기에 dp[][] 를 계산하게 되면 시간∙공간 복잡도가 매우 높다. 따라서, "비용"을 배낭의 크기로 생각하고 접근하는 것이 효율적이다. [생각] - dp 배열 정의 → dp[i][j] : i번째 앱까지 중 j 비용으로 얻을 수 있는 최대 byte 수 - 점화식 → dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - cost[i]] + memory[i]) 현재 앱을 계속 활성화 시켰을 때의 byte vs cost를 소모하면서 비활성화 시켰을 때의 byte 비교 Knapsack 풀이와 똑같았다. 4달 전쯤 풀..

[초기 접근 방법] 어떻게 풀어야 될 지 감이 잡히지 않아, O(N^4)으로 시간초과를 예상했지만 누적합도 복습할 겸 일단 누적합으로 제출했다. 누적합 → https://www.acmicpc.net/source/66884805 → https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java [생각] 처음부터 dp를 고려해야 겠다는 생각을 못한 문제.. 1. dp[i][j] : (i, j)에서 지을 수 있는 가장 큰 정사각형 목장 크기 2. 점화식 dp[i][j] = min(dp[i-1][j], dp[i][j-1]..

https://www.acmicpc.net/problem/2228 [초기 접근 방법] - 문제 이해 잘못 (2번 조건을 무시하고 '배열 구간 나누기'로 풀었다.) 그래도 이 때 문제 풀이를 적자면, 골드3 문제인데, dp[]가 1차원 배열이라니 뭔가 이상했어... [생각] 틀리고 '반례가 있을까?' 질문 게시판을 찾아보다가 접근이 아예 잘못된 것 같아서 구글링을 했다. 1. dp[i][j] : i개의 배열로, j개의 구간을 선택했을 때 구간합 최댓값 - 이 때 주의할 점은 배열을 이루는 수에는 음수도 있기에, -float('inf')로 초기화한다. 2. 점화식 1) 현재 구간을 유지하면서, i번째 값을 포함시키지 않았을 경우 dp[i][j] = max(dp[i][j], dp[i-1][j]) 2) 새로운 ..

[초기 접근 방법] 1. dp[i] : 합이 i가 되는 제곱수들의 최소 갯수 2. 점화식 dp[n] = min(dp[n], dp[n-제곱수] + 1) → 제곱수가 n보다 작을 때까지 비교 [생각] 문제에서 원하는 "합이 i가 되는 제곱수들의 최소 갯수"를 dp로 정의하고 풀면 되는 문제였어서, 쉽게 풀었던 것 같다. 아.. 시간 제한이 0.5초 이길래 시간초과가 나올까 봐 상수 시간복잡도까지 구했었다 [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N*sqrt(N)) → 1100만? # 공간복잡도 : O(n^2) # 참고 : - # 점화식을 세우자.. ㅎㅎ import math import sys input = sys.stdin.readline N = int(input()) # dp[i] : 합이..

https://www.acmicpc.net/problem/5557 [초기 접근 방법(o)] 1. 먼저 dp 메모제이션 할 배열을 정의하자 2. dp[i][j] : i번째 수까지 보았을 때, 수식을 만들어서 j가 나오는 경우의 수 - 0