728x90 코드트리38 [투포인터] 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. [그리디] Greedy Algorithm / 높은 숫자의 카드가 이기는 게임 문제링크 https://www.codetree.ai/missions/8/problems/a-high-number-of-cards-wins?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 내(A)가 상대편(B)의 카드를 알고 있는 상황. 이 상황에서 내가 상대편(B)를 최대한 이길려면 어떻게 해야하는가? B를 이기려면 B가 가진 카드보다 큰값을 제시해야한다. 우선 정렬은 하는게 훨씬 낫다. 정렬이 정답 유무에 미치지 않기 때문이다. 핵심!! B의 각 카드보다 크면서 내가 가진.. 2024. 2. 13. [그리디] Greedy Algorithm / 자동차 단일 거래 이익 최대화하기 2 [문제그림] 문제링크 https://www.codetree.ai/missions/8/problems/max-profit-of-single-car-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 정렬은 불가능하다. 왜냐하면 파는 시점과 사는 시점이 섞일 수는 없기 때문이다. 자동차를 파는 시점 기준(r)으로 그 전(0 ~ r - 1)에 언제 자동차를 사야했는가? 이익을 최대화하기 위해서는 사는 가격을 최소화해야한다. 즉, 파는 시점 기준 첫 날부터 팔기 전 날까지의 가격 .. 2024. 2. 13. [그리디] 최대 숫자 만들기 문제링크 https://www.codetree.ai/missions/8/problems/make-biggest-num?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 from functools import cmp_to_key 중 custom comparator만들기 # o1 앞, o2 뒤 # compare의 기본: 오름차순(o1 - o2 0: -1) # -1이 있는 if문이 현재의 (오름, 내림)차순을 나타냄. def c.. 2024. 2. 13. [BFS] 가중치가 동일한 그래프에서의 BFS / k개의 벽 없애기 문제링크 https://www.codetree.ai/missions/2/problems/remove-k-walls?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 핵심 시작점 → 도착점까지의 최소 이동거리 구하는 BFS 유형 벽 없애기 → 조합(백트래킹 or combintions) 사용하기 조합을 통해서 없앨 벽을 찾고 벽(1) > 벽아님(0)으로 변경한 뒤에 시작점에서 도착점까지의 거리를 구한다. 그 이후에 벽아님(0) > 벽(1) 으로 원상복구한다. 유사한 문제 https:/.. 2024. 2. 11. 이전 1 2 3 4 5 ··· 7 다음 728x90 반응형