동적계획법은 사용하는 문제
126
7 asked
안녕하세요.
해당 네트워크 선 자르기 문제는 dfs 를 사용해서도 풀 수 있는 거 같습니다.
그래서 궁금한점이, 실제 코딩테스트를 볼때 어떤 문제 유형에 동적계획법을 적용하는게 좋은지 궁금합니다.
그리고 이 문제처럼 dfs, 동적계획법 둘 다 적용해서 풀 수 있는 문제라면 어떤 방법을 적용하는게 좋을지도 궁금합니다.
Answer 2
0
안녕하세요, 인프런 AI 인턴입니다. heewon221님,
동적 계획법(DP)과 DFS는 서로 다른 방법의 문제 해결 전략이며 어느 방법을 사용해야 할지는 문제의 특성에 따라 결정됩니다. 동적 계획법은 주로 “최적 부분구조”와 “중복되는 부분 문제”를 가진 문제를 해결할 때 유용합니다. 이는 말 그대로 큰 문제를 작은 문제로 나누어 푸는 방법입니다. 특히 최적화 문제에서 많이 사용됩니다.
반면에, DFS는 깊이 우선 탐색을 이용하여 문제를 해결합니다. 그래프 탐색이나 백트래킹 문제에서 유용하게 사용할 수 있습니다. DFS를 사용하면 모든 해결 가능성을 탐색하고, 특정 조건을 만족하는지를 확인할 수 있습니다.
선택의 기준은 여러 요소가 있을 수 있습니다:
- 문제에서 중복되는 부분 문제가 많고 이를 효율적으로 저장하면서 푸는 것이 필요하다면, 동적 계획법을 고려하는 것이 좋습니다.
- 문제 탐색 영역이 넓고 모든 경우의 수를 하나씩 확인해야 한다면 DFS가 유리할 수 있습니다.
- 그리고, 시간 복잡도나 공간 복잡도의 조건이 있을 때, 두 방법 중 어떤 것이 더 최적인지도 고려해야 합니다.
아래 기존 질문 및 답변을 참고하시면 도움이 될 것입니다:
1. 이 문제를 경로의 문제로 보고(최단거리) 푼다면..: 문제를 풀 때 DFS와 BFS 또는 동적 계획법(DP)을 선택하는 기준에 대한 설명입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
기존에 윈도우 10으로 잘 써왔는데 윈도우 11로 바꾸고 나서 채점이 안됩니다.
0
76
2
스택에서 ')'을 만나는 경우
0
78
3
문제가 어디있나요?
0
65
2
변수 or 함수명
0
61
1
침몰하는 타이타닉 문제 질문입니다
0
56
1
AA.py 책점 에러
0
57
1
오늘 구매했는데 파이썬 자료구조 궁금한거 있으면 답변이 잘 될까요.
0
111
2
5.동전분배하기 문제 밑에코드도 정답이될까요?
0
110
1
아나그램 비교 코드
0
116
2
AA.PY파일 복사 후 채점 진행할때 오류 발생합니다.
0
160
2
문제 링크가있나여?
0
147
2
채점기 Time Limit Exceeded 오류 문의
1
163
2
제 코드 좀 봐주세요
0
148
1
예외가 존재할 가능성?
0
97
1
3번이 안풀립니다
0
93
0
5번 틀림
0
114
0
오류원인?
0
98
0
리스트 선언
0
106
1
침몰하는 타이타닉(그리디) 문제 질문
0
109
1
알고리즘
0
69
1
코딩테스트
0
92
1
DFS 순서 질문드립니다.
0
126
2
left, right를 사용한 풀이법에 대한 질문입니다
0
91
1
섹션 9 Dynamic Programming (동적 계획법) 최대부분증가수열
0
116
2