📌 문제 탐색하기N : 배열의 크기 ( 1 ≤ N ≤ 1,000 )A : 크기가 N인 배열 (0 ≤ Ai ≤ 100) 인덱스 i에 있는 숫자 A[i]는 최대 A[i]칸까지 오른쪽으로 점프 가능합니다.시작점은 0번 인덱스이고, 도착점은 N-1번 인덱스이며, 가장 오른쪽 칸에 도달하기 위한 최소 첨프 횟수를 구하는 것이 핵심입니다. 가능한 시간복잡도각 칸에서 가능한 점프 범위만큼 다음 칸들을 순회하면서 최소 점프 횟수를 갱신합니다.이 과정에서, 각 칸에서 최대 A[i]번 반복하게 되며, 문제 조건에 따라 A[i]는 최대 100입니다.외부 반복문은 0부터 N-1까지 순회하므로 O(N)내부 반복문은 각 i마다 최대 A[i]번 수행하므로, O(A[i])전체 시간복잡도는 O(N × K)이며, 여기서 K는 max(..

📌 문제 탐색하기N : N개의 줄matrix : N x 3 2차원 배열 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나이며 N개의 행에 걸쳐 세 개의 숫자가 주어집니다.각 행에서 한 숫자를 선택하며 아래로 내려가면서 숫자들의 합을 구하는 게임입니다.목표는 제시된 이동 규칙에 따라 내려오면서 얻을 수 있는 최대 점수와 최소 점수를 구하는 것입니다.가능한 시간복잡도조합각 행마다 최악의 경우 약 3가지의 선택지가 있을 수 있습니다.첫 번째 열이나 마지막 열에서는 선택지가 2가지이지만, 최악의 경우(즉, 항상 3가지 선택이 가능한 경우)를 가정합니다.첫 행에서 3가지 선택이 있고, 그 다음부터는 각 행마다 최대 3가지 선택이 있습니다.전체 경로의 개수는 3 × 3^(N-1)입니다.O(3^..

📌 문제 탐색하기집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 합니다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보는 것이 핵심입니다.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.가능한 시간복잡도조합모든 가능한 비용의 조합을 다 시도해야 하므로 가능한 조합은 3 * 2^(N-1)개로 매우 비효율적입니다.DP ( 동적계획법 )연속한 두 집은 같은 색을 칠할 수 없습니다.따라서, i번째 집을 빨간색으로 칠할 때, 이전 (i-1)번째 집은 초록 또는 파랑이어야 합니다.dp[i]..

📌 문제 탐색하기N : 세로길이M: 가로길이(1, 1) : 시작점(N, M) : 도착점오른쪽 또는 아래쪽 : 이동 가능한 방향1 : 자원 있음0 : 빈 땅 오른쪽과 아래쪽만 이동이 가능하며,경로 상에서 자원이 있는 칸의 합이 최대가 되도록 경로를 선택해야 하는 것이 핵심입니다.1≤N≤3001≤M≤300가능한 시간복잡도최대 300×300 = 90,000번의 연산으로 2초 안에 연산 가능합니다.알고리즘 선택오른쪽 또는 아래쪽으로만 이동 가능하므로, 각 칸에 도달하는 경로는 단순하게 결정되며, 누적 최대값을 저장하는 DP 방식으로 접근해 보겠습니다.📌 코드 설계하기문제의 Input을 받습니다.DP 테이블 초기화: 크기가 N×M인 2차원 배열 dp를 생성합니다.dp[0][0]에는 시작 위치의 값 matrix..

* 오늘의 학습 키워드 : 동적 계획법(Dynamic Programming, DP) - 복잡한 문제를 간단한 하위 문제로 분할하고, 그 하위 문제들을 각각 풀어서 전체 문제의 해답을 구하는 알고리즘핵심 개념메모이제이션(Memoization) : 이미 계산한 하위 문제의 결과를 메모리에 저장하여 동일한 하위 문제가 다시 계산될 때 저장된 값을 재사용.탑다운(Top - Dwon) 접근법 : 문제를 상위 문제에서 하위 문제로 재귀적으로 분할하면서 푸는 방식.바텀업(Bottom - Up) 접근법 : 문제를 하위 문제부터 풀어나가면서 점진적으로 상위 문제의 해를 구하는 방식, 일반적으로 반복문을 사용하며, 결과를 저장하기 위해 테이블(배열)을 사용함.* 예제 문제 : 피보나치 수열 - 재귀적 접근법 : 동일한 ..