영우

백준 1890 문제 해결 경로의 개수를 세는 문제이다. 여러가지 접근 방법이 있을 수는 있겠지만 가장 먼저 든 생각은 역시 DFS나 BFS를 이용한 완전탐색이었다. 아래그림을 보자 완전탐색의 문제점 모든 칸의 값이 1일 경우에 각 행이나 열의 마지막 칸을 제외한 모든 칸에서 2개의 경우가 발생한다. 이 의미는 한칸 전진할때마다 2개의 가능성이 생기는 것이고 행과 열의 길이가 100이므로 100 * 100개의 칸에서 2개의 경우가 생긴다는 의미 이므로 최악의 경우에 약 2의 10000제곱을 계산해야한다. 해결 방안 결국 모든 경로를 계산해 최종적인 위치로 도달할 수 있는지의 방법으로는 불가능하다. 이를 개선하는 아이디어는 중복을 없애는 것이다. 위의 그림에서 1, 1위치에서 2, 2로 가는 방법을 생각해보..

DP에 대해 한번 정리를 하고 싶어 DP문제를 찾아서 풀어보았다. DP에 대한 개념부터 한번 정리하겠다. Dynamic Programming 동적계획법의 정의는 하나의 큰 문제를 여러개의 작은 문제로 나누어 해결하는 것이다. 나는 이러한 정의가 분할정복과 크게 차이가 없다고 느껴져, 반복되는 부분의 결과를 써 놓아 기억하고, 활용하기라고 생각하고있다. DP 예시 DP를 활용했을때 시간복잡도적으로 이득을 볼 수 있는 가장 대표적인 예시가 피보나치수열이다. 피보나치 수열은 F(0) = 0, F(1) = 1, F(N) = F(N-1)+F(N-2)인 수열이다 피보나치 수열 구현 코드 재귀를 통한 구현이다. 가장 기본적인 아이디어로, 위의 수식을 그대로 코드로 구현한 것을 확인할 수 있다. Top-Down방식으로..