인프런 커뮤니티 질문&답변
작성한 질문수
4-F 질문드립니다.
작성
·
319
0
안녕하세요 강사님!!!
아래는 강사님 답안인데요.
line 15, 17 에서 배우지 않는 경우(line 17)에만 max로 ret을 갱신하는 이유를 이해하지 못하겠습니다.
line 15에서는 max로 ret을 갱신하지 않아도 되는건가요??
https://www.acmicpc.net/source/share/7943b7d08dcb4d30bec01eabbf160e77
감사합니다:)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
답변 3
0
강사님 강의 내용중에서 "이거 안배울래, 하고 넘어갈 수 가 있는거에요" 이 부분이 잘 이해가 안됩니다..
일단 15번 라인에서 ret = go(index+1, k-1, mask|(1<<index)) 들어가게 되면 index가 끝까지 들어가가서 cnt 값을 받아오게 될텐데 , 그 아래쪽 16번 라인에서 if 문을 통해서 다시 ret = max(ret, go(index+1, k, mask) 를 하는 부분은 왜 필요한지도 이해가 되지 않습니다...
0
배웠을 때 go(index+1, k-1, mask|(1<<index)) 랑
안배웠을 때 go(index+1, k, mask) 를 max로 갱신해야 하는 이유가 이해가 가지 않습니다.
안배웠으면 당연히 배웠을 때 보다 값이 더 작아서 max를 안해줘도 되는거 아닐까요..?
두개의 경우의 수중에서 최댓값을 찾아야 하는 것입니다. 예를 들어 a를 배웠을 때가 최댓값인지 배우지 않았을 때가 최댓값인지 비교하는게 중요해서 max를 걸어주어야 합니다.
이제 이해가 되었어요. 비트마스킹을 모든 subset 구하는데 손쉽게 사용하는건 익숙했는데 조합 구하는데도 사용할 수 있다는 것을 이 문제를 통해서 알 수 있게 되었습니다... 하지만 조합을 구할 때는 굳이 비트마스킹이 아니라 그냥 어레이 자체를 가져다가 DFS 해도 될꺼 같다는 생각이 드는데 이때에도 비트마스킹이 좀 더 효율성 같은 데서 장점이 있다고 보면 될까요..? (오히려 인덱싱을 다시 하는 데서 연산이 더 드는 것 같은 느낌도 있어서요)
이제 이해가 되었어요. 비트마스킹을 모든 subset 구하는데 손쉽게 사용하는건 익숙했는데 조합 구하는데도 사용할 수 있다는 것을 이 문제를 통해서 알 수 있게 되었습니다... 하지만 조합을 구할 때는 굳이 비트마스킹이 아니라 그냥 어레이 자체를 가져다가 DFS 해도 될꺼 같다는 생각이 드는데 이때에도 비트마스킹이 좀 더 효율성 같은 데서 장점이 있다고 보면 될까요..? (오히려 인덱싱을 다시 하는 데서 연산이 더 드는 것 같은 느낌도 있어서요)
>>
네 맞습니다.
아마 dfs를 이용한다는 것은 재귀함수를 호출해서 조합을 만든 다는 말씀이시죠? 기본적으로 함수호출보다는 for반복문이 더 코스트가 덜 들기 때문에 비트마스킹이 효율성 측면에서 장점이 있습니다.
0
안녕하세요 ㅎㅎ
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;
}이부분 말씀이시죠?
ret을 정의한다음에. 그 ret과 go라는 함수로 정의된 값과 비교해 ret이라는 변수에 최댓값을 담는 부분인데요.
line 15, 17 에서 배우지 않는 경우(line 17)에만 max로 ret을 갱신하는 이유를 이해하지 못하겠습니다.
>>
이 문제는 ant..를 반드시 배워야 합니다. 즉, 이부분이 아니라면 a가 아닌 e 등의 알파벳의 경우 배우지 않은 경우의 ~~ go함수의 값을 받아 최댓값을 갱신해야 하기 때문에 저런 로직이 들어가는 것입니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
ret = go(index+1, k-1, mask|(1<<index))이코드는 "해당 알파벳을 배우는 경우의 수"
ret = max(ret, go(index+1, k, mask)이 코드는 해당 알파벳을 배우지 않는 경우의 수입니다.
우리는 그 경우의 수 2가지를 비교하고 누적해서 최대치를 뽑아내야 하기 때문에 필요합니다.