백사니

해당 문제는 왼쪽 위에서 오른쪽 아래까지 갈 수 있는 경우의 수를 구하는 문제로 map의 사이즈가 최대 100 * 100으로 생각보다 크다는 것이 핵심이다. m*n이 최대 1만까지 나오므로 dfs나 bfs를 사용한다면 시간초과에 걸릴 수 있는 문제이다. 때문에 점점 문제를 줄여나가는 동적 프로그래밍(DP)를 사용해서 풀어야한다. 동적프로그래밍에 대한 자세한 설명은 아래 링크에 정리해놓았다. DP(Dynamic Programming) 동적 프로그래밍동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 최적화 기법이다. 이는 같은 상황이 반복되는 경우에 매우 효과적이다. 동적 프로그래밍은 똑같은 하위 문제를 여러번 계산jinho082008.tistory.com 문제 핵심 문제에서는 1,1에서 시..

동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 최적화 기법이다. 이는 같은 상황이 반복되는 경우에 매우 효과적이다. 동적 프로그래밍은 똑같은 하위 문제를 여러번 계산하지 않기 위해 결과를 저장해두고 이를 재활용하는 방식으로 진행된다. 동적 프로그래밍의 간단한 예시로 피보나치 수열이 있다.피보나치 수열의 경우 재귀함수로 간단하게 구현할 수 있지만 이렇게 될 경우 값을 구하기 위해 이전에 했던 계산을 다시 하면서 비효율적으로 동작한다.int fib(int n) { if (n n이 만약 10이라면 값을 구하기 위해 9,8일때의 값을 구해야한다. 또한 이를 구하기 위해선 각각8,7 7,6을 구해야한다. 즉 n값이 커질수록 연산수가 급격하게 늘어난다.하지만 이러한 반복 과정을 저장해서 사용..

해당 문제는 꼭대기에서 바닥까지 갈 수 있는 경로 중 숫자의 합이 가장 큰 경우를 찾는 문제로 동적 프로그래밍으로 문제를 부분으로 나누어서 해결하면 쉽게 풀 수 있다. 해당 문제는 위에서 아래로 내려오는 방법도 있지만 아래에서 위로 올라가며 마지막에 값 한개만 남기는 방법도 있다.  동적 프로그래밍에 대해 궁금하면 아래 링크에 정리해두었다. DP(Dynamic Programming) 동적 프로그래밍동적 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 푸는 최적화 기법이다. 이는 같은 상황이 반복되는 경우에 매우 효과적이다. 동적 프로그래밍은 똑같은 하위 문제를 여러번 계산jinho082008.tistory.com 위에서 아래로 내려오는 방법#include #include #include using ..