Velog Velog

알고리즘 문제를 풀다 보면 동적계획법에 관련된 문제들을 많이 볼 수 있다. 옛날에 알고리즘 스터디할 때 하긴 했는데 제대로 이론을 안하고 문제만 풀어서 그런지 오랜만에 코딩을 하니까 기억이 안나서 다시 공부하고 정리를 하려 한다. 다이내믹 프로그래밍, 동적계획법 (Dynamic Programming, DP) 하나의 문제는 한 번만 풀도록 하는 알고리즘, 한번 푼 것을 여러 번 다시 풀지 않는 효율적인 알고리즘 크고 어려운 문제가 있을 때 큰 문제를 잘게 나누어 해결한 뒤에 전체의 답을 구하는 방법 최적화 문제를 해결하는 데 유용함 최적화 문제 : 문제의 답이 여러 개 존재하며 가장 좋은 결과를 찾아야 하는 문제 (ex. 최단경로 문제) 다이내믹 프로그래밍을 사용하는 이유 분할-정복 기법(divide-co..