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

안녕하세요 ㅎㅎ

먼저 모든 경우의 수 중 가장 최고치를 찾습니다.

먼저 도착했다고 해서 최고일 수는 없습니다.

예를 들어 a -> b -> c 보다

a -> d -> e -> c가 더 최대겠죠.

    check[y][x] = 1;
    int value = (int)b[y][x] - '0';
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }
    check[y][x] = 0;

• 이미 도착했지만, 여러 곳을 순회하면서 방문할 수 있는 경우가 있다면 ,

• 이때 해당 memo 는 갱신되어야 하는 게 아닌가요??

네 맞습니다. 저 코드가 의미하는게 바로 그겁니다.

지금 제가 a -> {b, c} -> ...로 간다고 했을 때

a -> b -> d 로 가는게 있고

a -> c -> e -> d 로 가는 경우의 수가 있을 겁니다.

이 때 ret은 그 경우의 수 중 가장 max값이 담기게 되는 것입니다.

현재 갈 수 있는 방향으로 파생된 경우의 수중 max값이 down()함수에 쌓여서 + 1이 되서 최종 ret이 됩니다.

• 아니면 빨간색 코드에서 이미 여러 경우의 수를 확인했다는 것을 증명하는 것인가요?

   

-> 정확히는 제가 드린 앞의 코드입니다. 현재로서 갈 수 있는 모든 경우의 수중 최대값이라는 의미입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요 ㅎㅎ

먼저 모든 경우의 수 중 가장 최고치를 찾습니다.

먼저 도착했다고 해서 최고일 수는 없습니다.

예를 들어 a -> b -> c 보다

a -> d -> e -> c가 더 최대겠죠.

    check[y][x] = 1;
    int value = (int)b[y][x] - '0';
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i] * value;
        int nx = x + dx[i] * value;
        ret= max(ret,down(ny,nx) + 1);
    }
    check[y][x] = 0;

• 이미 도착했지만, 여러 곳을 순회하면서 방문할 수 있는 경우가 있다면 ,

• 이때 해당 memo 는 갱신되어야 하는 게 아닌가요??

네 맞습니다. 저 코드가 의미하는게 바로 그겁니다.

지금 제가 a -> {b, c} -> ...로 간다고 했을 때

a -> b -> d 로 가는게 있고

a -> c -> e -> d 로 가는 경우의 수가 있을 겁니다.

이 때 ret은 그 경우의 수 중 가장 max값이 담기게 되는 것입니다.

현재 갈 수 있는 방향으로 파생된 경우의 수중 max값이 down()함수에 쌓여서 + 1이 되서 최종 ret이 됩니다.

• 아니면 빨간색 코드에서 이미 여러 경우의 수를 확인했다는 것을 증명하는 것인가요?

   

-> 정확히는 제가 드린 앞의 코드입니다. 현재로서 갈 수 있는 모든 경우의 수중 최대값이라는 의미입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 김원태님, 질문 주셔서 감사합니다. 공유해주신 질문과 관련 있는 유사한 문제를 있었으며, 그에 대한 답변을 요약하여 드리겠습니다.

질문에 대한 해결의 핵심은 재귀적 DFS와 메모이제이션을 활용하여 최적의 결과를 찾는 과정에 있습니다. 이런 문제 해결 방법을 이해하기 위해 몇 가지 주요 개념들을 살펴봅시다.

핵심 개념

1. 메모이제이션:

   • 메모이제이션은 이미 계산한 결과를 저장하여 나중에 동일한 결과를 재사용할 수 있도록 하는 기법입니다. 이는 계산 속도를 높이는 데 도움을 주며, 불필요한 중복 연산을 피합니다.
     
   • 이미 도착한 인덱스가 왜 최대값이 되는지는, 해당 인덱스에 대해 이미 최적의 결과를 계산하고 있기 때문입니다. 즉, 메모 배열에서 이미 저장된 값은 해당 지점까지의 최적의 이동 경로 결과를 나타내고 있습니다.
     

2. DFS와 백트래킹:

   • 각 노드(혹은 위치)에서 갈 수 있는 모든 경로를 탐색하고, 그 경로들 중 최적의 결과를 찾습니다.
     
   • 여러 경우의 수를 확인한 후, 메모이제이션 배열(memo)에 저장하여 동일한 노드 재방문 간의 계산을 줄입니다.
     

3. 순환(cycle) 및 경계 조건:

   • 이미지에서 설명된 것과 같이, DFS에서 경계 밖으로 나가거나, 특정 조건(H를 만나면)을 만족하면 검사를 종료합니다.
     
   • 이를 통해 경로의 유효성을 검증하며, 무한 루프를 방지합니다.
     

관련된 질문 및 답변, 유사한 사례는 링크를 통해 더 깊이 있는 이해를 도울 수 있습니다. 예를 들어, 잘못된 코드에서 출발하여 최적화하는 과정을 설명한 7-c 코드 질문입니다는 코드의 재귀적 흐름과 메모이제이션의 활용법을 익히는 데 도움이 될 것입니다.

위의 설명이 도움이 되었기를 바랍니다. 각 단계에서 최적의 경로를 탐색하고, 그 결과를 적절히 저장 및 활용하는 방법을 이해하시면, 이 유형의 문제를 해결하는 데 많은 도움이 될 것입니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.

현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.