목록다이나믹프로그래밍 (1)

수 많은 우문은 현답을 만든다

Recursion: Davis' Staircase

문제 순수하게 짜려고하면 대략 3중 for문이 나온다. 딱히 그래프 데이터도없고 좌우로 이동하는 내용도 없으니 DFS, BFS는 아닌듯 하다. 이럴땐 수학적으로 접근해 작은 단위부터 규칙을 찾는수밖에... 다이나믹 프로그래밍(Dynamic Programming): 목적: 최적 부분 구조를 갖춘 문제를 해결하기 위한 기법으로, 작은 부분 문제들의 해를 저장하고 활용하여 전체 문제의 해를 효율적으로 계산하는 것이 목적입니다. 작동 방식: 문제를 작은 부분 문제들로 나누고, 각 부분 문제에 대한 해를 계산하여 메모이제이션(기억화)하며, 이를 조합하여 전체 문제에 대한 해를 구합니다. Bottom-up 방식과 Top-down 방식이 있습니다. 풀이 # n=1 # 1 # n=2 # 11 # 2 # n=3 # 11..
코딩테스트/DP 2024. 1. 20. 03:24
이전 Prev 1 Next 다음