목록DP (1)

WonniOS

[코드트리] DP 쉽게 이해하기 (개념부터 구현까지 총정리)

알고리즘을 공부하다 보면 "이 문제는 DP로 풀어야 합니다"라는 말을 자주 듣게 됩니다. 하지만 처음에는 DP가 굉장히 어렵고 추상적으로 느껴졌습니다. 저 역시 처음에는 "그냥 규칙 찾고 배열에 저장하는 거 아닌가?" 정도로만 이해했었습니다.이번 글에서는 제가 DP를 이해하게 된 방식으로, 최대한 쉽게 설명해보려고 합니다.DP란 무엇일까?DP(Dynamic Programming, 동적 계획법)는 "이미 계산한 결과를 저장해두고 다시 사용하는 방법" 입니다.예를 들어 피보나치 수열을 생각해보겠습니다.F(5)= F(4) + F(3)F(4)= F(3) + F(2)F(3)= F(2) + F(1)이렇게 재귀로 계산하면 F(3)이나 F(2)를 여러 번 계산하게 됩니다.즉,같은 계산을 반복한다.불필요한 연산이 많아진..
Algorithm 2026. 6. 15. 10:09
이전 Prev 1 Next 다음