DP

생각의 방향 DP 알고리즘 개념을 처음 공부하고 스스로 푼 문제! 바텀업(Bottom-up) 방법으로 푸는데 성공했다. 가장 까다로운 점은 '점화식 찾기' 였다. 어떻게 풀어야할지 고민하다가, 일단 경우의 수를 직접 적어가며(머릿속으로 상상하고 그리며) 점화식을 도출해냈다. 🔻 메모장에 적어가며 알아낸 점화식 더보기 n=2 -> 2개 n=3 [가로] [가로] [가로] -> 1 [세로] [세로] [가로] [가로] [세로] [세로] -> 3개 (1(=dp[1])+2(=dp[2])) n=4 [][][][] [][][][] -> [가로][가로][가로][가로] (all 가로) -> 1 -> [세로][세로][세로][세로] (all 세로) -> 짝수일 때 가능 1 => 2값 dp[2] 랑 동일. (거의 /2) -> ..

DP(Dynamic Programming) 💡 DP Dynamic Programming : 동적계획법 (동적 프로그래밍) 복잡한 문제를 재귀적인 방법으로 해결하는 알고리즘 설계 기법이다. 주로 ⭐최적화 문제에 많이 사용되며, 부분 문제의 해답을 저장해서 같은 계산의 반복을 피해 계산 시간을 줄여준다. 핵심 : 이전에 계산한 값을 다음 단계에서 써 먹는다는 사실! 핵심 : 문제의 재귀적인 구조를 찾아라! DP 알고리즘은 중복된 계산을 줄인다는 점에서 굉장히 효율적인 알고리즘이다. DP의 주요 방법 탑다운(Top-down) 접근법 (메모이제이션) : 재귀를 사용하여 큰 문제에서 작은 문제로 나아가며, 각 단계의 결과를 캐시(메모리)에 저장한다. 바텀업(Bottom-Up) 접근법 (타뷸레이션) : 반복문을 사..