728x90 DP5 [DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 고대 보물 지도의 비밀 문제링크 https://www.codetree.ai/missions/2/problems/secret-of-ancient-treasure-map?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 동일한 상황에 대해서 생각 특정한 위치(행)까지의 합(값)과 마이너스의 개수(열)가 동일한 경우 같은 상황이다. 이 문제의 포인트는 '연속'이다. 그러므로 dp의 i번째를 볼 때는 반드시 dp의 i - 1번째를 봐야하고 또 주의해야할 점은 연속을 끊어내고 내 스스로 연속의 시작점이 될 .. 2024. 2. 17. [DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 올바른 등식 만들기 문제링크 https://www.codetree.ai/missions/2/problems/right-equality?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 DP의 정의 DP[i][j] 는 i번째 숫자를 반드시 선택했을 때 i번 숫자로 ± 하여 j를 만드는 경우의 수라고 하겠다. 따라서, 점화식은 DP[i][j] = DP[i - 1][j - nums[i]] + DP[i -1][j + nums[j]] M이 -20 부터 20이다. 그런데 '음수'는 인덱스로 접근이 어렵다... 2024. 2. 16. [DP] 호텔(Python) 문제링크 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 1. 핵심 유형2-1. item을 중복해서 사용 가능 + 유형3. weight를 특정할 수 없는 경우 최소 비용을 고르기 때문에 보통은 도시(item) / 고객수(weight) / 비용(value)로 고객수 i명을 확보하기 위한 비용j라고 dp[i][j]를 정의할 수 있다. 하지만 문제는, 고객의 수, 즉 weight가 '무한'이므로 고객수를 특정할 수 없다는 것이다. 따라서 유형3으.. 2024. 2. 16. [DP] 특정한 숫자를 만드는 DP 유형 1. 대표 유형 특정한 '숫자'를 만드는 DP 유형의 예시 동전(item)을 중복사용 가능 or 불가능할 때 특정 '원(weight)'을 만들기 위한 동전의 최소 '개수(val)' or '경우의 수' 가방에 '무게(weight)' 제한이 있는 상황에서 보석(item)의 무게와 가치가 주어졌을 때, 보석을 넣었을 때 얻을 수 있는 최대 '가치(val)' 퀘스트(item)를 수행했을 때 경험치와 걸리는 시간이 제시 되어 있을 때, 특정 '경험치(weight)' 이상을 얻기 위한 최소 '시간(val)' → 결론은 '동전'문제와 다 동일하고 표현만 달라진다고 생각할 수 있다. item → 2차원DP의 행을 의미 weight → 2차원DP의 열을 의미 value → DP에 들어갈 값 동전 원(금액) 개수(1이 d.. 2024. 2. 14. [DP] 아이템을 적절히 고르는 문제 / 동전 거슬러주기 문제링크 https://www.codetree.ai/missions/2/problems/coin-change?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 동전 거슬러주기 유형 중 같은 동전을 중복해서 줄 수 있는 유형 Top-down의 핵심은 점화식이며 내가 설정한 숫자들의 의미를 잘 부여야한다. ret = inf dpf(money) = min(ret, dpf(money - coin) + 1) where coin dp[0]은 impossible이 아니다. # -1: no.. 2024. 2. 5. 이전 1 다음 728x90 반응형