DP 프로그래밍으로 알고리즘 이해하기 쉬워지는 법??

[도시백랑(ahn4685)]

삼성전자나 기타 SW업체때 코딩테스트때 DP를 많이 요구하는 거 같던데,
막상 써보니 시간이나 메모리 효율에도 상당히 좋다는건 알겠는데,
쉽게 하는 노하우 있을까요?
아니면 DP관련 책이라도 추천 좀

[머학원생(pjsdream)]

요즘 회사에서 하는 코딩테스트는 정보올림피아드, 대학생프로그래밍경시대회(ICPC)와 유사함

[머학원생(pjsdream)]

관련 사이트 백준, 알고스팟 같은데서 DP만 필터링해서 문제 연습해보시면 좋을듯

[머학원생(pjsdream)]

외국 문제풀이 사이트는 허벌나게 많음

[도시백랑(ahn4685)]

DP적으로 생각하는 유연한 사고방식을 가지려면 반복학습이 답인가요? 아니면 타고난 순발력같은건가요?

[머학원생(pjsdream)]

나는 경시대회만 초등학교때부터 해와서 몸에 익은지라.. 뭐라 설명드리기가 어렵네요

[머학원생(pjsdream)]

회사에선 웬 코딩테스트같은걸 한다고 사원분들 고생시킴 ㄷㄷ 경시대회 테크닉 익히는게 실무에 도움이 되려나

[아긔발(asceta)]

Dp 탑다운으로 푸는법 익혀보세요

[도시백랑(ahn4685)]

탑다운이나 바텀탑이나 프로그래밍 내용에 따라 적절한 선택을 해야 되는거 아닌가요? 문제마다 푸는 방법이 다르던데

[아긔발(asceta)]

Dp가 기존의 완전탐색에 메모라이징만 곁들인건데 그것만 캐치하면됨

[도시백랑(ahn4685)]

그 완전탐색을 줄이는게 dp니까 그 설계가 제일 어렵더군요

[아긔발(asceta)]

바텀업 탑다운 디피를 완전 마스터하면 자유자제로 바꿀수 있는데 탑다운이 훨씬 인간이 사고하기 편함 바텀업은 컴퓨터가 편하고.

[아긔발(asceta)]

디피를 처음 가르쳐줄때 보통 바텀업으로 점화식짜서 하는식으로 많이 가르쳐 주는데 그 바텀업방식에 빠져서 탑다운으로 하면쉬운문제에서 많이들 dp어렵다고 막힘

[도시백랑(ahn4685)]

그런데 대부분의 dp가 바텀 업 방식 아닌가요? 기존의 메모라이징된 것들 갖다써야되는 개념이니까

[아긔발(asceta)]

바텀업으로 풀리는 문제는 탑다운으로도 풀림 똑같이 ;; 사고하는 과정의 차이일뿐 탑다운도 메모라이징기반인데 다를게 없음. 재귀함수가 약해서 못하는 경우가 있는데 재귀함수 닉히는게 나중에 4차dp 7차dp나오고 조건 존나 복잡할때 바텀업으로 푸는거보다 훨씬쉬움

[아긔발(asceta)]

물론 바텀업이 더 쉬운 사람도 어딘가에 있겠지만 내주변에서 dp잘푸는 사람중에 한명도 못봄

[도시백랑(ahn4685)]

음.. 그렇군요 감사합니다. 탑다운으로 푸는 방법을 생각해봐야겠습니다. 탑다운으로 풀때 재귀함수를 이용하시나요? 순환문을 이용하시나요? 엄청나게 큰 수기준으로요

[아긔발(asceta)]

탑다운으로푼다 = 재귀로푼다 바텀업으로푼다 = 반복문으로푼다. 걍 이런식으로 생각하셈

[아긔발(asceta)]

또 하나의 차이는 탑다운은 최초의 캐쉬에 정답이 저장되고 바텀업은 마지막으로 계산한 캐쉬에 정답이 저장됨

[아긔발(asceta)]

아래꺼가 좀더 본질에 가깝긴한데 일단 위에처럼 생각해도 무방할듯

[도시백랑(ahn4685)]

재귀로 풀 경우 엄청나게 큰 수 기준으로 실행을 할 경우 메모리 참조때문에 실행시간 부분에서 차이가 나지는 않는지요?

[아긔발(asceta)]

오히려 탑다운이 더 빨리 풀리는 경우도 있음. 그런데 문제를 보면 탑다운, 바텀업 차이때문에 시간초과 걸리는 문제는 없음 dp로 구현만 하면

[아긔발(asceta)]

최적화를 생각하면 우선 탑다운으로 푼다음 바텀업으로 바꾸는 방식으로 진행하는게 역시 편함

[도시백랑(ahn4685)]

그럼 제가 설계를 잘못한거군요. 여태껏 바텀업으로 dp문제를 풀었는데, 탑다운으로 생각해보겠습니다 감사합니다!