인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요 문제 접근 방법에 관해 질문있습니다.
작성
·
313
0
선생님, 가방문제(냅색 알고리즘) 접근 방법에 관해 질문이 있습니다.
문제를 보고 "dy[j-w]+v" 식을 어떤 접근 방법으로 만드셨나요?
선생님 설명과 식을 보고 나면 이해가 가는데 처음 보는 문제에서 dy식을 만들때 어떻게 접근해야할지 모르겠습니다.
나름의 팁이 있을까요?
퀴즈
동적 계획법(Dynamic Programming)의 핵심 아이디어는 무엇일까요?
문제를 가능한 모든 경우를 탐색하여 최적해를 찾습니다.
현재 상태에서 가장 좋은 선택만을 따라갑니다.
큰 문제를 작은 부분 문제로 나누어 해결하고 그 해답을 재사용합니다.
데이터를 정렬하여 검색 성능을 최적화합니다.
답변 2
2
안녕하세요^^
다이나믹 점화식을 만들어내는 능력을 기르는 특별한 팁은 없습니다.
백준에서 다이나믹 문제를 많이 풀어보는 방법밖에 없습니다.
처음 배울때는 다이나믹 내 주제 중 기초인
1) LIS(최대부분증가수열 스타일)
2) 냅색알고리즘(가방문제 스타일)
3) LCS(최대공통부분문자열 스타일)
위 3주제로 시작하면 됩니다. 아래는 백준 추천문제입니다.
백준 다이나믹 문제번호와 문제이름입니다.
1. 11053(가장 긴 증가하는 부분수열)
2. 1965(상자넣기)
3. 18353(병사배치하기)
4. 2579(계단오르기)
5. 2655(가장 높은 탑 쌓기)
6. 14430(자원캐기)
7. 1890(점프)
8. 2293(동전1)
9. 2294(동전2)
10. 12865(평범한 배낭)
11. 12920(평법한 배낭2)
12. 5582(공통부분문자열)
13. 9252(LCS2)
14. 15483(최소편집)
15. 1915(가장 큰 정사각형)
0
