728x90 PS91 [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. [그리디] Parametric Search / 폭탄 떨구기 문제링크 https://www.codetree.ai/missions/8/problems/drop-the-bomb?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 이분탐색의 대상이 되는 값 → R R로 결정할 수 있는 것은 바로 주어진 범위를 덮는 폭탄의 개수를 결정한다. 덮어야하는 포인트의 첫 시작은 반드시 폭탄의 범위에 들어가야 하므로 이를 폭탄의 시작점으로 생각한다. 폭탄의 범위에 대한 생각 (R ~ 폭탄 ~ R) 로 생각할수도 있지만 (폭탄 ~ 2 * R)로 생각할 수.. 2024. 2. 15. [그리디] Greedy Algorithm / 폭탄 해체 작업 문제링크 https://www.codetree.ai/missions/8/problems/the-bomb-dismantling?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 핵심: 시간제한이 감소하는 순으로 보며 해당 시간에 선택할 수 있는 폭탄 중 점수가 가장 높은 폭탄을 선택하는 것이 최선이다! 예시 시간제한이 가장 긴 것부터 선택했을 때 가장 최대 이익을 얻을 수 있다. 만약 time 1 때 9를 선택하면 다른 폭탄 8과 2는 선택할 수 없기 때문에 이익이 작아진다. .. 2024. 2. 15. [SQL] 자동차 대여 기록 별 대여 금액 구하기 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/151141 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 핵심 CASE-WHEN 사용 IF문 사용 IF(condition, true일 때 value, false일 때 value) TIMESTAMPDIFF TIMESTAMPDIFF(단위, 시작일, 끝일) 해설 temp는 CAR_RENTAL_COMPANY와 CAR_RENTAL_COMPANY_HISTORY를 inner join하고 '트럭'만 필터링한 후에DURATION_TYPE과 TOTAL_F.. 2024. 2. 15. [투포인터] Parametric Search / 최대 거리의 점 문제링크 https://www.codetree.ai/missions/8/problems/maximum-distance-point?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 서로 다른 n개의 점에 대해서 m개의 물건을 설치할 때, (설치된 물건 사이의 거리의 최솟값)의 최댓값을 찾아라! n이 최대 200,000이므로 완탐 등은 불가능!! 이분탐색 → 이분탐색으로 선택할거면, 어떤 변수가 이분탐색의 대상이 될 수 있는지에 대해서 고민을 해야한다. 누적합 그리디... 예시를.. 2024. 2. 14. 이전 1 2 3 4 5 6 7 ··· 16 다음 728x90 반응형