[알고리즘] 다이나믹 프로그래밍 + 문제풀이

다이나믹 프로그래밍 (= 동적계획법)

• 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 증가시킴
• 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 정답이 그것을 포함하는 큰 문제에서도 동일할 경우 사용 가능
• 메모제이션(=>한 번 구현한 결과를 메모해두고, 다시 호출하면 그대로 가져옴)
• 상향식(Bottom Up)방식

 

분할 정복 vs 다이나믹 프로그래밍

• 공통점 : 큰 문제를 작게 나눔
• 차이점 : 분할과 정복은 한 번 해결된 문제를 다시 처리하지 않으나, DP는 처리함]

 

문제 풀이 현황(기록용)

1	백준 24416번	브론즈1	O	20230209
2	백준 9095번	실버3	△	20230216
3	백준 1463번	실버3	O	20230216