728x90 분류 전체보기144 [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. [SQL] 오랜 기간 보호한 동물(2) 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/59411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 핵심 LIMIT ROW_NUMBER() OVER (PARTITION BY ~ ORDER BY ~) TIMESTAMPDIFF(단위, START, END) 대여기간은 +1 잊지말기! 2. 코드(MySQL) # 입양을 간 동물 중 # 보호기간이 가장 길었던 동물 두마리의 아이디, 이름 # 보호기간 긴 순으로 내림차순 # 보호기간 = 입양일 - 보호시작일 with temp as ( sele.. 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. [그리디] Greedy Algorithm / 자연수 M/2개의 쌍 문제링크 https://www.codetree.ai/missions/8/problems/m2-pairs-of-natural-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 합들 중 최댓값이 최소가 되도록 하려면 가장 작은 수와 가장 큰 수를 순서대로 매칭하면 된다. 방법1(메모리초과 + 시간초과) 각 값들을 max_heap, min_heap에 넣어서 m // 2만큼 max_q + min_q의 조합하고 조합한 것 중 최대값을 고른다. 문제는 m이 10억이므로 최.. 2024. 2. 16. [DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 둘 중 하나 잘 고르기 문제링크 https://www.codetree.ai/missions/2/problems/choose-one-of-two-points?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 같은 상황 판별 및 점화식 i - 1번까지 파란색 카드의 수, 빨간색 카드의 수, 최대합이 같으면 같은 상황 dp에서 고려해야할 요소는 카드의 수와 합 총 카드의 수는 2n이므로 파란색 카드의 수 + 빨간색 카드의 수 = 2n이다. 그러므로 파란색 카드의 수만 dp에 기록해도 빨간색 카드의 수는 .. 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. 이전 1 2 3 4 5 6 7 8 ··· 24 다음 728x90 반응형