인프런 커뮤니티 질문&답변
작성한 질문수
3-A 질문있습니다.
해결된 질문
작성
·
14
0
안녕하세요 큰돌님:)
해당 문제를 아래와 같이 풀었습니다.
http://boj.kr/0f5124b1f6d449dfab81b98ee45ce9d7
clList.push_back(chList[idx]);
comb(idx + 1);
clList.pop_back();
comb(idx + 1);이런식으로 수업에서 말씀하신 대로 이것은 치킨 집 중에서 m개만 뽑으면 되는 것이니 있고 없고의 경우로 나눠서 조합 코드를 작성했습니다.
저의 코드에서 수정해야 할 방향이 있을까요?
답변 2
0
안녕하세요 원재님 ㅎㅎ
코드 깔끔하고 좋습니다.
다만, ret을 기반으로 최소값을 찾았다면 -> 더이상 최소값을 찾지 않게 가지치기만 넣으면 더 좋을 것 같습니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
원재님께서 작성하신 치킨집 문제 관련 조합 코드에 대해 문의하셨네요! 수업에서 배운 대로 ‘치킨집 중에서 m개만 뽑는’ 방법을 활용한 조합 코드로 작성하신 부분을 보았습니다.
일반적인 조합 방식을 활용하신 것 같으며, clList에 요소를 추가하고 바로 pop_back을 통해 제거하여 다음 경우의 수를 탐색하고 있습니다. 추가된 comb()의 두 번째 호출은 현재 인덱스의 요소를 포함하지 않는 조합을 찾기 위한 부분입니다.
기본적인 접근법은 잘 구성되었지만, 아래 몇 가지 확인 사항을 공유드립니다:
기본 동작 확인: 해당 조합 알고리즘이 정상적으로 n개의 치킨집 중 m개를 정확히 선택하는지, 그리고 최적 해를 구하는지 간단한 테스트 케이스와 도구로 확인해 보시면 좋습니다.
복잡도 고려: 코드의 시간 복잡도를 생각하실 필요가 있습니다. 모든 경우의 수를 다 탐색하려 하다 보면 조합의 성질상, 최악의 경우 시간 초과가 발생할 수 있음을 염두에 두시면 좋겠습니다.
코드 최적화: 해당 조합의 경우,
idx와chList의 관리가 정확히 이루어졌는지(인덱스 범위 초과 등)를 한 번 더 점검해 보시면 좋겠습니다.
나아가, 다음 유사한 상황을 탐색하거나 다른 학습자분들의 질문을 통해 도움을 받을 수 있는 게시물을 추천드립니다:
다만, 접근 방법에 있어서는 정답의 정확성 및 성능 테스트를 다른 입력으로 확신할 수 있는지 최종적으로 검증이 필요할 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.