4-F 질문드립니다.
404
작성한 질문수 6
안녕하세요 강사님!!!
아래는 강사님 답안인데요.
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
ret = go(index+1, k-1, mask|(1<<index))
이코드는 "해당 알파벳을 배우는 경우의 수"
ret = max(ret, go(index+1, k, mask)
이 코드는 해당 알파벳을 배우지 않는 경우의 수입니다.
우리는 그 경우의 수 2가지를 비교하고 누적해서 최대치를 뽑아내야 하기 때문에 필요합니다.
0
배웠을 때 go(index+1, k-1, mask|(1<<index)) 랑
안배웠을 때 go(index+1, k, mask) 를 max로 갱신해야 하는 이유가 이해가 가지 않습니다.
안배웠으면 당연히 배웠을 때 보다 값이 더 작아서 max를 안해줘도 되는거 아닐까요..?
0
두개의 경우의 수중에서 최댓값을 찾아야 하는 것입니다. 예를 들어 a를 배웠을 때가 최댓값인지 배우지 않았을 때가 최댓값인지 비교하는게 중요해서 max를 걸어주어야 합니다.
0
이제 이해가 되었어요. 비트마스킹을 모든 subset 구하는데 손쉽게 사용하는건 익숙했는데 조합 구하는데도 사용할 수 있다는 것을 이 문제를 통해서 알 수 있게 되었습니다... 하지만 조합을 구할 때는 굳이 비트마스킹이 아니라 그냥 어레이 자체를 가져다가 DFS 해도 될꺼 같다는 생각이 드는데 이때에도 비트마스킹이 좀 더 효율성 같은 데서 장점이 있다고 보면 될까요..? (오히려 인덱싱을 다시 하는 데서 연산이 더 드는 것 같은 느낌도 있어서요)
0
이제 이해가 되었어요. 비트마스킹을 모든 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점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
4 - A
0
26
2
코딩살구클럽 입장이 안됩니다
0
65
2
4-F 경우의 수 질문입니다.
0
33
2
코딩살구클럽 가입이 안됩니다.
0
76
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
57
1
교안 158페이지 문의드립니다
0
45
2
코딩살구클럽 관련 건의사항
0
116
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
44
1
진행 방법 질문드립니다!
0
81
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
63
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
316
2
백준 서비스 종료
9
952
1
sk 하이닉스 코테 대비
0
386
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
65
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
183
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
72
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
53
2