해설 코드 질문있습니다

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-R

작성

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요, 큰돌님 강의 정말 잘 수강하고 있습니다.

다름이 아니라 해당문제에서 아래 go함수가 기존의 완탐 유형인 방문처리 / go / 방문처리 해제와는 조금 다르게 max가 중간에 들어가게 되어 헷갈리는 부분이 있어서 질문드립니다.

제가 이해한바로는

각 단계에서 가능한 모든 말을 이동시키고, 각 말이 도착한 위치에서 얻을 수 있는 점수를 계산.
그 중에서 최대 점수를 선택한 후, 다음 단계로 넘어가며 또다시 최대 점수를 선택하는 과정을 반복.
이렇게 마지막 주사위까지 처리된 후, 각 단계에서의 최대 점수를 더한 값이 최종적으로 출력.

되는 로직으로 이해하였는데, 혹시 제가 이해한대로 실행되는게 맞는지 궁금합니다.

int go(int here){

if(here == n) return 0;

int ret = 0;

for(int i = 0; i < 4; i++){

int temp_idx = mal[i];

int mal_idx = move(temp_idx, a[here]);

if(isMal(mal_idx, i)) continue;

mal[i] = mal_idx;

ret = max(ret, go(here + 1) + v[mal_idx]);

mal[i] = temp_idx;

}

//cout << "RET : " << ret << "\n";

return ret;

}

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 수현님 ㅎㅎ

네 잘 이해하셨습니다.

각 단계에서 가능한 모든 말을 이동시키고, 각 말이 도착한 위치에서 얻을 수 있는 점수를 계산.

말이 이동할 수 있는 경우의 수는 총 4자기 -> 이중 최대값을 계산해야 함. 따라서 그 경우의 수로 이동했을 때의 값을 더한 것 중 최대값이라는 구조가 되어야 하므로 -> ret = max(ret, go(here + 1) + v[mal_idx]);

그 중에서 최대 점수를 선택한 후, 다음 단계로 넘어가며 또다시 최대 점수를 선택하는 과정을 반복.
이렇게 마지막 주사위까지 처리된 후, 각 단계에서의 최대 점수를 더한 값이 최종적으로 출력.

-> mal[i] = temp_idx; 이동한 것을 원복해서 각 경우의 수가 독립적으로 만듬 -> go 함수가 재귀적으로 호출 -> if(here == n) return 0; -> 마지막에 기저사례에 걸리면 해당 경우의 수로 부터 얻어져온 것 중에서 최대값을 골라 -> 각 단계에서 최대 점수를 더하고 더한 값이 최종적으로 최대값이 출력이 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

수현님께서 말씀하신 부분에 관해 유사한 질문과 답변을 찾았습니다. 백트래킹을 이용한 최적화 및 이해 방식에 대한 다른 질문을 참고하시기 바랍니다.

아래는 백트래킹 및 재귀 호출 구조에 대한 다른 게시물들이며, 각 답변에서 관련 개념을 안내하고 있습니다.

유사한 질문들

전역변수를 사용하지 않은 백트랙킹 코드 질문
- 재귀 함수 및 백트래킹 조건에 관한 설명입니다. 코드의 흐름을 그림으로 그려보며 이해하는 방법 등을 자세히 설명하고 있습니다.
4-B 재귀함수 질문 있습니다
- 재귀 함수의 호출 순서와 로직에 대해 디버깅 코드와 함께 설명하고 있습니다. 디버깅을 통해 재귀 함수의 동작을 확인하는 방법을 강조합니다.
2240번 자두나무 질문있씁니다!
- 단계별로 문제를 풀이하며 최적의 결과를 찾는 구조를 설명합니다. 각 단계에서 최대 값을 선택하는 과정이 어떻게 구현되는지에 대한 설명이 포함되어 있습니다.

질문하신 코드는 백트래킹을 이용한 최적의 결과를 찾는 알고리즘으로 보입니다. 기본적인 로직은 다음과 같습니다.

기저 사례:
```
if(here == n) return 0;
```
here가 n과 같아지면 더 이상 이동할 단계가 없으므로 0을 반환합니다.
모든 경우 탐색:
```
for(int i = 0; i < 4; i++) {
```
각 말(mal)에 대해 가능한 모든 이동을 시도합니다.
이동 후 처리:
```
ret = max(ret, go(here + 1) + v[mal_idx]);
```
이동 후 얻을 수 있는 점수를 계산하여 최대 값을 갱신합니다.
상태 복원:
```
mal[i] = temp_idx;
```
다음 반복문을 위해 이전 상태로 복원합니다.

질문자님의 이해가 전반적으로 맞습니다. 각 단계에서 말의 최적의 이동을 계산하고, 그 이동 이후의 상태에서 다시 최대 점수를 계산합니다. 마지막 주사위까지 이 과정을 반복하며 각 단계에서 얻은 최대 점수의 합을 구하게 됩니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

해설 코드 질문있습니다

유사한 질문들