728x90 PS/코드트리38 [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. [그리디] 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. [그리디] 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. 이전 1 2 3 4 ··· 7 다음 728x90 반응형