Baekjoon(C++)
[백준] 1520번: 내리막 길 C++로 풀어보기
생각 처음에는 BFS나 DFS를 사용하면 될 것 같다고 생각했는데, 이것만 이용하면 시간 초과가 뜬다. 다이나믹 프로그래밍(DP)를 사용해야 되는데, 다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 다이나믹 프로그래밍을 사용하려면 세 가지 과정을 거쳐야 하는데, 바로 테이블 정의하기 점화식 찾기 초기값 정하기 이다. 출처: https://blog.encrypted.gg/974 [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍 안녕하세요, 이번 시간에는 다이나믹 프로그래밍을 다룹니다. 직전까지 막 재귀, 백트래킹, 정렬 이런 것들로 되게 고통받으셨을텐데 오늘껀 개념도 그렇게 어렵지 않고 구현 난이도도 낮아서 blog.encrypted.gg..
