개발자 준비중인 블로그

더럽게 고생한 문제 중 하나다. 보통 가장 짧은 거리를 구하는 문제가 많으나 경우의 수를 붙여서 DP문제가 되었다. 우선 경로 자체를 DFS로 탐색하는 것이 맞다. DFS에서는 1. 해당 경로를 탐색하면 중복체크를 남긴다. 2. 해당 경로가 접근 가능하거나, 기존의 방법보다 이동거리가 짧다면, 누적거리를 기록하고 stack에 삽입한다. 3. 경로가 막히거나, 이미 탐색한 경로이며, 이동거리가 더 길다면 stack를 반환하여 다시 돌아간다. 이 3가지의 규칙을 따른다. 그리고 도착했다면 도착지점에 남겨진 누적거리를 체크하면 가장 빠른 길을 확인이 가능하다. 하지만 여기서는 가는 모든 경우의 수를 찾아야 한다. 그렇다면 여기서 DFS를 조금 변경하면 된다. 1. 해당 경로를 최초 탐색하면 중복체크를 남긴다...

경우의 수의 문제이다. 이런 경우의 수의 경우, 처음부터 마지막 값까지 가면서 누적되는 경우의 수를 더해가며 구하게 된다. 왜냐하면 1. 목표값까지의 경로값의 경우의 수는 불변하며, 2. 다음 목표값은 이전의 경로값과 중복되기 때문이다. 예를 들어보자 동전 1, 2, 5,가 있고 무한하게 주어진다고 가정하자 여기서 총합 2COIN을 만든다면 1+1, 2 이렇게 2개의 경우의 수가 나오게 되며 이는 COIN의 종류가 변하지 않는 이상 불변한다. (1) 여기서 COIN을 만든다면 1+1+1, 2+1 이렇게 2개의 경우의 수가 된다. 여기서 3COIN의 경우의 수를 자세히 보게 되면 2COIN을 만드는 경우의 수에 1COIN을 더한 값이 나온다. 즉 기존의 경우의 값을 참조하여 새로운 경우의 값을 구하는 것이..

n번째 피보나치 수를 구하는 문제이다. DP를 활용하여 풀면 수월하게 풀 수 있다. DP를 사용하기 위해 우선 점화식을 확인하면 $ F_0 = 0 $ $ F_1 = 1 $ $F_{(n)}=F_{(n-1)}+F_{(n-2)}$ $(n \in\{2,3,...\})$ 이며 각각 dp[0] = 0 dp[1] = 1 dp[n] = dp[n-1] + dp[n-2] 로 적용하여 변경하면 된다 n > count; vector dp; dp.push_back(0); dp.push_back(1); for (int i = 2 ; i

학부시절 알고리즘에서 제일 어려웠던 것으로 기억하는 알고리즘이다 지금도 알고리즘 문제를 보면 수많은 문제들이 있으며 여러 방법으로 응용이 가능한 방식이다. 1. 개요 Dynamic Programming (DP) 복잡한 문제를 간단하게 여러개의 문제로 나누어 이를 점화식으로 만들어 재귀구조로 문제를 해결하는 방식을 말한다. 주로 최적값 문제를 해결할 때에 사용한다. 가장 대표적인 문제를 뽑자면, 피보나치 수와 최단경로, 행렬 곱셉들이 있다. 문제를 여러게로 나누어 풀기 때문에 분할 정복과 비슷하지만 문제를 나누는 방식에서 그 차이가 들어난다. 분할정복의 경우 각 문제의 중복이 없게 분할한다. 즉, 각 문제들이 독립적으로 분리되어 있다. 하지만 동적 계획법의 경우는 문제 분할 시 중복이 존재하며, 이를 위해..