인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도 질문있습니다!
작성
·
278
0
안녕하세요!
좋은 강의 만들어주셔서 감사합니다!
다름이 아니라 문제 풀이 중 시간 복잡도 관련하여 궁금한 사항이 있어 질문드립니다!
만약 문제에서 피자집이 200개 이고 m이 12라고 한다면
피자집 조합의 경우만
200C12 = 6107693672247476400 라는 수가 나오게 되서.. 위 케이스에 대해 설명해주신 dfs 방식으로는 제한 시간 1초안에 시간 초과가 날 것 같다는 생각이 들었습니다..!
혹시 맞다면 다른 풀이 방법이 있을까요?
퀴즈
DFS를 활용한 부분집합 문제 해결의 핵심 아이디어는 무엇일까요?
힙(Heap) 자료구조를 이용해 우선순위 결정
각 원소를 포함하거나 포함하지 않는 두 가지 경로로 분기
너비 우선 탐색으로 모든 경우의 수 동시 탐색
이분 탐색으로 해(Solution)의 존재 여부 확인
