DP

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP dp[ i ] : 점프해 도착한 마지막 위치 i까지 가능한 최대 점프 횟수 i보다 앞에 있는 위치(j)들 中 해당 위치에서 점프해 i번째 위치로 올 수 있는 경우 중 최대 점프 가능 횟수 계산 for(int i = 1 ; i = i) { dp[i] = Math..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP (LDS) dp[ i ] : 마지막으로 고른 원소 위치가 i인 부분 수열 中 최장 감소 부분 수열의 길이 현재 위치의 값 arr[i]와 현재 위치보다 앞쪽 j에 있는 값들과 값을 비교해 현재 위치에 있는 값 arr[j]가 앞쪽에 있는 값 arr[i]보다 작다면 감소하는 부분 수열이므로 dp 배열을 갱신한다. for(int i = 0 ; i arr[i]) { dp[i] = M..

📖 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 💡 풀이 방식 • DP dp 배열을 만든다. (dp[i][j] : 해당 칸 (i, j)까지 스티커를 떼었을 때 얻을 수 있는 최대 점수) 2. 0번 열은 본인이 최대이므로 본인으로 초기화한다. 3. 1번 열은 특수처리한다. [0][1]은 왼쪽 아래 값과 본인 칸 값 더하기 [1][1]은 왼쪽 위쪽 값과 본인 칸 값 더하기 dp[0][1] = dp[1][0] + arr[0][1]; dp[1][1] = dp[0][0] + arr[1][1]; 4...

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DP . 입력받은 2차원 배열의 행이나 열의 크기가 1이라면 바로 1을 출력하고 종료하게 한다. (예외처리, TC 1) . 그게 아니라면, 2차원 배열을 (왼쪽 위 vs 왼쪽 vs 위쪽) 세 칸中 가장 작은 값 + 1을 해 갱신한다. . 새롭게 완성된 2차원 배열에서 최댓값을 찾아 출력한다. - dp 배열의 의미 : 현재 칸 (i, j)까지의 가장 긴 정사각형 길이 (여기서는 그냥 입력받은 2차원 배열 그대로 활용) - dp 점화식 : (왼쪽, 위, 왼쪽 위) 세 칸 中 최솟값 + ..

📖 문제  17626번: Four Squares라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1www.acmicpc.net  💡  풀이 방식• DP규칙을 찾아 점화식을 채운다.1 : 1^2                                           ⇒ 1개2 : 1^2 + 1^2                               ⇒ 2개3 : 1^2 + 1^2 + 1^2                   ⇒ 3개4 : 2^2                                           ⇒ 1개5 : 2^2 ..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP (Tabulation) - 각 칸에 적힌 수들 중 작은 값부터 순서대로 dp 값을 갱신해 저장한다. → 이를 위해 오름차순 정렬 필요 - 인접한 4칸에 대해 갱신을 진행한다. (단, 격자 범위 내에 있고, 현재 칸의 값보다 작은 경우) - dp 배열에서 최댓값을 찾는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 4..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP (Tabulation) . BST(1), BST(2)부터 시작해 BST(n) 구하기 - 서로 다른 BST 개수 = (왼쪽에 들어갈 수로 만들 수 있는 서로 다른 BST 개수) * (오른쪽에 들어갈 수로 만들 수 있는 서로 다른 BST 개수) → (왼쪽, 오른쪽 쌍) = (0, n-1), (1, n -2), (2, n-3), ... 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java...

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • DP 1. dp 배열의 값을 초기화한다. - 0번째 행의 값은 land 배열의 값 그대로 채운다. 2. 1 ~ (land.length - 1)행까지 dp 배열을 채운다. - 0번째 열인 경우, 이전 행의 1,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][0]을 더한다. - 1번째 열인 경우, 이전 행의 0,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][1]을 더한다. - 2번째 열인 경우, 이전 행의 0,1,..

📖 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 💡 풀이 방식 • DP 1. 2차원 배열을 입력받는다. 2. 2차원 배열 dp를 초기화한다. - dp[0][0] = arr[0][0] - 맨 위쪽 행은 arr 배열의 왼쪽 칸과 현재 칸의 값 中 작은 값으로 초기화 - 맨 왼쪽 열은 arr 배열의 위쪽 칸과 현재 칸의 값 中 작은 값으로 초기화 3. 나머지 칸은 현재 칸의 위쪽과 왼쪽 中 더 큰 값을 구한다. 그리고 이 값과 현재 칸의 값을 비교해 둘 中 더 작은 값으로 현재 칸의 값을 갱신한다. dp[i][j] = Math.min(Math.ma..