dp[i] 나 dp[i][j] 이렇게 테이블 만들잖아요 여기 i,j에 대한 정보를 뭐로 해야 할지 모르겠는데 완전탐색에서부터 생각해보는건가요? dp테이블 만들 때 확실한 근거가 없으니까 제대로 분류 안되는 것 같고 분류 해도 시간초과 나고.... 어케하면 dp테이블을 잘 만들 수 있을까
[일반] 동적계획법 풀 때
익명(119.70)
2020-04-02 19:24
추천 0
댓글 7
다른 게시글
-
라인 코테 떨리네 [16][일반] 익명(14.37) | 20.04.02추천 0
-
간단한 코드 질문 [11][일반] 익명(119.70) | 20.04.02추천 0
-
C++는 숫자 적을때 자리수 구분해서 적는기능 없나? [4][일반] asdf(210.183) | 20.04.02추천 0
-
코드포스 1위 바탕화면 ㅇㅅㅇ [11][일반] 익명(106.102) | 20.04.02추천 12
-
PS를 즐기는 님들게 묻고싶습니다. [12][일반] 익명(14.6) | 20.04.02추천 0
-
함수로 벡터 초기화할 때 값이 복사가 되지 않으려면 어떻게 해야함? [5][질문] 익명(58.143) | 20.04.02추천 0
-
예제 이해가 안되는데 질문점 [1][일반] 익명(119.70) | 20.04.02추천 0
-
[질문] 음..이문제 동적계획법으로 풀수 있나요? [4][질문] devbelly(devbelly) | 20.04.02추천 0
-
파딱의 PS갤 운영방침 [1][일반] 시아닌(kimjg1119) | 20.04.02추천 6
-
카카오 내이버 삼성 라인이 목표인데 알고리즘 공부 범위 봐주라 [7][일반] 익명(124.58) | 20.04.02추천 0
점화식 세우는거 연습하셈
dp완전탐색 반복되는거 저장한다고 생각해보셈
완전탐색으로 코드 못짜는걸 dp코드 못짠다고 오해하지 마셈 dp는 일종의 스킬이라 생각하고 큰 틀은 완전탐색임
완탐으로는 당연히 짜지는데 dp테이블 설계하기 어려운 문제들이 있어서 그럼..완탐 방식을 알아도 테이블 짜는게 아예 다른 문제같음 가령 백준에 그림 교환이라는 문제가 완탐은 그냥 순열 쓰면 되지 근데 시간초과잖음 당연히
또 빌딩이라는 문제도 완탐으로 하면 o(n^2) 누구나 시간초과 나게 할 수 있지 완탐이랑 dp알고리즘 설계하는게 차원이 다르다니까 어려운 문제 갈수록
일단 기본문제들 ㅈㄴ 풀고 얘기하자.
실~골드문제 100문제 깨져보고 다시 오겠다