시간복잡도 O(2^N)인거는 상관없나요?

23.01.21 12:23 작성 23.01.21 12:23 수정 조회수 361

문제보면 배열 원소 크기 제한이 백만개 이하던데

O(2^N)로는 너무 오래 걸리는 풀이 같아요.

일단 지금은 DFS를 연습하는 정도로만 받아들이면 될까요?

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

5. 합이 같은 부분집합(이진트리 DFS)

강의실 바로가기

답변 2

좋아요순

최신순

답변을 작성해보세요.

문제훈

2023.02.17

입력 설명에 보면

첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다. 두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않으며, 그 크기는 1,000,000 이하입니다.

즉, 원소의 갯수는 1~10개 사이이고 그 원소의 숫자의 크기가 백만 이하입니다.

김태원

2023.02.04

안녕하세요^^

죄송합니다. 제가 질문을 못봤습니다.

문제에는 N제한이 10으로 되어 있습니다. 백만개는 어디를 보고 하시는 말씀인지 모르겠습니다.