minhas2   4년 전

안녕하세요 동적프로그래밍을 공부하고있는 한 사람입니당..

문제를 해결하긴했는데 하는 내내 이게 백트랙킹같은 느낌이 들어서요..

사실 이론적으로는 동적프로그래밍과 백트랙킹을 구분할 수 있는데

구현에서의 다른점을 모르겠습니다..

이웃하는 집과 중복하는 색깔을 피하는 상황을 제외하고 모든 경우의수를 다 탐색한다는 점에선 백트랙킹같기도 하고요...

다른분들 푸는방식을 보니까 min함수를 이용해서 for문 하나로 심플하게 푸셨던데..

전 for문에 재귀호출까지 해버리니까 풀고나서도 찜찜해서 질문드립니다...!

동적프로그래밍엔 맞지않는 답일까요?..


아 그리고 코드보시고 이런식으로 구현하면 안되는데.. 싶은 거슬리는 문장(?)이 보이시면

피드백 환영(감사)합니다!


yukariko   4년 전

동적 계획법은 부분문제의 답으로 전체문제의 답을 구하는 알고리즘입니다. 이를 이용하면 모든 경우의수를 다 살펴보지 않아도 정의한 부분문제의 답들을 가지고 문제를 해결할 수 있습니다.

재귀에서는 메모이제이션을 통해 DP를 구현할 수 있습니다. 쉽게말해 부분문제의 답을 캐싱하여  구한 답을 재사용하는것이죠.

이코드는 가능한 모든경우를 탐색하여 답을 구합니다.

따라서 DP가 아닌 완전탐색, 백트래킹 코드라 할 수 있을것 같습니다.

minhas2   4년 전

감사합니다!

댓글을 작성하려면 로그인해야 합니다.