인프런 커뮤니티 질문&답변
작성한 질문수
4분 50초쯤 질문입니다.
작성
·
289
0
L 은 현재 탐색중인 노드의 인덱스고
n 은 배열의 크기인데
답은 5 -> 12 -> 8(무시) -> 3 순으로 탐색할때 나오는데
이때는 L == n - 1 아닌가요?
L == n 일때 부분집합이 완성된다는 말이 잘 이해가 가지 않습니다.
이 부분에 대해 설명해주시면 감사하겠습니다!
퀴즈
DFS를 활용한 부분집합 문제 해결의 핵심 아이디어는 무엇일까요?
힙(Heap) 자료구조를 이용해 우선순위 결정
각 원소를 포함하거나 포함하지 않는 두 가지 경로로 분기
너비 우선 탐색으로 모든 경우의 수 동시 탐색
이분 탐색으로 해(Solution)의 존재 여부 확인
답변 1
0
김태원
지식공유자
안녕하세요^^
L은 문제 배열을 탐색하는 인덱스로 사용한 것입니다. 문제배열에 문제는 0번 인덱스부터 n-1인덱스까지 차지하고 있어서 L이 n-1인덱스까지 적용하고 L이 n이 됐을 때 DFS가 하나의 부분집합을 완성한 종료지점으로 온 것입니다.
답변 감사합니다! 이해가 되었습니다