728x90 전체 글145 [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. [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. 이전 1 ··· 3 4 5 6 7 8 9 ··· 25 다음 728x90 반응형