다이나믹 프로그래밍 알고리즘에 대해 질문드립니다.
348
작성한 질문수 27
문제를 보고 이 문제가 dp문제다라는 것을 어떻게 알고 진행하는지 궁금합니다. 다양한 알고리즘이 존재하는데, 따로 문제에서 dp문제라는 주목할만한 힌트가 있나요???
답변 1
1
안녕하세요^^
문제를 딱 보고 다이나믹이다라고 판단할 수 있는 문제는 LIS, LCS, 냅색 등과 같은 유명한 다이나믹 유형이 아니면 판단하기 힘듭니다. 다이나믹 문제를 많이 풀어보면서 오는 감각이 있습니다.
다이나믹을 잘 하려면 일단은 다이나믹 이외의 다른 알고리즘을 이용해 문제를 푸는 능력이 뛰어나야 합니다. 그래야 어떤 문제를 만났을 때 다른 알고리즘을 적용해보고 안되겠다 싶을 때 다이나믹을 생각해보는 방식입니다.
일단 n제한이 커서 효율성을 생각해야 되고, 다른 알고리즘으로는 가능성이 없어보이면 다이나믹을 생각해보면서 점화식이 나올 수 있는지 연구해봅니다.
비밀번호
0
67
1
과일 가져가기 이러한 경우에는 반례가 생기지 않나요?
0
163
2
cpu 스케줄링
0
107
2
외부 문제 질문
0
122
2
가장 많이 사용된 회의실
0
118
2
심사위원 문제 시간복잡도 질문
0
127
1
현관문 출입순서
0
98
1
미로의 최단거리 통로
0
74
1
집으로 이동 문제 코드
0
125
1
채점 사이트 개설
0
161
2
송아지를 잡자
1
110
1
다익스트라 + 환승횟수
0
135
2
문제풀이 해설 질문입니다.
0
124
2
"이동 횟수" 문제가 변형된다면?
0
156
2
예제 3번의 정답이 이해가 되지 않아요 선생님 ㅜㅜ
0
248
1
"비밀번호" 문제 확인 부탁드립니다!
0
171
1
최대 길이 연속수열 질문
0
193
1
잃어버린 강아지 문제 count 관련 질문있습니다
0
204
1
바둑대회 질문입니당
0
222
1
5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다
0
311
1
알파코드 풀이질문입니다
0
218
1
7번 비밀 번호 문제에 시간복잡도가 궁금합니다!
0
164
1
혹시 이렇게 작성해도 괜찮나요?
0
287
2
문제풀이 확인 부탁드립니다.
0
245
1