4-F 1062번 문제 답안코드에서 이해가 가지 않는 부분이 있습... - 인프런

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

4-F

4-F 1062번 문제 답안코드에서 이해가 가지 않는 부분이 있습니다.

작성

int go(int index, int k, int mask) {
    if (k < 0) return 0;
    if (index == 26) return count(mask); 
    int ret = go(index+1, k-1, mask | (1 << index)); 
    if (index != 'a'-'a' && index != 'n'-'a' && index != 't'-'a' && index != 'i'-'a' && index != 'c'-'a') {
        ret = max(ret, go(index+1, k, mask)); 
    }
    return ret;
}

답안에서 go 함수의 기저사례 처리 부분이 이해가 가지 않습니다.

if (k < 0) return 0;
if (index == 26) return count(mask);

이렇게 k < 0 일때는 0을 리턴해주고 index==26일때 읽을 수 있는 단어갯수를 리턴해주고 있는데요,

문제의 조건이 K개의 글자를 가르쳤을때 읽을 수 있는 단어의 갯수의 최대값을 구하는 것인데

위와 같이 index==26 일때 count(mask)를 리턴해주면 k개를 모두 고르지 않은, 예를 들어 k-2만을 고른, 상태일때 읽을 수 있는 단어를 리턴해주게 되지 않나요?

저는 그래서

if(k==0) return count(mask);
if(index == 26 && k > 0 ) return 0;

이렇게 k==0일때 (즉, k가지를 모두 골랐을때) count(mask)로 읽을 수 있는 단어의 갯수를 리턴해주고
index가 끝까지 갔음에도 불구하고 k가 아직 0이 안되었을 경우에는 k개의 글자를 가르치지 못한경우이므로 0을 리턴하게 해주었는데
이렇게 하니 틀렸다고 나오네요.

왜 이렇게 하면 안되는것인지, 그리고 왜 큰돌님께서 작성해주신 답안대로 해야되는지 이해가 가지 않아서 이렇게 질문드립니다. 답변해주시면 감사하겠습니다

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

이렇게 k < 0 일때는 0을 리턴해주고 index==26일때 읽을 수 있는 단어갯수를 리턴해주고 있는데요,

-> k가 음수일 때는 불가능하니 0이고 index == 26일 때는 올바르게 모든 경우의 수를 체크했을 때이기 떄문에 그 때 count를 해준다는 로직입니다.

예를 들어 k-2만을 고른, 상태일때 읽을 수 있는 단어를 리턴해주게 되지 않나요?

좋은 지적입니다. 이 문제는 k개를 가르치고 -> 최댓값을 뽑는 것이죠. 근데 여기서 k - 2개를 가르친게 최댓값이 될 수도 있지만 최댓값이 안되게 되면 -> 자동으로 해당 경우의 수는 버려지게 됩니다.

알파벳을 많이 가르친게 확률적으로 최대값이 된다는 그리디한 부분도 들어갔다고 보시면 되는데요. ㅎㅎ

예를 들어 aaa를 알려면 a만 알아도 되지만 a, b를 알아도 aaa를 알게되죠? 즉 많이 가르친게 절대적으로 더 많은 알파벳을 알게 되는 것입니다.

if(k==0) return count(mask);
if(index == 26 && k > 0 ) return 0;

-> 이렇게 되면 k 미만으로 가르쳤을 때의 경우의 수는 파악하지 못합니다.

따라서 이렇게 하시면 됩니다.

int go(int index, int k, int mask) {
    if (k < 0) return 0;
    if(k == 0) return count(mask);
    if(index == 26) return count(mask);

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 박정호님.

질문 주신 내용은 C++ 코딩 테스트 문제에서 재귀 함수의 기저 사례를 어떻게 처리해야 하는지에 대한 고민 같습니다.

재귀 함수의 기저 사례 이해하기

질문에서 언급한 부분을 이해하기 위해서는 재귀 함수에서 기저 사례(base case)의 역할을 명확히 이해해야 합니다. 기저 사례는 더 이상 재귀 호출을 진행하지 않도록 하고, 계산의 결과를 직접적으로 반환하는 역할을 합니다.

기저 사례 분석:

if (k < 0) return 0;
- 여기서 k가 0보다 작아진다는 것은, 너무 많은 알파벳을 선택한 경우를 의미합니다. 즉, 선택 가능한 알파벳 수를 초과했기 때문에 0을 반환하여 이 경로를 종료합니다.
if (index == 26) return count(mask);
- index == 26은 모든 알파벳을 검사했음을 의미합니다. 이때 마스크(mask)를 통해 지금까지 선택한 알파벳으로 몇 개의 단어를 읽을 수 있는지를 계산하고 반환합니다. 이는 주어진 k개 이하의 알파벳으로 구성 가능한 최대 단어 수를 반환하는 것입니다.

박정호님이 제안한 코드 if(k==0) return count(mask);는 선택 가능한 알파벳 수가 정확히 k개가 되었을 때만 검사를 진행하는 것으로 보입니다. 그러나 원래 조건에 따르면 가능한 알파벳 수가 k개 이하이면 가능하므로, 이렇게 코드가 짜여있는 것입니다.

큰돌님의 코드 이해하기

큰돌님의 코드에서는 모든 알파벳을 끝까지 확인하고 가능한 조합마다 단어의 수를 카운트하는 전략을 씁니다. ‘index’가 26이 되었을 때까지 마스크를 사용하여 각 상태에서의 최대값을 찾고, 이러한 방식으로 전체 탐색을 마친 후에는 자연스럽게 가장 많은 단어를 읽을 수 있는 경우의 수가 찾아집니다.

좀 더 자세히 살펴보시려면 다음의 링크를 참고해 주세요:
- 관련 질문: 4-F 기저사례 질문
- 관련 게시물: 1062 가르침 기저사례 질문

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

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

4-F 1062번 문제 답안코드에서 이해가 가지 않는 부분이 있습니다.

재귀 함수의 기저 사례 이해하기

기저 사례 분석:

큰돌님의 코드 이해하기