모든 동적계획법 문제를 재귀적인 방법과 loop를 이용한 방법(반복적 동적계획법)으로 변환할 수 있나요.

  • Jaekwan
    Jaekwan

    안녕하세요.

    동적계획법에 대해서 공부를 하다가 재귀적인 방법+메모이제이션 vs for loop을 이용한 반복적 동적 계획법에 대해 궁금해서 질문을 드립니다.

    모든 동적 계획법 해법은 두 가지 방법 모두에 적용해서 풀 수 있는가? 인데요, 아래 문제의 경우 재귀적인 방법으로 해법이 알고리즘 문제 해결 전략에 나와 있는데 반복적 동적계획법으로도 풀 수 있는지 궁금합니다.
    https://algospot.com/judge/problem/read/JUMPGAME

    혹시 조언을 받을 수 있다면 부탁드립니다.


    4년 전
3개의 댓글이 있습니다.
  • Corea
    Corea

    풀이를 서술하지 않고 설명하기가 힘들 것 같아, 아래 스포일러로 묶어둡니다.

    책에는 어떤 풀이가 쓰여있는지 지금 확인할 수가 없네요. 우선, 동적계획법의 배열 정의를 다음과 같이 할 수 있습니다.

    • D(i, j) = i번째 줄의 j번째 칸에 도달할 수 있으면 1, 없으면 0

    해당 문제의 경우에는 항상 '오른쪽' 혹은 '아래쪽'으로만 이동할 수 있기 때문에, 2중 for loop를 이용하여 D(i, j)를 채울 수 있습니다. 이 때 두 가지 방법이 있습니다.

    1. D(i, j)를 채우기 위해 D(i-1, j), D(i-2, j), ... 와 D(i, j-1), D(i, j-2), ... 를 모두 확인하는 방법입니다. 이 경우 이전 칸의 숫자를 확인하여 (i, j)로 도달 할 수 있는지를 확인해야겠죠.
    2. D(i, j)에서 그 다음칸을 채우는 방법입니다. (i, j)칸의 숫자를 A라 하면, 만약 D(i, j)가 1인 경우 D(i+A, j)와 D(i, j+A)를 1로 만들어 줄 수 있겠죠.


    4년 전 link
  • Corea
    Corea

    만약 해당 문제를 해결하셨다면, 다른 사람의 코드를 통계 페이지에서 확인하실 수 있습니다. 다른 분들 중 반복적 방법으로 해결하신 분들도 많으니, 읽어보시면 도움이 될 것 같네요.


    4년 전 link
  • Jaekwan
    Jaekwan

    답변 감사합니다.
    배열에 대한 정의를 만드는 부분이 중요하군요. 정의를 만든 후 여러가지 방법으로 풀 수 있다는 부분에 큰 수 배우고 갑니다. 감사합니다.!


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.