백준 #다이나믹 프로그래밍 #DP #Dynamic Programming 썸네일형 리스트형 Dynamic Programming 1: 기초 풀이 접근 (백준 10942, 17070번) Dynamic Programming 문제는 결국 점화식을 찾는 게 관건이다. 즉 현재 상태가 이전 상태에 어떻게 의존하는지, 어떤 관계 속에 놓여있는지 파악해야 한다. DP 문제 풀이 접근 방식은 다음과 같다. 1) 머리만 굴리지 말고 직접 손으로 써본다. 어차피 DP는 점화식을 찾는 문제고, 점화식은 곧 이전 항과 현재 항 사이 숨은 패턴을 찾는 일이다. 다행히 직접 반복해보면서 써보면 패턴을 발견하게 되는 경우가 대부분이다. 테스트 케이스나 (테스트 케이스가 적절하지 않다면) 직접 예시를 고안해서 4~5개 항 정도 추론해볼 것. 2) 문제 조건을 결정 짓는 핵심 정보는 무엇인가? 3) 현재 상태가 이전 상태에 어떻게 의존하는가? 4) DP 배열의 정보를 명확히 설정한다. 1차원인가? 2차원 또는 그 .. 2023. 3. 28. 13:43 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
