인프런 커뮤니티 질문&답변
작성한 질문수
동적계획법은 사용하는 문제
작성
·
92
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다. heewon221님,
동적 계획법(DP)과 DFS는 서로 다른 방법의 문제 해결 전략이며 어느 방법을 사용해야 할지는 문제의 특성에 따라 결정됩니다. 동적 계획법은 주로 “최적 부분구조”와 “중복되는 부분 문제”를 가진 문제를 해결할 때 유용합니다. 이는 말 그대로 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 특히 최적화 문제에서 많이 사용됩니다.
반면에, DFS는 깊이 우선 탐색을 이용하여 문제를 해결합니다. 그래프 탐색이나 백트래킹 문제에서 유용하게 사용할 수 있습니다. DFS를 사용하면 모든 해결 가능성을 탐색하고, 특정 조건을 만족하는지를 확인할 수 있습니다.
선택의 기준은 여러 요소가 있을 수 있습니다:
- 문제에서 중복되는 부분 문제가 많고 이를 효율적으로 저장하면서 푸는 것이 필요하다면, 동적 계획법을 고려하는 것이 좋습니다.
- 문제 탐색 영역이 넓고 모든 경우의 수를 하나씩 확인해야 한다면 DFS가 유리할 수 있습니다.
- 그리고, 시간 복잡도나 공간 복잡도의 조건이 있을 때, 두 방법 중 어떤 것이 더 최적인지도 고려해야 합니다.
아래 기존 질문 및 답변을 참고하시면 도움이 될 것입니다:
1. 이 문제를 경로의 문제로 보고(최단거리) 푼다면..: 문제를 풀 때 DFS와 BFS 또는 동적 계획법(DP)을 선택하는 기준에 대한 설명입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.