해나의 컴공생존기

미로찾기는 BFS에서 많이 나오는 문제이다. 미로찾기 까지는 성공했지만,,, 이 문제의 핵심인 최단경로구하는거에서 막혔다.. 가다가 이길이 아닐때 어떻게 거리를 구하지...??? 맞는일인지 아닌지 어떻게 알고 거리를 update하지?? 이 것에 대한 해결방안으로 방문했는지 체크하는 배열에 이 자리까지 오는데 걸린 거리를 저장하는걸로 하였다. 다이나믹 프로그래밍..을 이용했다고 볼 수 있을 것 같다. #include #include #include #include using namespace std; int check[100][100]; int n, m; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; string a[100]; int main() { ios::..

알고리즘시간에 배운 동적프로그래밍 문제를 하나 가져와봤다. 의사코드를 한번 보면 재귀호출은 들어온 숫자(n)이 1이나 2가 아니라면 n-1과 n-2를 인자로 재귀호출하여 더해준다. 만약 6이 들어온다면 f(6) → f(5) + f(4) → ( f(4)+f(3) ) + ( f(3)+f(2) ) → ( ( f(3)+f(2) ) + ( f(2)+f(1) ) ) + ( ( f(2)+f(1) )+1 ) → ( ( ( f(2)+f(1) )+1 ) + ( 1+1 ) ) + ( (1+1 )+1 ) → ( ( ( 1+1 )+1 ) + 2 ) + 3 → 8 동적프로그래밍 의사코드를 보면 인자로 들어온 n만큼 배열을 만들어서 인덱스 1,2, 에는 1을 넣어주고 나머지 인덱스에는 앞에 두자리를 더한 값을 넣어준다. 하지만 '..