인프런 커뮤니티 질문&답변
작성한 질문수
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
작성
·
12
·
수정됨
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
백준 링크 : http://boj.kr/a8709cba062743bdb03033918da2f4a6
안녕하십니까 선생님. 수업 잘 듣고있습니다.
교안에 나온 재귀함수로 구현한 조합 방식으로 풀어봤는데 (9C7로 접근하였습니다.) 9C7로 푸는 경우에 이렇게 풀어도 될까요??
또한 위의 풀이가 다행히 시간초과는 뜨지 않았는데 제 코드의 경우 comb() 재귀 호출에 대한 시간복잡도를 어떻게 구해야할지 잘 모르겠습니다..
for문으로 factorial 구현하는 경우는 입력의 최대 크기로 시간복잡도를 구하고 위와 같이 순열,조합류의 문제는 입력의 갯수로 시간 복잡도를 구하는 것같은데, 이렇게 문제에따라 n을 최대 크기로 볼지, 입력의 갯수로 볼지 다르게 판단해야하는건가요??
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 재윤님.
조합을 재귀적으로 구현하는 방식에 대한 질문을 주셨군요. 조합은 주어진 요소 중에서 순서에 상관없이 몇 개의 요소를 선택하는 방법을 의미합니다. 재귀를 사용한 조합은 일반적으로 아래와 같은 논리를 따릅니다:
- 기본 케이스(Base Case): 선택할 요소가 더 이상 남아있지 않거나, 선택해야 할 요소의 수가 0인 경우에 대한 처리를 정의합니다.
- 재귀적 호출: 현재 요소를 선택하는 경우와 선택하지 않는 경우로 분리하여 문제를 쪼개는 방식입니다.
코드를 작성하실 때는, 각각의 선택지가 재귀적으로 호출되어야 하며, 호출마다 올바른 종료 조건을 갖춰야 합니다.
조합 문제를 백준 문제에 맞게 풀기 위해서는, 함수 구조를 제대로 이해하고 구현하는 것이 중요합니다. 코드나 구체적인 부분에 대한 피드백을 받기 위해서는 11-C 재귀함수로 조합 구현에 대한 게시글에서의 해결 방법도 함께 참고할 수 있습니다.
해당 게시물에서는 재귀를 사용한 조합 문제 풀이에 대한 설명과 실질적인 코드 프레임워크가 포함되어 있어 많은 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.