1차원 다이나믹을 쓸 때 vs 2차원 다이나믹을 쓸 때

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

9. 가방문제(냅색 알고리즘 : Knapsack algorithm)

작성

434

선생님 질문입니다.

사실 너무 많은 알고리즘과 문제가 있어서 질문자체의 범위가 큰 질문일수도 있지만, 질문 그대로 문제에 대해서 1차원으로 접근할건지 2차원으로 접근할건지에 대한 판단이 문제를 보고 잘 안섭니다.

좋은 팁이 있을까요?

(다른질문을 보니 물론 많이 풀어보면서 감을 익힐 수도 있겠지만 조언을 듣고싶습니다.)

python 코딩-테스트

답변 1

김태원

지식공유자

안녕하세요^^

네. 사실 정확하게 도식화 하는게 어렵습니다. 결국 문제를 많이 풀어본 경험에 의한 감각밖에는 저도 어떻게 말하기기 어렵네요. 저는 정보올림피아드를 해서 다이나믹을 그래도 꽤 많이 풀어봤습니다. 한 150개 이상 풀어본 것 같은데요. 이 경험으로 생각해 보면 거의 대부분이 2차원 다이나믹인 것 같습니다.

제가 말씀드리고 싶은 것은 다이나믹은 대부분 2차원 다이나믹인데 1차원은 최대부분증가수열(LIS) 스타일, 냅색스타일, 그리고 일부 경우의 수를 1차원 배열에서 하는 것 정도 빼고는 대부분 2차원 배열에서 행번호와 열번호에 의미를 부여하고 다이나믹으로 해결하는 문제들이었습니다. 그래서 LIS, 냅색, 일부 경우의 수(이건 경험적으로 판단)가 아니면 그냥 2차원이겠거니 하고 접근하면 좋을 것 같습니다.

Alex

질문자

감사합니다! 오늘도 좋은 하루 되시길 바랍니다!

인프런 커뮤니티 질문&답변

1차원 다이나믹을 쓸 때 vs 2차원 다이나믹을 쓸 때