코딩테스트 dp 공부 방향성

Question

안녕하세요 코딩테스트 준비하고있는 대학생입니다.알고리즘 문제 풀때 다른 유형들은 그래도 어느정도 풀다보니 익숙해져서 좀 풀리는것같습니다.근데 dp 동적프로그래밍 문제는 접근 방식도 좀 다양하기도하고 점화식 세우는 것 부터가 좀 힘든것같습니다고민 고민 하다 결국 답보고 푸는데 이렇게 판수박치기(?) 해서 유형 익히는게 맞나 싶기도하고 뭔가 이렇게 풀어서 유형익힌다해도문제 좀만 꼬아서 내면 풀기 힘들것같다는 생각이듭니다.dp 는 어떤식으로 공부하는것이 좋을까요?

삽살개발 · Answer

디피가 뭔가요

성실이 · Answer

알고리즘을 중요하게 보는 회사가 아니면 dp까지는 거의 안 나오니까 그쪽에 시간쓰는 것 보다는 기술 면접 준비에 좀 더 시간을 쓰는게 좋을 것 같아요.

막땅 · Answer

dp 풀이의 핵심은 탐색 공간을 어떻게 하면 MECE하게 잘 쪼개서 내가 필요한 정보만 들고 가냐입니다. 모든 dp 문제는 1) dp state(+ base case)를 정의하고2) dp transition을 찾아내면 끝납니다.여기서 2번이 어렵다고 생각하는 경우가 많은데, 사실은 1번이 정확하게 명확하게 정의되지 않아서 2번을 찾을 수 없는 거에요. https://atcoder.jp/contests/dp/tasks/dp_s간단한 예시로 이런 문제를 살펴볼게요.'어떤 1만 자리수를 가진 숫자가 주어졌을 때 그 숫자 이하의 수 중 99의 배수가 몇 개임?' 대충 이런 질문입니다. 나이브하게 접근하면 탐색 공간의 크기는 10^10000입니다. dp state를 떠올린다는 건 이 넓은 공간의 원소들을 적절히 공통된 특성으로 묶음을 지어서 탐색공간을 줄이는 작업입니다. 잠깐 고민을 해보세요. dp state(상태)를 정의할 때 한 가지 팁을 드리자면 정의를 자연어로 써보세요. 자연어로 잘 쓰여진다면 적절한 상태에요.이 문제의 경우dp[i][j][k] = 왼쪽부터 i번째 digit까지 살펴봤고 bound flag가 j일 때 D로 나눈 나머지가 k인 숫자의 개수 (dp[0][0][0]=1)이런 식으로 정의할 수 있습니다. 이 상태가 정의되고 나면 사실 점화식은 자연스럽게 나와요. i->i+1로 전이를 할 때 붙을 수 있는 숫자는 0-9 혹은 0-s[i]죠. 이때 나머지 k는 자연스럽게 전이가 되거든요.DP 연습의 핵심은 탐색 공간을 적절하게 잘 묶는 법을 연습하는 거에요. 위 문제에서는 D의 배수의 개수를 물었기 때문에 자연스럽게 D로 나눈 나머지가 상태공간이 되는 거죠. DP는 사실 너무 다양한 유형이 있어서 계속 맞으면서 배울 수 밖에 없어요. 다만 이런 핵심 원칙을 염두에 두고 공부를 하면 좀 더 자연스럽게 체화할 수 있지 않을까 싶네요.

코딩테스트 dp 공부 방향성

3개의 답변

Q&A 목록